MyhillNerode theorem
Let $L$ be a language^{} on the finite alphabet $A$ and let ${\mathcal{N}}_{L}$ be its Nerode equivalence. The following are equivalent^{}.

1.
$L$ is recognized by a deterministic finite automaton.

2.
${A}^{\ast}/{\mathcal{N}}_{L}$ is finite.
Moreover, the number of classes of ${\mathcal{N}}_{L}$ is the smallest number of states of a DFA recognizing $L$.
Proof. First, suppose ${A}^{\ast}/{\mathcal{N}}_{L}=\{{q}_{0}={[\lambda ]}_{{\mathcal{N}}_{L}},\mathrm{\dots},{q}_{k1}\}=Q,$ where $\lambda $ is the empty word^{} on $A$. Construct a DFA $$ (called the Nerode automaton for $L$) with $\delta :Q\times A\to Q$ defined by
$$\delta (q,a)={[wa]}_{{\mathcal{N}}_{L}},w\in q,$$  (1) 
and
$$F=\{q\in Q\mid \exists w\in L\mid w\in q\}.$$  (2) 
Then $\delta $ is well defined because ${w}_{1}{\mathcal{N}}_{L}{w}_{2}$ implies ${w}_{1}u{\mathcal{N}}_{L}{w}_{2}u$. It is also straightforward that $\mathcal{A}$ recognizes $L$.
On the other hand, let $$ be a DFA that recognizes $L$. Extend $\delta $ to $Q\times {A}^{\ast}$ by putting $\delta (q,\lambda )=q$ and $\delta (q,aw)=\delta (\delta (q,a),w)$ for every $q\in Q$, $a\in A$, $w\in {A}^{\ast}$. Define $f:Q\to {A}^{\ast}/{\mathcal{N}}_{L}\cup \{\mathrm{\varnothing}\}$ as
$$f(q)=\{\begin{array}{cc}{[w]}_{{\mathcal{N}}_{L}}\hfill & \mathrm{if}\delta ({q}_{0},w)=q\hfill \\ \mathrm{\varnothing}\hfill & \mathrm{if}\delta ({q}_{0},w)\ne q\forall w\in {A}^{\ast}\hfill \end{array}$$  (3) 
Then $f$ is well defined. In fact, suppose ${q}_{1}={q}_{2}=q$: then either $f({q}_{1})=f({q}_{2})=\mathrm{\varnothing}$, or there are ${w}_{1},{w}_{2}\in {A}^{\ast}$ such that $\delta ({q}_{0},{w}_{1})=\delta ({q}_{0},{w}_{2})=q$. But in the latter case, $\delta ({q}_{0},{w}_{1}u)=\delta ({q}_{0},{w}_{2}u)=\delta (q,u)$ for any $u\in {A}^{\ast}$, hence ${w}_{1}{\mathcal{N}}_{L}{w}_{2}$ since $\mathcal{A}$ recognizes $L$. Finally, for any $w\in {A}^{\ast}$ we have ${[w]}_{{\mathcal{N}}_{L}}=f\left(\delta ({q}_{0},w)\right),$ so every class of ${\mathcal{N}}_{L}$ has a preimage^{} according to $f$; consequently, $Q\ge {A}^{\ast}/{\mathcal{N}}_{L}$. $\mathrm{\square}$
Title  MyhillNerode theorem 

Canonical name  MyhillNerodeTheorem 
Date of creation  20130322 18:52:13 
Last modified on  20130322 18:52:13 
Owner  Ziosilvio (18733) 
Last modified by  Ziosilvio (18733) 
Numerical id  14 
Author  Ziosilvio (18733) 
Entry type  Theorem 
Classification  msc 68Q70 
Classification  msc 20M35 
Synonym  MyhillNerode theorem for languages 