Myhill-Nerode theorem

Let $L$ be a language on the finite alphabet $A$and let ${𝒩}_L$ be its Nerode equivalence.The following are equivalent.

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

2. $A^{\ast }/{𝒩}_L$ is finite.

Moreover, the number of classes of ${𝒩}_L$is the smallest number of states of a DFA recognizing $L$.

Proof.First, suppose$A^{\ast }/{𝒩}_L=\{q_0={[\lambda ]}_{{𝒩}_L},\mathrm{\dots },q_{k-1}\}=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]}_{{𝒩}_L},w\in q,$$(1)

and

$$F=\{q\in Q\mid \exists w\in L\mid w\in q\}.$$(2)

Then $\delta$ is well definedbecause $w_1{𝒩}_L{w}_2$ implies $w_{1}u{𝒩}_L{w}_{2}u$.It is also straightforward that $𝒜$ 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 }/{𝒩}_L\cup \{\mathrm{\varnothing }\}$ as

(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{𝒩}_L{w}_2$ since $𝒜$ recognizes $L$.Finally, for any $w\in A^{\ast }$ we have${[w]}_{{𝒩}_L}=f\left(\delta (q_0,w)\right),$so every class of ${𝒩}_L$ has a preimage according to $f$;consequently, $|Q|\ge |A^{\ast }/{𝒩}_L|$. $\mathrm{\square }$