Converting an NFA to an equivalent DFA

Both deterministic and non-deterministic finite machines recognize the set of regular languages. This article explores a step by step approach to convert a NFA to a DFA that accepts the same language.

NFA

Consider the following NFA

State $\downarrow$ Transition $\rightarrow$	$0$	$1$	$\epsilon$
$q_0$ – start	$\{q_1\}$	$\{q_0\}$	$\{q_1, q_2\}$
$q_1$	$\{q_0, q_2\}$	$\emptyset$	$\emptyset$
$q_2$	$\emptyset$	$\{q_2, q_3\}$	$\{q_3\}$
$q_3$ – final	$\emptyset$	$\{q_1, q_4\}$	$\{q_5\}$
$q_4$	$\emptyset$	$\emptyset$	$\emptyset$
$q_5$ – final	$\{q_3, q_5\}$	$\emptyset$	$\emptyset$

This NFA can be converted into an equivalent DFA by following these steps

Compute $\epsilon$ -close set

The $\epsilon$ -close set of a state is defined as the set of all states that can be reached by following $0$ or more $\epsilon$ transitions from that state. The $\epsilon$ -close set of a state will always contain that state. The $\epsilon$ -close set of all the states of the NFA are computed

State $\downarrow$ Transition $\rightarrow$	$0$	$1$	$\epsilon$	$\epsilon$ -close Set $(E)$
$q_0$ – start	$\{q_1\}$	$\{q_0\}$	$\{q_1, q_2\}$	$\{q_0, q_1, q_2, q_3, q_5\}$
$q_1$	$\{q_0, q_2\}$	$\emptyset$	$\emptyset$	$\{q_1\}$
$q_2$	$\emptyset$	$\{q_2, q_3\}$	$\{q_3\}$	$\{q_2, q_3, q_5\}$
$q_3$ – final	$\emptyset$	$\{q_1, q_4\}$	$\{q_5\}$	$\{q_3, q_5\}$
$q_4$	$\emptyset$	$\emptyset$	$\emptyset$	$\{q_4\}$
$q_5$ – final	$\{q_3, q_5\}$	$\emptyset$	$\emptyset$	$\{q_5\}$

Start state of DFA

The start state of DFA will be the epsilon closure of start state of NFA. In this case

$\begin{equation*} \{q_0, q_1, q_2, q_3, q_5\} \end{equation*}$

State $\downarrow$ Transition $\rightarrow$	0	1
$\{q_0, q_1, q_2, q_3, q_5\}$ – start

Transition on $0$ followed by $\epsilon$ -close

Track the transition for each state in the above set and combine the result.

$\begin{align*} q_0 \xrightarrow{\text{0}} & \, \{q_1\} \\ q_1 \xrightarrow{\text{0}} & \, \{q_0, q_2\} \\ q_2 \xrightarrow{\text{0}} & \, \emptyset \\ q_3 \xrightarrow{\text{0}} & \, \emptyset \\ q_5 \xrightarrow{\text{0}} & \, \{q_3, q_5\} \\ \end{align*}$

Thus,

$\begin{equation*} \{q_0, q_1, q_2, q_3, q_5\} \xrightarrow{\text{0}} \{q_0, q_1, q_2, q_3, q_5\} \end{equation*}$

Take the $\epsilon$ -close of this set

$\begin{align*} E(q_0) = & \, \{q_0, q_1, q_2, q_3, q_5\} \\ E(q_1) = & \, \{q_1\} \\ E(q_2) = & \, \{q_2, q_3, q_5\} \\ E(q_3) = & \, \{q_3, q_5\} \\ E(q_5) = & \, \{q_5\} \\ \end{align*}$

Thus, the final state is given by

$\begin{equation*} E(\{q_0, q_1, q_2, q_3, q_5\}) = \{q_0, q_1, q_2, q_3, q_5\} \end{equation*}$

State $\downarrow$ Transition $\rightarrow$	0	1
$\{q_0, q_1, q_2, q_3, q_5\}$ – start	$\{q_0, q_1, q_2, q_3, q_5\}$

Transition on $1$ followed by $\epsilon$ -close

Track the transition for each state in the above set and combine the result.

$\begin{align*} q_0 \xrightarrow{\text{1}} & \, \{q_0\} \\ q_1 \xrightarrow{\text{}} & \, \emptyset \\ q_2 \xrightarrow{\text{1}} & \, \{q_2, q_3\} \\ q_3 \xrightarrow{\text{1}} & \, \{q_1, q_4\} \\ q_5 \xrightarrow{\text{1}} & \, \emptyset \\ \end{align*}$

Thus,

$\begin{equation*} \{q_0, q_1, q_2, q_3, q_5\} \xrightarrow{\text{1}} \{q_0, q_1, q_2, q_3, q_4\} \end{equation*}$

Take the $\epsilon$ -close of this set

$\begin{align*} E(q_0) = & \, \{q_0, q_1, q_2, q_3, q_5\} \\ E(q_1) = & \, \{q_1\} \\ E(q_2) = & \, \{q_2, q_3, q_5\} \\ E(q_3) = & \, \{q_3, q_5\} \\ E(q_4) = & \, \{q_4\} \\ \end{align*}$

Thus, the final state is given by

$\begin{equation*} E(\{q_0, q_1, q_2, q_3, q_4\}) = \{q_0, q_1, q_2, q_3, q_4, q_5\} \end{equation*}$

State $\downarrow$ Transition $\rightarrow$	0	1
$\{q_0, q_1, q_2, q_3, q_5\}$ – start	$\{q_0, q_1, q_2, q_3, q_5\}$	$\{q_0, q_1, q_2, q_3, q_4, q_5\}$

The above process has to be repeated until no more new states are being added and all transitions are accounted for. In this case there is a new state.

$\begin{equation*} \{q_0, q_1, q_2, q_3, q_4, q_5\} \end{equation*}$

Transition on $0$ followed by $\epsilon$ -close

Track the transition for each state in the above set and combine the result.

$\begin{align*} q_0 \xrightarrow{\text{0}} & \, \{q_1\} \\ q_1 \xrightarrow{\text{0}} & \, \{q_0, q_2\} \\ q_2 \xrightarrow{\text{0}} & \, \emptyset \\ q_3 \xrightarrow{\text{0}} & \, \emptyset \\ q_4 \xrightarrow{\text{0}} & \, \emptyset \\ q_5 \xrightarrow{\text{0}} & \, \{q_3, q_5\} \\ \end{align*}$

Thus,

$\begin{equation*} \{q_0, q_1, q_2, q_3, q_4, q_5\} \xrightarrow{\text{0}} \{q_0, q_1, q_2, q_3, q_5\} \end{equation*}$

Take the $\epsilon$ -close of this set

$\begin{align*} E(q_0) = & \, \{q_0, q_1, q_2, q_3, q_5\} \\ E(q_1) = & \, \{q_1\} \\ E(q_2) = & \, \{q_2, q_3, q_5\} \\ E(q_3) = & \, \{q_3, q_5\} \\ E(q_5) = & \, \{q_5\} \\ \end{align*}$

Thus, the final state is given by

$\begin{equation*} E(\{q_0, q_1, q_2, q_3, q_5\}) = \{q_0, q_1, q_2, q_3, q_5\} \end{equation*}$

State $\downarrow$ Transition $\rightarrow$	0	1
$\{q_0, q_1, q_2, q_3, q_5\}$ – start	$\{q_0, q_1, q_2, q_3, q_5\}$	$\{q_0, q_1, q_2, q_3, q_4, q_5\}$
$\{q_0, q_1, q_2, q_3, q_4, q_5\}$	$\{q_0, q_1, q_2, q_3, q_5\}$

Transition on $1$ followed by $\epsilon$ -close

Track the transition for each state in the above set and combine the result.

$\begin{align*} q_0 \xrightarrow{\text{1}} & \, \{q_0\} \\ q_1 \xrightarrow{\text{}} & \, \emptyset \\ q_2 \xrightarrow{\text{1}} & \, \{q_2, q_3\} \\ q_3 \xrightarrow{\text{1}} & \, \{q_1, q_4\} \\ q_4 \xrightarrow{\text{1}} & \, \emptyset \\ q_5 \xrightarrow{\text{1}} & \, \emptyset \\ \end{align*}$

Thus,

$\begin{equation*} \{q_0, q_1, q_2, q_3, q_4, q_5\} \xrightarrow{\text{1}} \{q_0, q_1, q_2, q_3, q_4\} \end{equation*}$

Take the $\epsilon$ -close of this set

$\begin{align*} E(q_0) = & \, \{q_0, q_1, q_2, q_3, q_5\} \\ E(q_1) = & \, \{q_1\} \\ E(q_2) = & \, \{q_2, q_3, q_5\} \\ E(q_3) = & \, \{q_3, q_5\} \\ E(q_4) = & \, \{q_4\} \\ \end{align*}$

Thus, the final state is given by

$\begin{equation*} E(\{q_0, q_1, q_2, q_3, q_4\}) = \{q_0, q_1, q_2, q_3, q_4, q_5\} \end{equation*}$

State $\downarrow$ Transition $\rightarrow$	0	1
$\{q_0, q_1, q_2, q_3, q_5\}$ – start	$\{q_0, q_1, q_2, q_3, q_5\}$	$\{q_0, q_1, q_2, q_3, q_4, q_5\}$
$\{q_0, q_1, q_2, q_3, q_4, q_5\}$	$\{q_0, q_1, q_2, q_3, q_5\}$	$\{q_0, q_1, q_2, q_3, q_4, q_5\}$

No new states are added an all transitions are accounted for.

Final states

If a state in the DFA has any occurrence of a final state in the original NFA, it is marked final. In the above case, $q_3$ and $q_5$ are final in the original NFA. This makes both the states in the DFA final.

State $\downarrow$ Transition $\rightarrow$	0	1
$\{q_0, q_1, q_2, q_3, q_5\}$ – start, final	$\{q_0, q_1, q_2, q_3, q_5\}$	$\{q_0, q_1, q_2, q_3, q_4, q_5\}$
$\{q_0, q_1, q_2, q_3, q_4, q_5\}$ – final	$\{q_0, q_1, q_2, q_3, q_5\}$	$\{q_0, q_1, q_2, q_3, q_4, q_5\}$

State Diagram

Here is an equivalent transition state diagram

Rendered by QuickLaTeX.com

The Beard Sage

Converting an NFA to an equivalent DFA

NFA

Compute $\epsilon$ -close set

Start state of DFA

Transition on $0$ followed by $\epsilon$ -close

Transition on $1$ followed by $\epsilon$ -close

Transition on $0$ followed by $\epsilon$ -close

Transition on $1$ followed by $\epsilon$ -close

Final states

State Diagram

Leave a Reply Cancel reply

NFA

Compute -close set

Start state of DFA

Transition on followed by -close

Transition on followed by -close

Transition on followed by -close

Transition on followed by -close

Final states

State Diagram

Leave a Reply Cancel reply

Compute $\epsilon$ -close set

Transition on $0$ followed by $\epsilon$ -close

Transition on $1$ followed by $\epsilon$ -close

Transition on $0$ followed by $\epsilon$ -close

Transition on $1$ followed by $\epsilon$ -close