DFA minimisation

Why it exists

The subset construction and the product construction produce DFAs with more states than necessary. A smaller DFA is cheaper to store, easier to compare with another DFA, and, most important for GATE, the smallest DFA of a language is unique, so "the number of states of the minimal DFA" is a well-defined number that questions ask for. Minimisation is also how two DFAs are tested for equivalence.

Prerequisites

You need DFAs and the subset construction (subset construction); counting minimal states for common languages is practised in DFA design patterns.

Precise definitions

Let $D = (Q, \Sigma, \delta, q_0, F)$ be a DFA and extend $\delta$ to strings as $\delta^*$.

• Two states $p, q$ are equivalent, written $p \equiv q$, if for every string $w \in \Sigma^*$: $\delta^*(p, w) \in F \iff \delta^*(q, w) \in F$.
• They are distinguishable if some string $w$ (a distinguishing string) is accepted from exactly one of them. $\equiv$ is an equivalence relation.
• A state is reachable if some string leads to it from $q_0$.
• The minimal DFA of $L$ is a complete DFA for $L$ with the fewest states. Its states are the equivalence classes of the reachable states of any complete DFA for $L$: $[q] \xrightarrow{a} [\delta(q, a)], \quad [q_0] \text{ start}, \quad [q] \text{ accepting iff } q \in F.$
• Theorem. The minimal DFA is unique up to renaming of states, and no DFA for $L$ has fewer states. (The deeper reason is the Myhill-Nerode theorem: the states correspond to the classes of strings with the same future; see Myhill-Nerode.)

Convention. A complete DFA has a transition for every symbol from every state, so the dead state counts as a state. If a question says "minimum number of states of a DFA", count the dead state when the language needs one (this is the usual textbook and GATE convention; if a question explicitly allows a partial DFA the answer is one less). Needs verification against the wording of each question.

How it works

The procedure

1. Remove unreachable states (search from $q_0$). They never matter.
2. Make the DFA complete (add a dead state if some transition is missing).
3. Partition refinement (Moore). Start with two groups: accepting and non-accepting. Repeat: two states stay in the same group only if for every symbol they move into the same group (of the previous round). Stop when a round splits nothing.
4. Merge each group into one state. Transitions and the accepting set are inherited from any member (they are the same for all members).

Why this is right: after round $k$, two states are in the same group exactly when no string of length at most $k$ distinguishes them. Round $0$ uses the empty string; round $k + 1$ prepends one symbol. At most $|Q| - 1$ rounds split anything, because every round that splits increases the number of groups, which cannot exceed $|Q|$.

Example 1: a DFA with a useless parity bit

The first DFA below recognises "ends with $01$" but also remembers whether the number of symbols read is even or odd (states $q_i e$ and $q_i o$), and has a state $u$ that nothing leads to. It has $7$ states, $6$ reachable.

Run the rounds. After the unreachable state is dropped, round $0$ separates the accepting states $\{q_2 e, q_2 o\}$ from the rest. Round $1$ looks at where the states of the big group go on $0$ and on $1$ and splits it into $\{q_0 e, q_0 o\}$ and $\{q_1 e, q_1 o\}$. Round $2$ changes nothing, so we stop with three groups.

Merging the groups gives the minimal DFA: three states, the usual DFA for "ends with $01$".

The table-filling algorithm and distinguishing strings

The same result can be found by marking pairs of states. Make a triangular table of all pairs of reachable states.

1. Mark a pair when exactly one of the two states is accepting (the empty string distinguishes them). These are the level-$0$ pairs.
2. Mark a pair $\{p, q\}$ at level $k + 1$ if for some symbol $a$ the pair $\{\delta(p, a), \delta(q, a)\}$ was marked at level $k$ (so $a$ followed by that pair's distinguishing string distinguishes $p$ and $q$).
3. Repeat until nothing new is marked. The pairs left unmarked are equivalent.

The level of a marked pair is the length of the shortest distinguishing string. The unmarked pairs are then merged into groups (equivalence is transitive, so the groups are well defined).

In this table the pairs $\{q_0 e, q_0 o\}$, $\{q_1 e, q_1 o\}$ and $\{q_2 e, q_2 o\}$ stay empty: the parity bit never changes the future of a string, because "ends with $01$" does not depend on the length.

Equivalence of two DFAs

To test whether two DFAs accept the same language: (a) minimise both and compare the minimal DFAs (they must have the same number of states, the same start, the same transitions up to renaming); or (b) put both machines side by side, run table filling on the combined set of states and see whether the two start states end up equivalent; or (c) search the product automaton for a reachable pair of states of which exactly one is accepting.

Cost

Moore's algorithm takes at most $|Q| - 1$ rounds of $O(|Q| \cdot |\Sigma|)$ work: $O(|Q|^2 |\Sigma|)$. Hopcroft's algorithm needs $O(|\Sigma| \, |Q| \log |Q|)$. (Textbook results, quoted.)

What minimisation does not do

• It is for DFAs. A minimal NFA is not unique, and finding a smallest NFA is a hard problem (quoted, not proved here); an NFA is usually made small by design, not by an algorithm.
• It does not change the language.
• A DFA can already be minimal even if it looks large; the "ends with $01$" machine on three states is minimal because its three states have different futures.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The subset construction produces the DFAs that minimisation reduces (subset construction); the minimal DFA is the object counted by the Myhill-Nerode theorem (Myhill-Nerode); closure constructions such as product and reversal create DFAs whose minimal sizes are asked in GATE (closure properties); scanner generators minimise their DFAs (lexical analysis).

PYQs

Consider a finite state machine (FSM) with one input X
and one output f, represented by the given state transition
table. The minimum number of states required to realize
this FSM is ________. (Answer in integer)

Let Σ = {1,2,3,4}. For x ∈ Σ* , let prod(x) be the product of
symbols in x modulo 7. We take prod(ε) =1,where ε is the
null string .
For example, prod(124) = (1 × 2 × 4) mod 7 = 1.
Define L = {x ∈ Σ* | prod(x) = 2}.
The number of states in a minimum state DFA for L is
___________. (Answer in integer)

Consider the 5-state DFA M accepting the language L(M) ⊂
(0 + 1) * shown below. For any string w ∈ (0 + 1) * let n0(w)
be the number of 0 ' s in w and n1(w) be the number of 1's
in w.

Which of the following statements is/are FALSE?

Consider the language L over the alphabet {0, 1}, given
below: L = {w ∈ {0, 1}* | w does not contain three or more
consecutive 1's}. The minimum number of states in a
Deterministic Finite-State Automaton (DFA) for L is _____.

THEORY OF COMPUTATION

Consider the following language.
L = {x ε {a,b}* | number of a's in x is divisible by 2 but
not divisible by 3}. The minimum number of states in a
DFA that accepts L is _______.

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

The minimum possible number of states of a deterministic
finite automaton that accepts the regular language
L = {w1aw2 | w1, w2 ∈ {a,b}*, |w1| = 2,|w2| ≥ 3} is
_________

Consider
the
language
L
given
by
the
regular
expression (a+b)*b(a+b) over
the
alphabet
{a,b}.
The smallest number of states needed in deterministic finite-
state automaton (DFA) accepting L is _________

The number of states in the minimum sized DFA that
accepts the language defined by the regular expression
(0+1)*(0+1)(0+1)*is_________.

Consider the DFAs M and N given above. The number of
states in a minimal DFA that accepts the language
 L(M) ∩ L(N) is __________.

The number of states in the minimal deterministic finite
automaton corresponding to the regular expression
 (0 + 1) * (10) is __________

Consider the DFA given.

Which of the following are FALSE?
1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal
DFA.
4. A accepts all strings over {0, 1} of length at least 2.

A deterministic finite automation (DFA) D with alphabet
Σ = {a, b} is given below.

Which of the following finite state machines is a valid
minimal DFA which accepts the same language as D?

Definition of a language L with alphabet {a} is given as
following. L = {ank | k > 0, and n is a positive integer
constant} What is the minimum number of states needed
in a DFA to recognize L?

Self-check

Revision card

References