# Finite automata, monoids, and Myhill-Nerode theorem

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 $M(L) = \Sigma^*/\cong_L$ is defined by the equivalence $\cong_L$ with

$u \cong_L v$ if and only if $xuy \in L \iff xvy \in L$ for every $x,y \in \Sigma^*$.

Myhill Theorem.  A language is regular if and only if the syntactic monoid is finite.

If we define another equivalence relation $\sim_L$ with

$u \sim_L v$ if and only if $uy \in L \iff vy \in L$ for every $y \in \Sigma^*$,

$\Sigma^*/\sim_L$ may not be a monoid in general, but we have the following:

Myhill-Nerode Theorem.  A language $L$ can be recognized by a finite automaton with $k$ states if and only if the relation $\sim_L$ has index $k$; that is, $\Sigma^*/\sim_L$ has $k$ classes.