Converting an NFA to a DFA

We will show how to convert a non-deterministic automaton to a deterministic automaton, which proves that non-deterministic and deterministic automata have equal computational power.

The basic idea

Take a non-deterministic automaton ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ without epsilon transitions. We construct a deterministic automaton ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ as follows:

• Q_D ⊆ 2^Q_N
• Σ_D = Σ_N
• p₀ = {q₀}
• F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

We define the transition function δ_D as follows:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\Sigma }}_D:{\delta }_D(Q,a)=\bigcup _{q\in Q}{\delta }_N(q,a)$$

What does this mean? A non-deterministic automaton can be in several states at once, so, for example, we can reach a situation where our non-deterministic automaton is in the states {q₀, q₁}. By reading the next symbol, say 1, we can get to the set of states {q₀, q₂, q₃}. In the deterministic version of the same automaton this appears as follows: we create two states, name them {q₀, q₁} and {q₀, q₂, q₃} and introduce a transition between them for the symbol 1. Formally we move from one state to the other, but thanks to the naming we know that in the non-deterministic automaton we would find ourselves in two states, or three states respectively.

Example

Take this non-deterministic automaton:

To construct the deterministic automaton we first need to build the new transition function. A table in which we record all the transitions will help us. At the start the table looks like this:

$$\begin{array}{ccc}\text{state}/\text{symbol}& 0& 1\\ \left\{q_0\right\}\end{array}$$

At the end of the algorithm the left-hand column will contain all the states of the deterministic automaton. The completed table will then define the transition function. Now we write into the table which states we get to if we are in the state {q₀} and the input symbols are 0 and 1.

$$\begin{array}{ccc}\text{state}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

From state q₀ there is a transition for the symbol 0 only to state q₁, whereas for the symbol 1 it leads to states q₁ and q₂. Now we add two new states to the table: {q₁} and {q₁, q₂}. Why? Whenever we write into the table a set of states that is not yet in the left-hand column, we add that set of states there.

$$\begin{array}{ccc}\text{state}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

and we fill it in again. For the state {q₁, q₂} we must not forget to check both states, that is, the union of where we get to from state q₁ and where we get to from state q₂.

$$\begin{array}{ccc}\text{state}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

We have got several new states, which we must add to the table:

$$\begin{array}{ccc}\text{state}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}\\ \{q_0,q_3\}\end{array}$$

…and again we fill in the transitions:

$$\begin{array}{ccc}\text{state}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

We already have the states {q₀, q₁, q₃}, {q₁} and {q₁,q₂} in the table, so we add only the state {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{state}/\text{symbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

We have not added any new state, so the table is complete. Now we just draw the diagram. The states of the deterministic automaton are in the first column, and the transitions for the symbols 0 and 1 are in the other columns. Every state that contains an accept state of the original automaton will also be an accept state in this automaton. That is, every state containing q₃ will be an accept state. The automaton will look like this:

We can show that the automaton really works correctly. Let’s try to accept the string 11001. In the deterministic automaton we follow the path

$$q_0{\to }^1{q}_1,q_2{\to }^1{q}_0,q_3{\to }^0{q}_1{\to }^0{q}_0,q_1,q_3{\to }^1{q}_0,q_1,q_2,q_3$$

and the automaton would accept the string, because the last state {q₀, q₁, q₂, q₃} is an accept state. In the non-deterministic automaton, during a simulation, we would get to the same states: we would start in state q₀ and for the symbol 1 we would get to the states {q₁, q₂}. The next symbol 1 would take us to the states {q₀,q₃}, and so on for the other states. In the end we would find ourselves in all the states {q₀, q₁, q₂, q₃} and the automaton would accept the string.

Sources

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools