Converting NKA to DKA

We show how to convert a non-deterministic automaton into a deterministic automaton, proving that the computational power of non-deterministic automata and deterministic automata is equivalent.

The basic idea

Consider a nondeterministic automaton $\left<Q_N, \Sigma_N, \delta_N, q_0, F_N\right>$ without epsilon transitions. We construct a deterministic automaton $\left<Q_D, \Sigma_D, \delta_D, p_0, F_D\right>$ such that

• Q_D ⊆ 2^Q_N
• $\Sigma_D = \Sigma_N$
• p₀ = {q₀}
• F_D = {Q ∈ Q_D,|,Q ∩ F_N ≠ ∅}

We define the transition function δ_D as follows:

$$ \forall Q \in Q_D, a\in\Sigma_D: \delta_D(Q, a) = \bigcup_{q\in Q} \delta_N(q, a) $$

What does it mean? A nondeterministic automaton can be in multiple states at the same time, so for example we can get to a situation where our nondeterministic automaton is in the states {q₀, q₁}. By reading another symbol, for example 1, we can get to the set of states {q₀, q₂, q₃}. In the deterministic version of the same automaton, this manifests itself by creating two states, naming them {q₀, q₁} and {q₀, q₂, q₃}, and introducing a transition between them for the symbol 1. Formally, this will get us from one state to the other, but thanks to the naming we will know that in the nondeterministic automaton we would be in two or three states, respectively.

Example

Consider this nondeterministic automaton:

To construct a deterministic automaton, we first need to construct a new transition function. To do this, we need a table in which to write down all the transitions. At the beginning, the table looks like this:

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\} \end{array} $$

In the left column we will have all the states of the deterministic automaton at the end of the algorithm. The completed table will then determine the transition function. Now we will write in the table what states we get to if we are in the states {q₀} and the input symbols are 0 and 1.

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \end{array} $$

From the state q₀, the transition for symbol 0 leads only to the state q₁, while for symbol 1 it leads to the states q₁ and q₂. Now we add two new states to the table: {q₁} and {q₁, q₂}. Why? The moment we add a set of states to the table that we don't already have in the left column, we add that set of states there.

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}\\ \left\{q_1, q_2\right\} \end{array} $$

and fill it in again. For the state {q₁, q₂}, we must not forget to check both states, i.e. where we get from the state q₁ with where we get from the state q₂.

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \end{array} $$

We've got some new states to add to the table:

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}\\ \left\{q_0,q_3\right\}\\ \end{array} $$

again add transitions:

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \left\{q_0,q_3\right\}&\left\{q_1\right\}&\left\{q_1,q_2\right\}\\ \end{array} $$

The states {q₀, q₁, q₃}, {q₁} and {q₁,q₂} are already there, so we'll just add the state {q₀,q₁,q₂,q₃}.

$$ \begin{array}{c|c|c} \mbox{ Status }/\mbox{ Symbol }&0&1\\\hline \left\{q_0\right\}&\left\{q_1\right\}&\left\{q_1, q_2\right\}\\ \left\{q_1\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_1, q_2\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_3\right\}\\ \left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \left\{q_0,q_3\right\}&\left\{q_1\right\}&\left\{q_1,q_2\right\}\\ \left\{q_0,q_1,q_2,q_3\right\}&\left\{q_0, q_1, q_3\right\}&\left\{q_0,q_1,q_2,q_3\right\}\\ \end{array} $$

We haven't added any new state, so the table is complete. Now we just build the diagram. The states of the deterministic automaton are in the first column, the transitions for symbols 0 and 1 are in the other columns. Any state that contains an end state from the original automaton will be an end state in this automaton. That is, any state containing q₃ will be an end state. The automaton will look like this:

We can show that the automaton works really well. If we try to accept the word 11001. In a deterministic automaton, we'll take the path

$$ q_0 \rightarrow^1 q_1, q_2 \rightarrow^1 q_0, q_3 \rightarrow^0 q_1 \rightarrow^0 q_0, q_1, q_3 \rightarrow^1 q_0, q_1, q_2, q_3 $$

and the automaton would accept the word because the last state {q₀, q₁, q₂, q₃} is a terminal state. In a non-deterministic automaton, we would get to the same states during the simulation, i.e. we would start in the state q₀ and for symbol 1 we would get to the states {q₁, q₂}. The next symbol 1 would get us to the states {q₀,q₃} etc. for the next states. Eventually we would be in all the states {q₀, q₁, q₂, q₃} and the automaton would accept the word.

Sources

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