Kleene-Buchi Theorem. For a language L, the following are equivalent:
(1) L is recognized by a finite automaton,
(2) L is defined by a regular expression,
(3) L is definable in Monadic second order logic,
(4) L is recognized by a finite monoid.
The syntactic monoid is defined by the equivalence with
if and only if for every .
Myhill Theorem. A language is regular if and only if the syntactic monoid is finite.
If we define another equivalence relation with
if and only if for every ,
may not be a monoid in general, but we have the following:
Myhill-Nerode Theorem. A language can be recognized by a finite automaton with states if and only if the relation has index ; that is, has classes.