0
$\begingroup$

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 : 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):

First picture

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

Second Picture

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\}$.

third picture

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

Fourth Picture

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

Fifth Picture

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

States Table

My intuitive approach did actually the following:

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – Nathaniel Mar 10 at 19:59
  • $\begingroup$ sorry. it was a typo $\endgroup$ – Abhishek Ghosh Mar 10 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.