Subset construction

Why it exists

Nondeterministic machines are convenient to design but cannot be run directly by simple hardware or a simple program: a DFA can. The subset construction shows that nothing is lost: every NFA can be converted into a DFA for the same language. It is the algorithm that turns the NFA produced from a regular expression into the DFA of a scanner, and its worst case, an exponential blow-up, is one of the standard facts GATE asks.

Prerequisites

You need the NFA, its epsilon closure and the set simulation (NFA).

Precise definitions

Let $N = (Q, \Sigma, \delta, q_0, F)$ be an NFA (it may have $\varepsilon$ edges). The subset construction builds the DFA $D = (Q_D, \Sigma, \delta_D, d_0, F_D)$:

• the states of $D$ are sets of states of $N$: $Q_D \subseteq \mathcal{P}(Q)$;
• the start state is $d_0 = \operatorname{ECLOSE}(\{q_0\})$;
• for a set $S$ and a symbol $a$: $\delta_D(S, a) = \operatorname{ECLOSE}\bigl(\bigcup_{p \in S} \delta(p, a)\bigr)$ (every state of $S$ moves on $a$, then the closure is taken);
• $S$ is accepting iff $S \cap F \ne \emptyset$.

The empty set $\emptyset$ is a legitimate state: it is the dead state of $D$ (once reached, no computation of $N$ survives).

Correctness idea. After reading $w$, the DFA is in the set of all NFA states that some computation on $w$ can be in. So $D$ accepts $w$ iff some computation of $N$ accepts $w$.

How it works

The algorithm

1. Compute $d_0 = \operatorname{ECLOSE}(\{q_0\})$ and put it in the list of discovered sets.
2. Take the next undiscovered-transition set $S$ from the list. For each symbol $a$ compute $T = \delta_D(S, a)$. Record the transition. If $T$ is new, add it to the list.
3. Stop when every set in the list has all its transitions. Mark as accepting every set that contains a state of $F$.

Only sets reachable from $d_0$ are built, so the DFA usually has far fewer than $2^{|Q|}$ states.

Example 1: ends with 01

The NFA has states $p, q, r$ ($p$ loops on $0, 1$; $p \xrightarrow{0} q$; $q \xrightarrow{1} r$; $r$ accepting). Start: $\{p\}$. On $0$: $p \to \{p, q\}$; on $1$: $p \to \{p\}$. From $\{p, q\}$: on $0$: $p \to \{p, q\}$, $q$ has no $0$-edge: $\{p, q\}$; on $1$: $p \to p$, $q \to r$: $\{p, r\}$. From $\{p, r\}$: on $0$: $\{p, q\}$ ($r$ has no edges); on $1$: $\{p\}$. Three sets, which is the DFA for "ends with $01$" (the $\{p, r\}$ contains $r$ so it accepts).

Example 2: the third symbol from the end is 1

The NFA ($4$ states) leads to $8$ reachable subsets; each records which of the last three symbols were $1$ (a $1$ can be a "guess candidate" at distance $0$, $1$ or $2$ from the end). The DFA below is the result; run it on $01101$ and compare with the NFA run of the previous page: the DFA is in one state at a time, which is the set that the NFA had active.

The blow-up: $2^n$ is reached

For the language "the $n$-th symbol from the end is $1$" the NFA has $n + 1$ states and the subset construction produces $2^n$ states, and no DFA for the language has fewer: the $2^n$ strings of length $n$ are pairwise distinguishable (two different ones differ in some position $i$; appending $i - 1$ symbols puts that position at the $n$-th place from the end, accepted after one string and rejected after the other). So the worst case of the construction is exact.

For a general $n$-state NFA the DFA has at most $2^n$ states, and this bound is reached by the machines above.

Epsilon moves

Take the closure at the start and after every move; the rest is unchanged. For the $\varepsilon$-NFA for $a^* b^*$ (states $s_0$ with an $a$-loop and an $\varepsilon$ edge to $s_1$, $s_1$ with a $b$-loop, accepting): the start set is $\operatorname{ECLOSE}(\{s_0\}) = \{s_0, s_1\}$; on $a$: $\{s_0\}$, closure $\{s_0, s_1\}$; on $b$: $\{s_1\}$; from $\{s_1\}$ on $a$: $\emptyset$ (dead), on $b$: $\{s_1\}$. Three DFA states: $\{s_0, s_1\}$, $\{s_1\}$, $\emptyset$, the DFA with a dead state that has the language $a^* b^*$. (The accepting ones are the first two, since they contain $s_1$.)

The result need not be minimal

The NFA for "contains $00$ or $11$" has $4$ states; the subset construction produces $5$ reachable sets; two of them, $\{a, s, t\}$ and $\{b, s, t\}$, behave identically and are merged by minimisation, leaving $4$ states (minimisation). A good procedure is: build the subset DFA, then minimise it.

Cost of doing it

The construction takes time proportional to the size of the DFA times $|\Sigma|$ times the work to compute a set (about $|Q|^2$ per move with closures): exponential in the worst case. In practice compilers build the DFA lazily, only for the states that the input actually reaches, or minimise the NFA first.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The construction is the second half of "regular expression to scanner" (lexical analysis); the DFA it produces is then reduced by minimisation; combined with the product it gives the closure of regular languages under complement (closure properties).

PYQs

Let M be a nondeterministic finite automaton (NFA)
with 6 states over a finite alphabet. Which of the
following options CANNOT be the number of states in
the minimal deterministic finite automaton (DFA) that is
equivalent to M?

A regular language L is accepted by a non-deterministic
finite automaton (NFA) with n states. Which of the
following statement(s) is/are FALSE?

Let N be an NFA with n states. Let k be the number of
states of a minimal DFA which is equivalent to N. Which
one of the following is necessarily true?

Which of the following pairs have DIFFERENT
expressive power?

Consider the regular grammar:
S → Xa | Ya
X → Za
Z → Sa | ε
Y → Wa
W → Sa
where S is the starting symbol, the set of terminals is
{a} and the set of non-terminals is {S, W, X, Y, Z}. We
wish to construct a deterministic finite automaton
(DFA) to recognize the same language. What is the
minimum number of states required for the DFA?

Self-check

Revision card

References