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. 1.

$L$ is recognized by a deterministic finite automaton.

2. 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$ (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$ 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 MyhillNerodeTheorem 2013-03-22 18:52:13 2013-03-22 18:52:13 Ziosilvio (18733) Ziosilvio (18733) 14 Ziosilvio (18733) Theorem msc 68Q70 msc 20M35 Myhill-Nerode theorem for languages