**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.

Advertisements