# Co-relating the direct algo for $\epsilon-NFA$ to $DFA$ with the chain : $\epsilon-NFA \rightarrow NFA \rightarrow DFA$

I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following algorithm to convert an $$\epsilon\text{-NFA}$$ to $$\text{DFA}$$

1. initially, ϵ-closure(s0) is the only state in Dstates and it is unmarked;
2. while there is an unmarked state T in Dstates do begin
3.    mark T;
4.    for each input symbol a do begin
5.       U := ϵ-closure(move(T, a));
6.       if U is not in Dstates then
7.           add U as an unmarked state to Dstates;
8.       Dtran[T, a]:= U
9.    end
10. end


where

$$\begin{array}{*{20}{|c}} \hline {{\text{OPERATION}}} & {{\text{DESCRIPTION}}}\\ \epsilon-closure(s) & \text{Set of NFA states reachable from NFA states s on \epsilon -} \\ {} & \text{transitions alone.}\\ \epsilon-closure(T) & \text{Set of NFA states reachable from some NFA state s in T} \\ {} & \text{on \epsilon - transitions alone.}\\ move(T,a) & \text{Set of NFA states to which there is a transition on input} \\ {} & \text{symbol a from some NFA state s in T.}\\ \hline \end{array}$$

The authors then say: We construct $$Dstates$$, the set of states of $$D$$, and $$Dtran$$, the transition table for $$D$$, in the following manner. Each state of $$D$$ corresponds to a set of $$NFA$$ states that $$N$$ could be in after reading some sequence of input symbols including all possible $$\epsilon$$-transitions before or after symbols are read. The start state of $$D$$ is $$\epsilon-closure(s_0)$$. $$^\dagger$$ States and transitions are added to $$D$$ using the algorithm above. A state of $$D$$ is an accepting state if it is a set of $$NFA$$ states containing at least one accepting state of $$N$$. $$^{\dagger\dagger}$$

The authors then apply the above algorithm on the example :

The application is straight forward as far as the use of the above algorithm is concerned (so not including it here). By till now while solving problems of these types I followed the following strategy (the strategy followed in the text : Introduction to Automata Theory, Languages, and Computation by Hopcroft et. al) :

STEP 1: $$\epsilon-NFA$$ to $$NFA$$

To do this for each state $$t$$ in the $$NFA$$ we first find $$\epsilon-closure(t)$$ and store it in $$E$$. Then for each symbol $$a$$ in $$\Sigma$$, we find the $$move(E,a)$$ and store it in $$F$$ and find $$\epsilon-closure(F)$$ and place it at the table location $$TABLE[t][a]$$

$$\begin{array}{c|ccc} states & a & b \\ \hline \rightarrow 0 & \{1,2,3,4,6,7,8\} & \{1,2,4,5,6,7\} \\ 1 & \{1,2,3,4,6,7\} & \{1,2,4,5,6,7\} \\ 2 & \{1,2,3,4,6,7\} & \phi \\ 3 & \{1,2,3,4,6,7,8\} & \{1,2,4,5,6,7\} \\ 4 & \phi & \{1,2,4,5,6,7\} \\ 5 & \{1,2,3,4,6,7,8\} & \{1,2,4,5,6,7\} \\ 6 & \{1,2,3,4,6,7,8\} & \{1,2,4,5,6,7\} \\ 7 & \{8\} & \phi \\ 8 & \phi & \{9\} \\ 9 & \phi & \{10\} \\ *10 & \phi & \phi \\ \end{array}$$

In this above table construction, the start state of the $$\epsilon-NFA$$ $$0$$ is still the start state of the $$NFA$$ constructed in the table. $$^\ddagger$$

And aditional final states in the above NFA are all those those states in the $$\epsilon-NFA$$, which can reach the final state in the $$\epsilon-NFA$$ using only $$\epsilon$$ moves. $$^{\ddagger\ddagger}$$

STEP 2: Using subset construction we convert the above table for NFA to that a DFA as shown:

$$\begin{array}{c|ccc} states & a & b \\ \hline \rightarrow [0] & [1,2,3,4,6,7,8] & [1,2,4,5,6,7] \\ [1,2,3,4,6,7,8] & [1,2,3,4,6,7,8] & [1,2,4,5,6,7,9] \\ [1,2,4,5,6,7] & [1,2,3,4,6,7,8] & [1,2,4,5,6,7] \\ [1,2,4,5,6,7,9] & [1,2,3,4,6,7,8] & [1,2,4,5,6,7,10] \\ *[1,2,4,5,6,7,10] & [1,2,3,4,6,7,8] & [1,2,4,5,6,7] \\ \end{array}$$

The final state in the $$DFA$$ is all those sets having at least one final state of the NFA from which it is formed.

This DFA which I have obtained happens to equivalent to the DFA obtained as output from the algorithm in the text. [ This could have been minimized but not going into it as the algorithm under discussion does not do so]

I cannot get the intuition how these two algorithms are equivalent.

1. In $$\ddagger$$ we can start with the actual start state of the $$\epsilon-NFA$$ but in $$\dagger$$ we are assuming $$\epsilon-closure(s_0)$$ as the state of the DFA being produced.

2. The equivalence between $${\dagger\dagger}$$ and $${\ddagger\ddagger}$$ ?

3. Moreover in the line 3 of the algorithm I intuitively felt that we could have written :

  U := ϵ-closure(move(ϵ-closure(T), a));


Just as we are doing in step 1 of my work out.

PostScript

I thought of an intuition as to how the algorithm is working. Let us consider the string $$abb$$ and give it to the $$\epsilon- NFA$$ then we trace out the steps.

Step (i):

Though $$0$$ is the start state, but from $$0$$ (using $$\epsilon$$ moves) we can parallelly be at the states $$\{0,1,2,4,7\}$$

From the states $$\{0,1,2,4,7\}$$ where we can be present parallelly on scanning the symbol $$a$$ we are at states $$\{3,8\}$$.

Step (ii):

Now if we are at states $$\{3,8\}$$ parallelly, using $$\epsilon$$ moves, we can parallelly be in states $$\{1,2,3,4,6,7,8\}$$.

Now if we scan the symbol $$b$$ then we shall reach the states : $$\{5,9\}$$ in parallel.

Now from states $$\{5,9\}$$ we can reach states $$\{1,2,4,5,6,7,9\}$$ in parallel using $$\epsilon$$ productions only.

Finally on scanning the last symbol $$b$$ we reach states $$\{5,10\}$$ and using $$\epsilon$$ production we can be parallelly at the states $$\{1,2,4,5,6,7,10\}$$. Since we have reached the final state $$10$$ we say $$\text{YES}$$.

The way we found the membership of $$abb$$, I feel is quite related to the way the algorithm in text produces the output.

Output from the algorithm

My intuitive approach did actually the following:

$$A \xrightarrow{\text{a}} B \xrightarrow{\text{b}} D \xrightarrow{\text{b}} E$$

• The line U := ϵ-closure(move(T, ϵ-closure(a) )); does not really make sense, since a is an input symbol, and not a state of the automaton. If you meant ϵ-closure(move(ϵ-closure(T), a));, it is not necessary, since T is already a closure given the algorithm. – Nathaniel Mar 10 at 19:59
• sorry. it was a typo – Abhishek Ghosh Mar 10 at 20:13