Seonglae ChoInformally, people often define regular languages as:
regular language = a language expressible by a DFA/NFA/regular expression
Myhill–Nerode provides an equivalent viewpoint:
regular language = a language for which the amount of information that must be remembered about the past input is finite
A theorem for deciding whether a language is regular. A language is regular iff the set of equivalence classes induced by the Myhill–Nerode equivalence relation has finite size (i.e., the relation has finite index).
- language membership = whether a string belongs to the language (i.e., whether it is in )
- partition into equivalence classes = grouping strings that behave the same way for all possible future continuations
Myhill–Nerode equivalence
Define an equivalence relation on strings where two strings are indistinguishable by any continuation with respect to membership in . Formally,
Intuition: if , then no suffix can distinguish and by making exactly one of and land in .
Nerode equivalence classes
The equivalence classes of partition into groups of strings that behave identically with respect to . The index of is the number of distinct classes:
Key fact (Myhill–Nerode): is regular iff this number is finite. Moreover, the number of classes equals the number of states in the minimal DFA for .