Myhill-Nerode theorem

Why it exists

How many states does the smallest DFA for a language need? How do you prove that no DFA exists? The pumping lemma answers only the second question, and only in one direction (it can prove non-regularity but never regularity). The Myhill-Nerode theorem gives an exact answer to both: it characterises regular languages by a property of the language alone, and the number it counts is the number of states of the minimal DFA. GATE asks: the minimum number of states of a DFA for this language, prove or decide that this language is regular, how many equivalence classes does this relation have.

Prerequisites

You need DFAs and their minimisation (DFA minimisation), in particular the idea that two states are distinguishable if some string leads one to an accepting state and the other not.

Precise definitions

Fix a language $L \subseteq \Sigma^*$. For strings $x, y \in \Sigma^*$ write

In words: $x$ and $y$ have the same future (the set of suffixes $z$ with $xz \in L$). A string $z$ with exactly one of $xz$, $yz$ in $L$ distinguishes $x$ and $y$.

• $\equiv_L$ is an equivalence relation. Its classes partition $\Sigma^*$. The number of classes is the index of $L$.
• It is right invariant: if $x \equiv_L y$ then $xa \equiv_L ya$ for every symbol $a$ (a continuation of $xa$ is a continuation of $x$).
• $L$ is a union of classes (all members of a class are in $L$ or all are not, since $z = \varepsilon$ is a test).

Theorem (Myhill-Nerode). For a language $L$ the following are equivalent: (1) $L$ is regular; (2) $L$ is the union of some classes of a right invariant equivalence relation of finite index; (3) $\equiv_L$ has finitely many classes. Moreover, the number of classes of $\equiv_L$ is the number of states of the minimal complete DFA for $L$, and that DFA is unique up to renaming the states.

Proof idea. (1) to (3): if a DFA with $k$ states accepts $L$, strings that end in the same state have the same future, so $\equiv_L$ has at most $k$ classes. (3) to (1): build the DFA whose states are the classes, whose start state is the class of $\varepsilon$, whose transition on $a$ sends the class of $x$ to the class of $xa$ (well defined because of right invariance) and whose accepting states are the classes inside $L$. It accepts $L$. No smaller DFA exists, by the first direction.

How it works

Reading the minimal DFA off the classes

Take $L$ = the strings over $\{a, b\}$ that end with $ab$. Group the strings by their future:

Three classes: strings that do not end in $a$ or $ab$ (their future is "must still read $ab$"), strings that end in $a$ (they need one more $b$) and strings that end in $ab$ (accepting). The last three columns of the table are the transition table of the minimal DFA, and no DFA with two states accepts $L$.

The class of a string that cannot be extended to a member of $L$ (every future is empty) is the trap class; a minimal complete DFA has such a state when it exists. A minimal partial DFA drops it, so state the convention when counting.

Proving that a language is not regular

If there are infinitely many pairwise distinguishable strings, the index is infinite and $L$ is not regular. Method: choose an infinite family $x_1, x_2, \dots$ and, for every pair $i \ne j$, a suffix $z_{ij}$ that is completed to a member of $L$ from one of them but not from the other.

For $L = \{a^n b^n : n \ge 0\}$ take $x_i = a^i$. For $i < j$ the suffix $b^i$ gives $a^i b^i \in L$ but $a^j b^i \notin L$:

Every pair is separated, so $L$ has infinitely many classes (at least one for each $i$) and is not regular. A table of classes cannot prove this by itself, but it shows the pattern: as longer prefixes are allowed, the number of classes keeps growing for $a^n b^n$ and for palindromes, while it stops at the number of states for regular languages.

Two cautions. (1) The suffix must work for the pair: one of $xz$, $yz$ in $L$, the other not. (2) Finitely many distinguishable strings never prove anything; the family must be infinite.

Counting the states of a minimal DFA

To find the minimal number of states: find the classes, that is, describe a string by the least information that determines its future, and count the possible values of that information.

• "the number of $a$'s is divisible by 3 and the number of $b$'s is even": the information is (number of $a$'s mod 3, number of $b$'s mod 2): $3 \times 2 = 6$ classes.
• "the $k$-th symbol from the end is $a$": the information is the last $k$ symbols (a shorter string counts as if padded with $b$'s): $2^k$ classes. This is why the DFA for the third symbol from the end has $8$ states while the NFA has $4$.
• "the length is $\equiv 1 \pmod 4$": the information is the length mod 4: $4$ classes.
• "contains $aba$": the information is the longest suffix that is a prefix of $aba$, or "already found": $4$ classes.

A language whose classes are the elements of a group

Let the alphabet be the set of all permutations of $k$ objects, and $L$ the set of strings whose product (composition) is the identity. After reading a string the only thing that matters is the product so far, and two different products are distinguished by the inverse of one of them. So the classes are the $k!$ permutations.

The minimal DFA has $k!$ states; for $k = 5$ that is $120$.

Compared with the pumping lemma

There are non-regular languages that satisfy the pumping condition (see the pumping lemma); Myhill-Nerode classifies them correctly because it is an "if and only if".

Worked examples

Cheat box

Traps and GATE patterns

Connections

The minimisation algorithm of DFA minimisation computes the classes by table filling; the level at which a pair of states is marked equals the length of the shortest string that distinguishes them. The theorem complements the pumping lemma, which only proves non-regularity. Designing a DFA by deciding what to remember (DFA design patterns) is the same as finding the classes.

PYQs

Consider the following two languages over the alphabet {a,
b}:
L1 = { αβα | α ∈ {a, b}+ AND β ∈ {a, b}+ }
L2 = { αβα | α ∈ {a}+ AND β ∈ {a, b}+ }
Which ONE of the following statements is CORRECT?

Let    Σ      be
the
set
of
all
bijections
from {1, ... ,5} to {1, ... ,5}, where id denotes the identity
function, i.e. id(j) = j, ∀j. Let ∘ denote composition on
functions.
For
a
string x= x1x2 ... xn∈Σn, n≥0,
let π(x) = x1 ∘x2 ∘⋯∘xn. Consider the language L=
{x∈Σ*|π(x) = id}. The minimum number of states in
any DFA accepting L is _______

THEORY OF COMPUTATION

Let L1 = {w ∈ {0,1}* | w has at least as many occurrences
of (110)'s as (011)'s}. Let L2 = {w ∈ {0,1}*|w has at least
as many occurrences of (000)'s as (111)'s}. Which one of
the following is TRUE?

Self-check

Revision card

References