The Myhill-Nerode Theorem

See Kozen (1997) lectures 13-16.

DFA minimization

Every regular language has a minimal DFA that is unique up to isomorphism, and there is an algorithm for constructing it from any given DFA for $A$. Proving uniqueness requires the Myhill-Nerode theorem, but constructing a minimal DFA can be achieved using a simple algorithm.

Given a DFA, the minimization process consists of two steps: getting rid of inaccessible states, and collapsing equivalent states.

The quotient construction

By ‘collapsing’ two states $p$ and $q$, we mean we can identify the two states as being the same, and one larger state.

1. We cannot collapse a final state $p$ and a non-final state $q$, since if $x,y\in {\Sigma }^{\ast }$ were such that $\hat{\delta }(s,x)=p$ and $\hat{\delta }(x,y)=q$, it is impossible to ensure that $x$ is rejected and $y$ is accepted after collapsing.
2. If we merge $p$ and $q$, we are forced to also merge $\delta (p,a)$ and $\delta (q,a)$ for all $a\in \Sigma$, to preserve determinism.

These two observations imply inductively that we cannot collapse $p$ and $q$ if $\hat{\delta }(p,x)\in F$ and $\hat{\delta }(q,x)\notin F$ for some string $x$. It turns out that this is also a sufficient condition.

Proposition 283.1(Proposition).

States $p$ an $q$ of a DFA can be safely collapsed iff there does not exist a string $x$ such that $\hat{\delta }(p,x)\in F$ and $\hat{\delta }(q,x)\notin F$.

Proof.

efine an equivalence relation$\sim$ on $Q$ by

$$p\sim q⟺\forall x\in {\Sigma }^{\ast }(\hat{\delta }(p,x)\in F⟺\hat{\delta }(q,x)\in F).$$

We now define the quotient automaton $M/\sim$:

$$M/\sim :=(Q/\sim ,\Sigma ,{\delta }^{\prime },s^{\prime },F^{\prime }),$$

where

$$\begin{array}{rl}& {\delta }^{\prime }([p],a):=[\delta (p,a)],\\ & s^{\prime }:=[s],\\ & F^{\prime }:=\{[p]|p\in F\}.\end{array}$$

We need to show that ${\delta }^{\prime }$ is well defined: if $p\sim q$, then $\delta (p,a)\sim \delta (q,a)$:

$$\begin{array}{rl}\hat{\delta }(\delta (p,a),x)\in F& ⟺\hat{\delta }(p,ax)\in F\\ & ⟺\hat{\delta }(q,ax)\in F\\ & ⟺\hat{\delta }(\delta (q,a),x)\in F.\end{array}$$

It is also clear that $p\in F⟺[p]\in F^{\prime }$. After showing that for all $x\in {\Sigma }^{\ast }$, ${\hat{\delta }}^{\prime }([p],x)=[\hat{\delta }(p,x)]$, we can show that $L(M/\sim )=L(M)$. Thus, we have shown that $\forall x\in {\Sigma }^{\ast }(\hat{\delta }(p,x)\in F⟺\hat{\delta }(q,x)\in F)$ is a sufficient condition for collapsing $p$ and $q$.

It is also clear that no further collapsing is possible.□

The minimization algorithm

1. Write down a table of all pairs $\{p,q\}$, initially unmarked.
2. Mark $\{p,q\}$ if $p\in F$ and $q\notin F$ or vice versa.
3. Repeat the following until no more changes occur: if there exists an unmarked pair $\{p,q\}$ such that $\{\delta (p,a),\delta (q,a)\}$ is marked for some $a\in \Sigma$, then mark $\{p,q\}$.
4. When done, $p\sim q$ iff $\{p,q\}$ is not marked.

This is easily proved by induction on the length of distinguishing suffixes.

---

The Myhill-Nerode Relations

Correspondence between MH relations and DFAs

Let $M$ be a DFA for a regular language $R\subseteq {\Sigma }^{\ast }$ with no inaccessible states. $M$ induces an equivalence relation ${\equiv }_M$ on ${\Sigma }^{\ast }$ defined by $x{\equiv }_{M}y⟺\hat{\delta }(s,x)=\hat{\delta }(s,y)$. Some properties of ${\equiv }_M$:

1. it is a right congruence: $x{\equiv }_{M}y⟹xa{\equiv }_{M}ya$.
2. It refines $R$: $x{\equiv }_{M}y⟹(x\in R⟺y\in R)$ for all $x,y\in {\Sigma }^{\ast }$.
3. It is of finite index, since $M$ has finitely many states.

Call any equivalence relation $\equiv$ on ${\Sigma }^{\ast }$ a Myhill-Nerode relation for $R$ if it satisfies the three properties above, that is, if it is a right congruence of finite index refining $R$.

Given any Myhill-Nerode relation $\equiv$ on ${\Sigma }^{\ast }$ for $R$, we can produce a DFA $M_{\equiv }=(Q,\Sigma ,\delta ,s,F)$ accepting $R$:

$$\begin{array}{rl}Q& :=\{[x]|x\in {\Sigma }^{\ast }\}\\ s& :=[ϵ]\\ \delta ([x],a)& :=[xa]\\ F& :=\{[x]|x\in R\}.\end{array}$$

These two constructions are inverses up to isomorphism, that is, $M\cong M_{{\equiv }_M}$, and $\equiv ={\equiv }_{M_{\equiv }}$. Thus, Myhill-Nerode relations for $R$ are in a bijective correspondence with DFAs for $R$ with no inaccessible states.

The Myhill-Nerode Theorem

There exists a coarsest Myhill-Nerode relation for any given regular set $R$.

Definition 283.2(Definition).

Let $R\subseteq {\Sigma }^{\ast }$, regular or not. We define an equivalence relation ${\equiv }_R$ on ${\Sigma }^{\ast }$ in terms of $R$ as follows:

$$x{\equiv }_{R}y⟺\forall z\in {\Sigma }^{\ast }(xz\in R⟺yz\in R).$$

For any set $R$, regular or not, ${\equiv }_R$ satisfies properties 1 and 2 of Myhill-Nerode relations and is the coarsest such relation on ${\Sigma }^{\ast }$. If $R$ is regular, this is also of finite index, and therefore a Myhill-Nerode relation on $R$ (the coarsest possible one, and corresponds to the unique minimal finite automaton for $R$).
j

Theorem 283.3(Theorem).

Let $R\subseteq {\Sigma }^{\ast }$. The following statements are equivalent:

1. $R$ is regular;
2. there exists a Myhill-Nerode relation for $R$;
3. the relation ${\equiv }_R$ is of finite index.

---

References

Kozen, D. C. (1997). Automata and Computability. Springer New York. https://doi.org/10.1007/978-1-4612-1844-9