Proving DFA Minimality: Reachability and State Distinguishability

Good to see you again. In the previous lesson, you used pairwise distinguishable strings to prove that every DFA for a language needs a certain number of states. We now apply the same idea to a DFA that has already been constructed.

This completes the regular-language proof techniques module. The goal is stronger than showing a lower bound in the abstract: you will prove that a particular DFA has exactly the smallest possible number of states. The two facts you must establish are that every state is reachable from the start and that every distinct pair of states is distinguishable by some common suffix.

---

The minimal-DFA criterion

Let

$$M=(Q,\Sigma ,\delta ,q_0,F)$$

be a DFA. Recall that $M$ is minimal when no DFA with fewer than $|Q|$ states recognizes the same language.

Two kinds of redundant states can make a DFA nonminimal:

1. Unreachable states. If no input from the start state ever enters a state $q$, then that state has no effect on the recognized language. It can be removed.

2. Indistinguishable states. If two states have identical acceptance behavior under every possible future input, then the DFA never needs to remember which of those two states it is in. They can be merged.

The following theorem gives a precise test.

Minimal-DFA criterion. A DFA is minimal if and only if:

1. every state is reachable from its start state, and
2. every pair of distinct states is distinguishable.

The first condition shows that all listed states are genuinely used. The second shows that none of the used states can represent the same “future behavior.”

Reachability

A state $q\in Q$ is reachable if there exists a string $x\in {\Sigma }^{\ast }$ such that

$${\delta }^{\ast }(q_0,x)=q.$$

Here, ${\delta }^{\ast }$ is the extended transition function: it describes the state reached after a whole string rather than one symbol.

To prove reachability, give one access string for each state. The empty string $ϵ$ always reaches the start state:

$${\delta }^{\ast }(q_0,ϵ)=q_0.$$

State distinguishability

Two states $p$ and $q$ are distinguishable if some string $z\in {\Sigma }^{\ast }$ makes their future behavior differ:

$${\delta }^{\ast }(p,z)\in F\text{and}{\delta }^{\ast }(q,z)\notin F,$$

or the reverse.

The string $z$ is a distinguishing suffix for the pair of states. As in the previous lesson, $ϵ$ is allowed. Therefore, an accepting state and a rejecting state are immediately distinguishable by $ϵ$.

Be careful about the distinction between the two related ideas:

• Distinguishable strings $x,y$ are compared by starting at $q_0$, then reading $x$ and $y$.
• Distinguishable states $p,q$ are compared by starting directly from $p$ and $q$, then reading the same suffix.

They fit together perfectly. If

$${\delta }^{\ast }(q_0,x)=p\text{and}{\delta }^{\ast }(q_0,y)=q,$$

and $z$ distinguishes $p$ and $q$, then $z$ distinguishes the prefixes $x$ and $y$ with respect to $L(M)$.

---

Why these two conditions prove minimality

The minimal-DFA criterion is not merely a useful rule; it follows directly from the lower-bound argument from the previous lesson.

Suppose $M$ has $k$ states, every state is reachable, and every distinct pair of states is distinguishable. For each state $q_i$, choose an access string $x_i$ such that

$${\delta }^{\ast }(q_0,x_i)=q_i.$$

Because distinct states of $M$ are distinguishable, for each $i\ne j$ there is a suffix $z$ for which exactly one of

$${\delta }^{\ast }(q_i,z)\text{and}{\delta }^{\ast }(q_j,z)$$

is accepting. Equivalently, exactly one of $x_{i}z$ and $x_{j}z$ belongs to $L(M)$. Thus the access strings

$$x_1,x_2,\dots ,x_k$$

are pairwise distinguishable strings for $L(M)$.

By the Myhill–Nerode lower-bound principle, every DFA recognizing $L(M)$ needs at least $k$ states. Since $M$ itself has $k$ states, no smaller equivalent DFA exists. Therefore $M$ is minimal.

This proof reveals the roles of the two requirements:

Requirement	What it contributes to the lower-bound proof
Every state is reachable	Supplies one actual input prefix for each state.
Every pair is distinguishable	Proves that no two of those prefixes may be represented by one state in any equivalent DFA.
$M$ has $k$ states	Supplies the matching upper bound: $k$ states are sufficient.

A common incomplete argument says: “Every pair of states is distinguishable, so the DFA is minimal.” This omits reachability. An unreachable state can be distinguishable from other states but still removable, because no actual computation from the start ever reaches it.

---

Worked proof: binary numbers divisible by three

Consider the DFA in the diagram below. It processes binary strings, allowing leading zeros. Its three states represent the remainder of the binary number read so far when divided by $3$:

• $S_0$: remainder $0$,
• $S_1$: remainder $1$,
• $S_2$: remainder $2$.

Only $S_0$ is accepting, so the DFA recognizes binary representations of multiples of $3$.

Let us prove rigorously that this DFA is minimal.

Step 1: Establish reachability

We need an access string for every state.

State	Access string	Verification
$S_0$	$ϵ$	The empty string leaves the DFA at the start state $S_0$.
$S_1$	$1$	From $S_0$, reading $1$ enters $S_1$.
$S_2$	$10$	From $S_0$, reading $1$ enters $S_1$, and then reading $0$ enters $S_2$.

Hence every state is reachable.

Notice that access strings do not have to be accepted. The string $1$, for example, is not accepted, but it is still a perfectly valid witness that $S_1$ is used.

Step 2: Distinguish every pair of states

There are only three unordered pairs:

$$\{S_0,S_1\},\{S_0,S_2\},\{S_1,S_2\}.$$

Start with pairs involving $S_0$. Since $S_0$ is accepting and $S_1,S_2$ are rejecting, the empty suffix works:

$${\delta }^{\ast }(S_0,ϵ)=S_0\in F,$$

while

$${\delta }^{\ast }(S_1,ϵ)=S_1\notin F.$$

Thus $S_0$ and $S_1$ are distinguishable by $ϵ$. Likewise,

$${\delta }^{\ast }(S_2,ϵ)=S_2\notin F,$$

so $S_0$ and $S_2$ are distinguishable by $ϵ$.

The remaining pair is $S_1,S_2$. They are both rejecting, so $ϵ$ does not separate them. Try the suffix $1$:

$${\delta }^{\ast }(S_1,1)=S_0\in F,$$

but

$${\delta }^{\ast }(S_2,1)=S_2\notin F.$$

Therefore $S_1$ and $S_2$ are distinguishable by $1$.

A compact witness table makes the full argument easy to inspect:

Pair of states	Distinguishing suffix	Result from first state	Result from second state
$S_0,S_1$	$ϵ$	$S_0$, accepting	$S_1$, rejecting
$S_0,S_2$	$ϵ$	$S_0$, accepting	$S_2$, rejecting
$S_1,S_2$	$1$	$S_0$, accepting	$S_2$, rejecting

Every pair of distinct states is distinguishable.

Step 3: State the conclusion

A polished final proof reads as follows:

Every state is reachable: $ϵ$ reaches $S_0$, $1$ reaches $S_1$, and $10$ reaches $S_2$.

The states $S_0$ and $S_1$ are distinguished by $ϵ$, as are $S_0$ and $S_2$, because $S_0$ is accepting while $S_1$ and $S_2$ are rejecting. Finally, $S_1$ and $S_2$ are distinguished by $1$, since reading $1$ sends $S_1$ to accepting state $S_0$ but leaves $S_2$ at rejecting state $S_2$.

Thus every state is reachable and every pair of distinct states is distinguishable. By the minimal-DFA criterion, this DFA is minimal.

The remainder interpretation offers intuition, but it is not the proof. The proof consists of the explicit access strings and distinguishing suffixes.

---

How to find distinguishing suffixes

For small DFAs, use the following disciplined search strategy.

First, use acceptance status

For every accepting state $p$ and rejecting state $q$, record

$$z=ϵ.$$

This immediately handles all mixed accepting/rejecting pairs.

Then, compare transitions from same-status pairs

Suppose $p$ and $q$ are both accepting or both rejecting. Inspect a symbol $a\in \Sigma$.

If $\delta (p,a)$ and $\delta (q,a)$ are already known to be distinguishable by $z$, then $az$ distinguishes $p$ and $q$. Indeed,

$${\delta }^{\ast }(p,az)={\delta }^{\ast }(\delta (p,a),z),$$

and similarly for $q$. Since the two target states have opposite outcomes after $z$, the original states have opposite outcomes after $az$.

For the example DFA:

• $S_1$ and $S_2$ are both rejecting.
• On input $1$, they reach $S_0$ and $S_2$, respectively.
• Those target states differ immediately in acceptance status.
• Therefore $1ϵ=1$ distinguishes $S_1$ and $S_2$.

This is the logical basis of the table-filling minimization method: distinguishability can be propagated backward through matching labeled transitions.

---

A proof-writing template

When asked to prove a given DFA $M=(Q,\Sigma ,\delta ,q_0,F)$ minimal, organize your answer in this order.

1. List reachability witnesses

For each state $q\in Q$, provide a string $x_q$ and verify

$${\delta }^{\ast }(q_0,x_q)=q.$$

A compact table is often best.

2. List pairwise distinguishing witnesses

For every unordered pair of distinct states $p,q$, provide a suffix $z_{p,q}$. Verify explicitly that exactly one of

$${\delta }^{\ast }(p,z_{p,q})\in F$$

and

$${\delta }^{\ast }(q,z_{p,q})\in F$$

holds.

For a DFA with $n$ states, there are

$$\left(\genfrac{}{}{0ex}{}{n}{2}\right)$$

pairs to account for. When state names have a regular pattern, one general argument may cover many pairs; otherwise, a witness table is precise and efficient.

3. Invoke the criterion

End with the exact logical conclusion:

Since every state is reachable and every pair of distinct states is distinguishable, $M$ is minimal.

Avoid weaker conclusions such as “the DFA seems to use all its states” or “no states look mergeable.” Minimality is a universal claim about all possible equivalent DFAs, so it needs the reachability-and-distinguishability theorem.

---

Common proof errors

Error	Why it is insufficient	Repair
Showing only that every state has an incoming edge	An edge from an unreachable component does not make a state reachable from the start.	Give a string beginning at $q_0$ for each state.
Saying two states are different because they have different names or different outgoing edges	Different transition diagrams can still produce identical acceptance behavior.	Find a common suffix that makes one run accept and the other reject.
Comparing states using different suffixes	The two computations must receive the same continuation.	Use one string $z$ from both states in each pair.
Forgetting $ϵ$	Accepting versus rejecting states are already distinguishable.	Test $ϵ$ before searching for a longer witness.
Proving only some pairs distinguishable	One unexamined pair may be mergeable.	Account for every unordered pair, or give a general argument covering them.
Establishing distinguishability but not reachability	An unreachable state can be removed even if it differs from all others.	Prove reachability first.

---

Key takeaways

To prove a particular DFA minimal, show both that:

1. every state is reached by some input from the start state, and
2. every two distinct states have different futures, witnessed by a suffix that makes exactly one computation accept.

The connection to the previous lesson is direct: choose one access string per reachable state. Pairwise state distinguishability makes those access strings pairwise distinguishable for the DFA’s language, forcing every equivalent DFA to retain at least as many states.

You have now completed the regular-language proof toolkit: closure arguments, pumping-lemma proofs, Myhill–Nerode lower bounds, and minimal-DFA proofs. The next module turns to context-free languages, beginning with the constructive task of designing a context-free grammar and proving that it generates exactly the intended language.