Someone wanted to learn this too, so Grasp built them a personal learning path.

Proving DFA State Lower Bounds with Pairwise Distinguishable Strings

Hello. In the previous lesson, you proved nonregularity by assuming a target language was regular and using closure properties to force a contradiction. That method filtered a language into a known nonregular one.

This lesson begins the Myhill–Nerode viewpoint. Instead of transforming the language, we ask: How much information about a prefix must a DFA retain in order to handle every possible continuation? If two prefixes require different future behavior, they must have led to different DFA states. Finding many such prefixes proves a lower bound on the number of states.

By the end, you will be able to exhibit a set of pairwise distinguishable strings and turn it into a rigorous Myhill–Nerode lower-bound proof.

Distinguishability: different possible futures

Let $L \subseteq Σ^{*}$ . Two strings $x$ and $y$ are distinguishable with respect to $L$ if there is some suffix $z \in Σ^{*}$ such that exactly one of $x z$ and $yz$ belongs to $L$ .

The suffix $z$ is called a distinguishing suffix or witness. Formally, $x$ and $y$ are distinguishable when either

x z \in L and yz \in / L,

x z \in / L and yz \in L .

The empty string is allowed as a suffix. Thus, if $x \in L$ and $y \in / L$ , then $z = ϵ$ already distinguishes them.

The key point is that distinguishability is a property of the language, not of a particular DFA diagram. We use a witness suffix to prove a constraint that every DFA for the language must satisfy.

Consider

K = {0^{n} 1^{n} ∣ n \geq 0} .

The strings $0^{2}$ and $0^{5}$ are distinguishable with respect to $K$ . Take

z = 1^{2} .

Then

0^{2} z = 0^{2} 1^{2} \in K,

but

0^{5} z = 0^{5} 1^{2} \in / K .

The suffix $1^{2}$ reveals that the machine must somehow retain the difference between having seen two zeros and having seen five zeros.

[PDF] Notes on State Minimization 1 Distinguishable and Indistinguishable ...

Read Notes on State Minimization, a Stanford CS154 handout by Luca Trevisan and Ryan Williams. It gives the formal definition of distinguishability and proves the state lower-bound principle that this lesson uses.

In Section 1, “Distinguishable and Indistinguishable States” (PDF pp. 1–2), first read the definition, including the two short examples. Then follow the key lemma: focus on why reaching the same state after x and y would make every common suffix behave identically. On the next page, beginning with “Consider now the following generalization of the notion of distinguishability,” read the set argument, which lifts the idea from one pair of strings to k strings.

Why one distinguishing suffix forces two states

Suppose $M = (Q, Σ, δ, q_{0}, F)$ is a DFA recognizing $L$ . Imagine that two strings $x$ and $y$ lead $M$ to the same state:

δ^{*} (q_{0}, x) = δ^{*} (q_{0}, y) = q .

Once the DFA is in state $q$ , it has no record of whether it arrived after reading $x$ or $y$ . If it then reads the same suffix $z$ , it must behave identically in both cases:

δ^{*} (q_{0}, x z) = δ^{*} (q, z) = δ^{*} (q_{0}, yz) .

Therefore, $x z$ and $yz$ must either both be accepted or both be rejected.

Now take the contrapositive:

If some suffix $z$ makes exactly one of $x z$ and $yz$ belong to $L$ , then $x$ and $y$ must lead to different states in every DFA recognizing $L$ .

This is the engine behind Myhill–Nerode lower bounds. A distinguishing suffix is evidence that the DFA cannot merge two prefixes into one state.

It is useful to frame this in terms of the possible “futures” of a string. Define the future of $x$ relative to $L$ as

{z \in Σ^{*} ∣ x z \in L} .

Two strings are distinguishable exactly when their futures differ: at least one suffix belongs to one future but not the other.

The Myhill–Nerode equivalence relation is written

x \equiv_{L} y ⟺ for every z \in Σ^{*}, x z \in L if and only if yz \in L .

Thus, distinguishable strings lie in different Myhill–Nerode equivalence classes. For this lesson, the important consequence is simple: different equivalence classes require different DFA states.

From one pair to a lower bound

A set of strings

S = {x_{1}, x_{2}, \dots, x_{k}}

is pairwise distinguishable with respect to $L$ if every two different strings in the set are distinguishable. More precisely, for each pair $x_{i} \neq = x_{j}$ , there must be some suffix $z_{i, j}$ such that exactly one of $x_{i} z_{i, j}$ and $x_{j} z_{i, j}$ is in $L$ .

The suffix may depend on the pair. You do not need to find one universal suffix that distinguishes every pair.

Lower-bound principle

If $L$ has a pairwise distinguishable set of $k$ strings, then every DFA recognizing $L$ has at least $k$ states.

The proof is short but should be written carefully.

Let $S = {x_{1}, \dots, x_{k}}$ be pairwise distinguishable with respect to $L$ , and let $M$ be any DFA recognizing $L$ .

For every two distinct indices $i$ and $j$ , the strings $x_{i}$ and $x_{j}$ have a distinguishing suffix. Therefore, they cannot lead $M$ to the same state. Hence the $k$ strings in $S$ lead to $k$ distinct states of $M$ . It follows that $M$ has at least $k$ states.

This is the lower-bound direction of the Myhill–Nerode theorem.

Be precise about what it does and does not establish:

A set of $k$ pairwise distinguishable strings proves at least $k$ states are necessary.
It does not by itself prove that $k$ states are sufficient.
To prove a DFA has exactly $k$ states in the minimum possible implementation, one also needs an equivalent DFA with $k$ states. The next lesson will make that argument systematic.

A finite lower bound: counting ones modulo $m$

Consider, for an integer $m \geq 2$ , the language

D_{m} = {w \in {0, 1}^{*} ∣ #_{1} (w) \equiv 0 (mod m)},

where $#_{1} (w)$ is the number of ones in $w$ . The language contains exactly the strings whose number of ones is divisible by $m$ .

We will prove that any DFA recognizing $D_{m}$ needs at least $m$ states.

Choose the candidate set

S_{m} = {1^{0}, 1^{1}, \dots, 1^{m - 1}} .

Since $1^{0} = ϵ$ , this set has exactly $m$ strings. Intuitively, its members represent the $m$ distinct remainders possible after counting ones.

Take any two distinct strings $1^{i}$ and $1^{j}$ in $S_{m}$ , where

0 \leq i, j \leq m - 1 and i \neq = j .

Use the suffix

z = 1^{m - i} .

Appending $z$ to the first string gives

1^{i} z = 1^{i} 1^{m - i} = 1^{m} \in D_{m} .

But appending the same suffix to $1^{j}$ gives a string with

j + (m - i)

ones. Modulo $m$ , this count has remainder $j - i$ . Because $i \neq = j$ and both indices are between $0$ and $m - 1$ , this remainder is not zero. Therefore,

1^{j} z \in / D_{m} .

So every two distinct strings in $S_{m}$ are distinguishable. By the lower-bound principle, every DFA for $D_{m}$ requires at least $m$ states.

The proof captures a broader pattern:

If a language requires a DFA to remember one of $m$ different unresolved situations, look for $m$ prefixes whose required completions differ.

For $D_{m}$ , the unresolved situation is the count of ones modulo $m$ .

Infinite distinguishable sets prove nonregularity

The same method proves nonregularity when there are arbitrarily large pairwise distinguishable sets.

Return to the language from the previous lesson:

E = {w \in {0, 1}^{*} ∣ #_{0} (w) = #_{1} (w)} .

Previously, you proved $E$ nonregular by intersecting it with the regular filter $0^{*} 1^{*}$ . Now we will see the memory obstruction directly.

Consider the infinite set

S = {0^{i} ∣ i \geq 0} .

Take two different members, $0^{i}$ and $0^{j}$ . Without loss of generality, suppose

i < j .

Choose the suffix

z = 1^{i} .

Then

0^{i} z = 0^{i} 1^{i} \in E,

because the completed string has exactly $i$ zeros and $i$ ones. But

0^{j} z = 0^{j} 1^{i} \in / E,

because it has more zeros than ones.

Thus, $0^{i}$ and $0^{j}$ are distinguishable. Since $i$ and $j$ were arbitrary distinct nonnegative integers, every pair of strings in $S$ is distinguishable.

For any positive integer $k$ , the finite subset

{ϵ, 0, 0^{2}, \dots, 0^{k - 1}}

has $k$ pairwise distinguishable strings. Therefore, any DFA for $E$ would need at least $k$ states for every $k$ .

But a DFA has a fixed finite number of states. If it had $N$ states, taking $k = N + 1$ would yield the contradiction that it needs at least $N + 1$ states. Therefore, $E$ is not regular.

The closure-property proof and this proof reach the same conclusion differently:

The closure proof filters $E$ until the known language $0^{n} 1^{n}$ appears.
The distinguishability proof shows that every possible number of zeros already creates a distinct future requirement.

A reliable proof-writing template

When asked to prove a DFA lower bound using Myhill–Nerode distinguishability, use this structure.

State the target language $L$ and the number $k$ you aim to lower-bound.
Specify a candidate set
$S = {x_{1}, \dots, x_{k}} .$
Take an arbitrary distinct pair from the set. If the strings have parameters, state the relevant condition, such as $i < j$ .
Choose a distinguishing suffix $z$ , usually as a formula based on the pair.
Verify opposite membership outcomes:
$x_{i} z \in L and x_{j} z \in / L,$
or the reverse.
Conclude pairwise distinguishability, then invoke the lower-bound principle to state that every DFA for $L$ has at least $k$ states.

For a nonregularity proof, replace the fixed $k$ with an infinite family, or show that such a set exists for every positive $k$ .

Two frequent errors are worth guarding against:

Error	Why it fails	Repair
Showing that each candidate string can be distinguished from only one other string	A $k$ -state lower bound requires every distinct pair to require different states.	Start with an arbitrary pair and prove the witness construction works for that pair.
Claiming two strings reach different states without comparing membership after a common suffix	Different-looking prefixes can lead to the same state.	Exhibit one suffix that makes exactly one completed string belong to the language.
Finding many strings but not stating why they are pairwise distinguishable	Quantity alone proves nothing; a DFA can merge indistinguishable strings.	Explicitly name the witness suffix and perform both membership checks.
Using a witness that depends on only one string without verifying the other case	The suffix must separate the selected pair, not merely complete one candidate successfully.	Compute both $x z$ and $yz$ .

Key takeaways

A DFA’s state summarizes everything relevant about the input prefix for all future continuations. If two prefixes have a suffix that produces opposite membership outcomes, they cannot share that summary and therefore cannot reach the same state.

A set of $k$ pairwise distinguishable strings gives a Myhill–Nerode lower bound of $k$ states. An infinite pairwise distinguishable set shows that no finite DFA can recognize the language.

Next, you will use the same two ingredients from the opposite direction: to prove that a given DFA is minimal, you will establish that all of its states are reachable and that no two of those states can be merged.

Previous lesson

Proving Nonregularity Using Closure Properties

Next lesson

Proving DFA Minimality: Reachability and State Distinguishability

Can't find a good explanation? Sign up and we'll make it for you