Myhill-Nerode 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}},\ldots,q_{k-1}\}=Q,$ where $\lambda$ is the empty word on $A$ . Construct a DFA $\mathcal{A}=\left<Q,A,q_{0},\delta,F\right>$ (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 $\mathcal{A}=\left<Q,A,q_{0},\delta,F\right>$ 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\{\emptyset\}$ as

f(q)=\left\{\begin{array}[]{ll}[w]_{\mathcal{N}_{L}}&\mathrm{if}\;\delta(q_{0}% ,w)=q\\ \emptyset&\mathrm{if}\;\delta(q_{0},w)\neq q\forall w\in A^{\ast}\end{array}\right.

(3)

Then $f$ is well defined. In fact, suppose $q_{1}=q_{2}=q$ : then either $f(q_{1})=f(q_{2})=\emptyset$ , 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|\geq|A^{\ast}/\mathcal{N}_{L}|$ . $\Box$

Title	Myhill-Nerode theorem
Canonical name	MyhillNerodeTheorem
Date of creation	2013-03-22 18:52:13
Last modified on	2013-03-22 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	Myhill-Nerode theorem for languages