Myhill--Nerode Theory and DFA Minimization: Examples and Counterexamples

The states $r$ and $s$ are equivalent because every continuation from either state stays in a rejecting sink. No other pair is equivalent: $q_a$ is distinguished from $q_b$ by the word $b$, and $q_0$ is distinguished from both $q_a$ and $q_b$ by $\epsilon$.

The quotient therefore has four states $[q_0]$, $[q_a]$, $[q_b]$, and $[r]=[s]$. Its only nontrivial merge is the class $[r]=[s]$, and [L1] shows that the quotient recognizes the same language as the original DFA.

Concretely, the quotient still accepts $a$, $b$, and $bb$, while it rejects $\epsilon$, $ab$, and $ba$. The merge removes a redundant rejecting state without changing any acceptance decision.

Fix integers $i<j$. Appending the suffix $1^i$ gives $0^i{1}^i\in L$ and $0^j{1}^i\mathrm{\notin }L$, so [L1] shows that $1^i$ distinguishes the prefixes $0^i$ and $0^j$.

Because every pair $0^i,0^j$ with $i<j$ is distinguished by step 1.1, the family $\{0^n:n\ge 0\}$ is pairwise distinguishable. Therefore [L2] implies that $L$ is not regular.

The same decomposition used in FALSE: the pumping lemma characterizes the regular languages shows that $G$ satisfies the regular pumping conclusion: words with $\mathrm{\mid }w\mathrm{\mid }\ge 2$ pump on the first letter of the front copy of $w$, while words with $\mathrm{\mid }w\mathrm{\mid }=1$ pump inside the nonempty tail $v$.

For each $n\ge 1$, the prefix $p_n=(01{)}^n$ is distinguished from every longer $p_m=(01{)}^m$ by the suffix $x_n=(10{)}^{n}1$, because [L3] gives $p_n{x}_n\in G$ and $p_m{x}_n\mathrm{\notin }G$ when $m>n$. Hence the prefixes $p_n$ are pairwise distinguishable, so [L2] shows that $G$ is not regular.

Thus $G$ is a concrete nonregular language that still satisfies the pumping conclusion, so it is a counterexample to the refuted statement.