Finite Playground

To verify is human; to prove, divine.

Leave a comment

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.