Algebraic Characterization of Regular Languages: How to Cope With All These Equivalences?

摘要

Algebraic characterization of regular languages is one of the difficult parts in Automata Theory course. Typically, this part covers two topics. One is Nerod theorem: it provides an algebraic criterion for regularity of a language; for regular language it also provides a basis for understanding the structure of the minimal DFA that accepts it. Another topic is minimization of finite automata. Both topics are based on consideration of a variety of equivalences (general equivalence relation on words, right-invariant equivalence, equivalence R_L induced by a given language L, equivalence and k-equivalence of states, equivalence of automata). Moreover, relations between different equivalences (such as equality and refinement) are also employed. Being rather abstract, these concepts and techniques cause numerous difficulties and misconceptions that lead students to severe errors in problem solutions. Sometimes, trying to avoid these difficulties, students tend to heavily rely on visual representation of the automata model that makes things so to speak "obvious". For example, in automata minimization it is typical for students that equivalent states are identified "at a glance", ignoring the formal process for incremental construction of equivalence classes. Of course, this "method" captures only simple cases of equivalence and leaves the important concepts not understood properly.