Myhill--Nerode Theory and DFA Minimization

Equality of right languages is reflexive, symmetric, and transitive, so [L1] and [L2] show that ${\equiv }_D$ is an equivalence relation on $Q$.

Fix a letter $a\in \mathrm{\Sigma }$. If $p{\equiv }_{D}q$, then induction on $v$ using [L3] gives ${\delta }^{\ast }(\delta (p,a),v)={\delta }^{\ast }(p,av)$ and ${\delta }^{\ast }(\delta (q,a),v)={\delta }^{\ast }(q,av)$ for every word $v$; applying [L1] to the continuation $av$ therefore yields $\delta (p,a){\equiv }_D\delta (q,a)$.

We now induct on the word $u$. The case $u=\epsilon$ is immediate from [L3]. If the claim holds for $u$ and $a\in \mathrm{\Sigma }$, then step 1.2 applied to the equivalent states ${\delta }^{\ast }(p,u)$ and ${\delta }^{\ast }(q,u)$ gives ${\delta }^{\ast }(p,ua){\equiv }_D{\delta }^{\ast }(q,ua)$.

Steps 1.1 and 2.1 prove both claims.

Step [L2] shows that if $q{\equiv }_D{q}^{\mathrm{\prime }}$ then $[\delta (q,a)]=[\delta (q^{\mathrm{\prime }},a)]$ for every letter $a$, so $\bar{\delta }([q],a)$ is independent of the chosen representative.

If $q{\equiv }_D{q}^{\mathrm{\prime }}$ and $q\in F$, then [L4] gives ${\delta }^{\ast }(q,\epsilon )=q$ and ${\delta }^{\ast }(q^{\mathrm{\prime }},\epsilon )=q^{\mathrm{\prime }}$. Applying [L5] to the continuation $\epsilon$ therefore shows $q^{\mathrm{\prime }}\in F$ as well. Thus $\bar{F}$ is representative-independent.

Let ${\bar{\delta }}^{\ast }$ be the extended transition of the quotient DFA. Induction on $u$ using [L1] and [L4] gives ${\bar{\delta }}^{\ast }([q],u)=[{\delta }^{\ast }(q,u)]$ for every state class $[q]$ and every word $u$.

For every word $u$, step 1.3 and [L3] give $u\in L(D\mathrm{/}{\equiv }_D)⟺{\bar{\delta }}^{\ast }([q_0],u)\in \bar{F}⟺[{\delta }^{\ast }(q_0,u)]\in \bar{F}⟺{\delta }^{\ast }(q_0,u)\in F⟺u\in L(D)$.

Therefore the quotient DFA is well defined and equivalent to $D$.

Reflexivity, symmetry, and transitivity follow immediately from the biconditional in [L1], so [L2] shows that ${\equiv }_L$ is an equivalence relation.

Assume $u{\equiv }_{L}v$ and fix $x\in {\mathrm{\Sigma }}^{\ast }$. For every continuation $y$, [L1] applied to the continuation $xy$ gives $uxy\in L⟺vxy\in L$, which is exactly the condition $(ux){\equiv }_L(vx)$.

Therefore ${\equiv }_L$ is an equivalence relation preserved by right concatenation.

For every state $s$ and words $x,z$, repeated use of [L3] gives ${\delta }^{\ast }(s,xz)={\delta }^{\ast }({\delta }^{\ast }(s,x),z)$; in particular, ${\delta }^{\ast }(q_0,uz)={\delta }^{\ast }({\delta }^{\ast }(q_0,u),z)$ and ${\delta }^{\ast }(q_0,vz)={\delta }^{\ast }({\delta }^{\ast }(q_0,v),z)$.

If ${\delta }^{\ast }(q_0,u)={\delta }^{\ast }(q_0,v)$, then step 1.1 implies ${\delta }^{\ast }(q_0,uz)={\delta }^{\ast }(q_0,vz)$ for every $z\in {\mathrm{\Sigma }}^{\ast }$. By [L2], this gives $uz\in L$ if and only if $vz\in L$ for every $z$, so [L1] yields $u{\equiv }_{L}v$.

Therefore every reachable state of $D$ contains words from at most one Nerode class, and distinct Nerode classes must land in distinct reachable states.

Assume $L$ is regular. By [L1], choose a DFA $D$ recognizing $L$. Step [L2] gives an injection from the set of Nerode classes of $L$ into the reachable state set of $D$, so the index of ${\equiv }_L$ is finite because a DFA has only finitely many states.

Assume conversely that ${\equiv }_L$ has finite index. Let $Q$ be its finite set of equivalence classes, let the start state be $[\epsilon ]$, define $\delta ([u],a):=[ua]$, and let $F:=\{[u]\in Q:u\in L\}$. By [L3], the transition rule is well defined, so [L4] gives a DFA $D_L=(Q,\mathrm{\Sigma },\delta ,[\epsilon ],F)$.

For every word $u\in {\mathrm{\Sigma }}^{\ast }$, induction on $u$ shows that the state reached by $D_L$ from $[\epsilon ]$ is exactly $[u]$. Hence $u\in L(D_L)⟺[u]\in F⟺u\in L$, so $D_L$ recognizes $L$ and [L1] implies that $L$ is regular.

Steps 1.1 and 2.1 prove both implications.

Because $L$ is regular, [L1] provides a DFA $D_L$ whose states are exactly the Nerode classes of $L$ and which recognizes $L$.

Let $D$ be any DFA recognizing $L$. Every Nerode class contains some word $u$, and the state reached by $D$ on $u$ is reachable. By [L2], two distinct Nerode classes cannot reach the same state of $D$, so $D$ has at least as many reachable states as $D_L$ has states.

Step 1.2 shows that no DFA for $L$ can use fewer reachable states than $D_L$, so $D_L$ is minimal. It is canonical because its states are defined directly from the language $L$ rather than from an auxiliary machine.

A minimal DFA has no unreachable states. Indeed, if $D_i$ had an unreachable state, then [L3] would remove it without changing the language, contradicting minimality.

Let $D_L$ be the canonical Nerode-class DFA from [L1]. Because step 1.1 shows that every state of $D_i$ is reachable, for each state $q$ of $D_i$ we may choose a word $u$ with ${\delta }_i^{\ast }(q_{0,i},u)=q$, which is possible by [L2], and send $q$ to the Nerode class $[u]$. If two words $u,v$ reach the same state $q$, then every continuation is accepted or rejected identically from that state, so $u$ and $v$ determine the same Nerode class. Thus the map is well defined. For any Nerode class $[u]$, the state reached by $D_i$ on $u$ maps to $[u]$, so the map is surjective onto the state set of $D_L$.

Both $D_i$ and $D_L$ are minimal DFAs for $L$: $D_i$ by hypothesis and $D_L$ by [L1]. Therefore their finite state sets have the same cardinality. The surjection from step 2.1 between finite sets of equal size is therefore a bijection.

The bijection of steps 2.1 and 3.1 sends the start state to $[\epsilon ]$, and its definition via reaching words shows that it preserves letter transitions and accepting states. Hence each $D_i$ is pointed-isomorphic to $D_L$, so $D_1$ and $D_2$ are pointed-isomorphic to one another.

Replace $D$ by its reachable part using [L1]. Let $M_0$ be the set of accepting/nonaccepting pairs, and for $t\ge 0$ let $M_{t+1}$ be obtained from $M_t$ by also marking every pair $\{p,q\}$ for which some letter $a$ has $\{\delta (p,a),\delta (q,a)\}\in M_t$. Put $M:={\bigcup }_t{M}_t$.

We prove by induction on $t$ that every pair in $M_t$ has a distinguishing word of length at most $t$. For $M_0$, the empty word distinguishes every accepting/nonaccepting pair by [L2]. For the induction step, if $\{p,q\}$ is newly marked because $\{\delta (p,a),\delta (q,a)\}\in M_t$, prepend the letter $a$ to a distinguishing word for the successor pair.

Conversely, we induct on the length of a distinguishing word $x$. If $x=\epsilon$, then the pair is in $M_0$. If $x=ay$, then $y$ distinguishes $\delta (p,a)$ and $\delta (q,a)$, so the induction hypothesis puts the successor pair in some $M_t$, and the algorithm then marks $\{p,q\}$ at the next stage. Therefore a pair is marked exactly when it is distinguishable.

Unmarked pairs are therefore precisely the indistinguishable pairs, hence precisely the state-equivalent pairs by [L2]. By [L3] this is an equivalence relation, and [L4] gives an equivalent quotient DFA $Q$.

Let $E$ be any reachable DFA equivalent to $D$. Because step 1.1 replaced $D$ by its reachable part, each state class $C$ of $Q$ has a representative state $q_C$ reached in $D$ by some word $u_C$. Send $C$ to the state reached by $E$ on $u_C$. If $C\mathrm{\ne }{C}^{\mathrm{\prime }}$, then their representatives are distinguishable by step 3.1; choose a distinguishing word $x$. The words $u_{C}x$ and $u_{C^{\mathrm{\prime }}}x$ are then accepted differently by $D$, hence also by the equivalent DFA $E$, so the reached states of $E$ are distinct. Thus this map from the states of $Q$ into the states of $E$ is injective.

Therefore every reachable DFA equivalent to $D$ has at least as many states as $Q$. Since $Q$ itself is equivalent to $D$ by step 4.1, it is a minimal DFA for the same language.

Choose the DFA $D$ recognizing $L$ supplied by [L0], and let $p$ be its number of states, which is finite by [L1]. Fix a word $w=a_1\cdots a_m\in L$ with $m\ge p$. As $D$ reads the prefixes $\epsilon ,a_1,a_1{a}_2,\dots ,a_1\cdots a_p$, [L3] gives $p+1$ visited states.

By [L4], two of those first $p+1$ visited states are equal; write them as the states after the prefixes of lengths $i<j\le p$, and set $x:=a_1\cdots a_i$, $y:=a_{i+1}\cdots a_j$, and $z:=a_{j+1}\cdots a_m$. Then $w=xyz$, $\mathrm{\mid }xy\mathrm{\mid }=j\le p$, and $\mathrm{\mid }y\mathrm{\mid }=j-i>0$.

Because the run returns to the same state after reading $y$, repeating or deleting that loop does not change the state reached before the suffix $z$. Therefore [L2] implies $x{y}^{i}z\in L$ for every $i\ge 0$, so the factorization from step 2.1 satisfies all three required conditions.

If two words are pairwise distinguished by suffixes, then [L1] shows that they lie in distinct Nerode classes.

Therefore the infinitely many given words occupy infinitely many Nerode classes. By [L2], $L$ cannot be regular.

The language $G$ satisfies the pumping conclusion with pumping length $4$. If $s=w{w}^{R}v\in G$ with $\mathrm{\mid }w\mathrm{\mid }\ge 2$, write $w=au$ with $u\mathrm{\ne }\epsilon$ and choose $x=\epsilon$, $y=a$, $z=u{u}^{R}av$; then $xz=u{u}^{R}av\in G$, the original word is $xyz\in G$, and for every $i\ge 2$ the word $x{y}^{i}z=a^{i}u{u}^{R}av$ lies in $G$ by using the one-letter witness word $a$ and the nonempty suffix $a^{i-2}u{u}^{R}av$.

For each $n\ge 1$, let $p_n:=(01{)}^n$ and $x_n:=(10{)}^{n}1$. Then $p_n{x}_n=(01{)}^n(10{)}^{n}1$ lies in $G$ by taking witness word $(01{)}^n$ and suffix $1$. If $m>n$ and $p_m{x}_n$ were in $G$, write $p_m{x}_n=r{r}^{R}v$ with $r\mathrm{\ne }\epsilon$ and $v\in \{0,1{\}}^{+}$. The word $p_m{x}_n=(01{)}^m(10{)}^{n}1$ has exactly one doubled adjacent pair, namely the middle 11 at the junction between $(01{)}^m$ and $(10{)}^{n}1$. Any prefix of the form $r{r}^R$ has a doubled middle pair at the boundary between $r$ and $r^R$, so that boundary must be this unique 11. Hence $\mathrm{\mid }r\mathrm{\mid }=2m$, which makes the palindromic prefix $r{r}^R$ have length $4m$. But $\mathrm{\mid }{p}_m{x}_n\mathrm{\mid }=2m+2n+1<4m+1$ because $n<m$, so no such factorization with nonempty $v$ exists. Therefore $p_m{x}_n\mathrm{\notin }G$, and the prefixes $p_n$ are pairwise distinguishable.

If instead $\mathrm{\mid }w\mathrm{\mid }=1$, then $s=aav$ with $\mathrm{\mid }v\mathrm{\mid }\ge 2$ because $\mathrm{\mid }s\mathrm{\mid }\ge 4$; writing $v=bt$ and choosing $x=aa$, $y=b$, $z=t$ pumps entirely inside the nonempty suffix $v$, so every $x{y}^{i}z$ stays in $G$. Thus every sufficiently long word in $G$ has a legal pumping decomposition.

Step 1.2 and [L2] show that $G$ is not regular, while steps 1.1 and 2.1 show that $G$ still has the regular pumping property. Therefore the pumping property does not characterize regularity, and the statement is false.

The language $O$ is regular: a two-state DFA that toggles parity after each input symbol accepts exactly the words of odd length.

Fix any pumping length $p\ge 1$ and take $w:=0^{2p+1}\in O$. The decomposition $x:=\epsilon$, $y:=0$, $z:=0^{2p}$ is legal because $\mathrm{\mid }xy\mathrm{\mid }=1\le p$ and $\mathrm{\mid }y\mathrm{\mid }>0$, but pumping once gives $xz=0^{2p}$, whose length is even, so $xz\mathrm{\notin }O$. Thus this legal decomposition does not pump.

Step 1.2 shows that a regular language can have bad legal decompositions even though [L1] supplies some good one. Therefore the quantifiers cannot be reordered as stated, and the statement is false.