# Converting NFA to DFA by Complete and Lazy Subset Construction

###### Question

Given a transition table construct the NFA and using subset construction generate the DFA.

Task is to convert the NFA $N = ( Q_N, \sum, \delta_N, q_0, F_N )$ to DFA $D = ( Q_D, \sum, \delta_D, \{ q_0 \}, F_D )$ such that $L(D) = L(N)$. Both DFA and the NFA will accept the same language.

###### NFA Tuples:
$N = ( Q_N, \sum, \delta_N, q_0, F_N ) \\$

$= ( \{ p,q,r,s \}, \{ 0,1 \}, \delta, p, \{ s \} )$


###### Power set of NFA states $Q_N$:

Since the NFA has 4 states its power set will contain $2^4 = 16$ states. Omitting the empty set $\emptyset$ there will be $2^4 - 1 = 15$ states.

If $Q_N$ is set of states of NFA the $P(Q_N)$ which is the power set of $Q_N$ are possible states of the DFA $Q_D$.

Each sets in the power sets can be named something else to make it easy to understand. Each of the sets in the power set represent a state in the DFA.

$Q_N = \{ p,q,r,s \}$

$P(Q_N) = \{ \{ \},\{ p \},\{ q \},\{ r \},\{ s \}, \{ p,q \}, \{ p,r \}, \{ p,s \}, \{ q,r \}, \{ q,s \}, \{ r,s \},$
$\{ p,q,r \}, \{ p,q,s \}, \{ p,r,s \}, \{ q,r,s \}, \{ p,q,r,s \} \}$


###### Subset Construction:

The NFA can be converted to DFA using complete subset construction or by lazy evaluation of states. I will show both methods.

$F_D$ is all the set of N states that includes at least one accepting state. Final state of the DFA $F_D$ is set of subset of NFA states $Q_N$ such that $S \cap F_N \ne \emptyset$.

For each set $S \subseteq Q_N$ and for each input symbol a in $\sum$,

$\delta_D (S,a) = \bigcup\limits_{\text{p in S}} \delta_N (p,a)$

This above is the formula to fill subset table. Although when filling by hand it is clearly visible.

This will be the transition table for the DFA. Although not all the $2^N$ states will be there. First thing to do is where ever there is the final state of the NFA mark that with star and p will also be start state for the DFA.

The table can be filled using shortcut by first copying the NFA table for the first four states since they are same as the NFA. Next for each element in the set for an copy from its corresponding row and union all the sets.

The same thing is done in the formula above. To get the transition from a state ( each of the sets in the power set ) for an input symbol which replaces a it produces the output. Right side of the formula takes each element from the set and for the input symbol it produces an item and unions them.

For example,

$\delta_D ( \{ p,s \}, 0) = \delta_N (p,0) \cup \delta_N (s,0)$
$= \{ p,q \} \cup \{ s \}$
$= \{ p,q,s \}$


Another example,

$\delta_D ( \{ p,q,r,s \}, 1) = \delta_D ( \{ p,q,r \} ,1) \cup \delta_N (s,1)$
$= \{ p,r \} \cup \{ s \}$
$= \{ p,r,s \}$


Here, I just used the pre-computed value in the subset table. Since {p,q,r} is computed beforehand so I get the value from the table.

Each sets can be renamed to something else. Here I name sets from 1 to 15. Although it becomes a little bit confusing with the input symbol but it will take a lot of work to change things.

After renaming the states in the subset table,

###### Reachable States:

Only reachable states of power set of $Q_N$ or the reachable states of the DFA $Q_D$.

###### Lazy Evaluation / Subset Construction:

The above method is very slow and time consuming. Since all $2^N$ are not reachable for every DFA so this method will speed up the process by avoiding extra work.

Start with the start state and only construct the states the are reachable from starting state and similarly follow those states.

###### Generated DFA using Lazy Subset Construction:

As it is visible both DFA are same.