The subset construction

DFAs can be viewed as a special case of NFAs, i.e. those for which the the there is precisely one start state $S=\{q_0\}$ and the transition function returns always one-element sets (i.e. $\delta(q,x)=\{q'\}$ for all $q\in Q$ and $x\in\Sigma$).

Below we show that for every NFA we can construct a DFA which accepts the same language. This shows that NFAs aren't more powerful as DFAs. However, in some cases NFAs need a lot fewer states than the corresponding DFA and they are easier to construct.

Given an NFA $A=(Q,\Sigma,\delta,S,F)$ we construct the DFA

$$D(A)=({\cal P}(Q),\Sigma,\delta_{D(A)},S,F_{D(A)})$$

where

$$\delta_{D(A)}(S,x) = \bigcup \{ \delta(q,x) \mid q \in S \}$$

$$F_{D(A)} = \{ S \subseteq Q_N \mid S \cap F \not= \{\} \}$$

The basic idea of this construction (the subset construction) is to define a DFA whose states are sets of states of the NFA. A final state of the DFA is a set which contains at least a final state of the NFA. The transitions just follow the active set of markers, i.e. a state $S\in{\cal P}(Q_N)$ corresponds to having markers on all $q\in S$ and when we follow the arrow labelled $x$ we get the set of states which are marked after reading $x$.

As an example let us consider the NFA $C$ above. We construct a DFA $D(C)$

$$D(C) = ({\cal P}(\{q_0,q_1,q_2\},\{0,1\},\delta_{D(C)},\{q_0\},F_{D(C)})$$

with $\delta_{D(C)}$ given by

$$\begin{array}{r\vert\vert c\vert c} \delta_{D(C)} & 0 & 1 \... ... {*}\{q_0,q_1,q_2\} & \{q_0,q_2\} & \{q_0,q_1,q_2\} \end{array}$$

and $F_{D(C)}$ is the set of all the states marked with ${*}$ above,i.e.

$$F_{D(C)} = \{ \{q_2\},\{q_0,q_2\},\{q_1,q_2\},\{q_0,q_1,q_2\}\}$$

Looking at the transition diagram:

we note that some of the states ( $\{\},\{q_1\},\{q_2\},\{q_1,q_2\}$) cannot be reached from the initial state, which means that they can be omitted without changing the language. Hence we obtain the following automaton:

We still have to convince ourselves that the DFA $D(A)$ accepts the same language as the NFA $A$, i.e. we have to show that $L(A)=L(D(A))$.

As a lemma we show that the extended transition functions coincide:

Lemma 2.1  

$$\hat{\delta}_{D(A)}(S,w) = \hat{\delta_{A}}(S,w)$$

The result of both functions are sets of states of the NFA $A$: for the left hand side because the extended transition function on NFAs returns sets of states and for the right hand side because the states of $D(A)$ are sets of states of $A$.

Proof: We show this by induction over the length of the word $w$, let's write $\vert w\vert$ for the length of a word.

$\vert w\vert=0$

Then $w=\epsilon$ and we have

$$% latex2html id marker 4677 \begin{array}{lcl} \ \hat{\delta... ...lumn{2}{l}{\textrm{by (\ref{n-delta-hat-epsilon})}} \end{array}$$

$\vert w\vert=n+1$

Then $w=xv$ with $\vert v\vert=n$.

$$% latex2html id marker 4685 \begin{array}{lcl} \ \hat{\delta... ...m{(*) see below.}}\\ & = & \hat{\delta}_A(S,xv) \end{array}$$

$\Box$

We note that in the step marked with (*) we use a property of $\hat{\delta}_A$ which requires another lemma:

Lemma 2.2  

$$\hat{\delta}_A(\bigcup P,w) = \bigcup \{ \hat{\delta}_A(S,w) \mid S\in P \}$$

I leave it as an exercise to prove this lemma.

We can now use the lemma to show

Theorem 2.3  

$$L(A) = L(D(A))$$

Proof:

$$% latex2html id marker 4697 \begin{array}{c} w \in L(A) \\ ... ...m{Definition of $L(A)$\ for DFAs}\\ w\in L_{D(A)} \end{array}$$

$\Box$

Corollary 2.4   NFAs and DFAs recognize the same class of languages.

Proof: We have noticed that DFAs are just a special case of NFAs. On the other hand the subset construction introduced above shows that for every NFA we can find a DFA which recognizes the same language. $\Box$