1
$\begingroup$

While Learning about removing null moves from NFA , I came across a thought....

To Remove Epsilon moves we follow following steps :

  1. Find Closure of all states which have null moves
  2. Mark these states which have null moves
  3. Make a revised transition table without epsilon column and Find all possible transition for those marked states by using their Closures.
  4. you will get nfa without null moves/epsilon moves

Where is the issue : Actually, Doubt arises when you think of an nfa like this :

If we try to remove epsilon moves out of it...

enter image description here

Initial transition Table : enter image description here

Now finding closure for q0, q1 and q3.

Which is CL(q0) = {q0,q1,q2} CL(q1) = {q1,q2} CL(q3) = {q2,q3} We find a transition table after following above steps which is : enter image description here

The question gets quite tricky...

because now this nfa has q1,q2 where there is no way to reach them..

So What do you think we will remove q1 and q2 as they are unreachable or we will draw a nfa with them...

$\endgroup$
  • 1
    $\begingroup$ You didn't calculate the closure, you just gave (some - you missed a couple) of the transitions that you have to add. The original non-epsilon transitions aren't just ignored. $\endgroup$ – G. Bach Oct 19 '13 at 22:04
  • $\begingroup$ @G.Bach I have edited the question a bit but still there is no error in question from my part... Have a look again... $\endgroup$ – Shubham Oct 20 '13 at 8:04
6
$\begingroup$

In your construction you correctly computed the closures of the original states and then made the $a$- and $b$-transitions, but you omitted step (3) of the algorithm: compute the closures of the results again. For example, from $q_0$ on input of $a$ the first step is $$ q_0\stackrel{CL}{\longrightarrow} \{q_0, q_1, q_2\} $$ then, on seeing an $a$ we make the transitions, as you did: $$ \{q_0, q_1, q_2\}\stackrel{a}{\longrightarrow} \{\delta(q_0, a), \delta(q_1, a), \delta(q_2, a)\}=\{q_3, q_4\} $$ then (here's the step you omitted), you take the closure again: $$ \{q_3, q_4\}\stackrel{CL}{\longrightarrow} \{q_2, q_3, q_4\} $$ and thus you'll have the new transition $\delta'(q_0, a) = \{q_2, q_3, q_4\}$.

If you do this for all the state-symbol pairs, you'll find that the transitions of your new NFA are $$\begin{array}{c|cc} & a & b\\ \hline q_0 & \{q_2, q_3, q_4\} & \{q_2, q_3\} \\ q_1 & \{q_2, q_3, q_4\} & \varnothing \\ q_2 & \{q_4\} & \varnothing \\ q_3 & \{q_4\} & \{q_5\} \\ q_4 & \{q_5\} & \{q_2, q_3\} \\ q_5 & \varnothing & \varnothing \\ \end{array}$$ Since $q_1$ is an unreachable state, it can be eliminated without changing the langauge of the resulting NFA.

$\endgroup$
2
$\begingroup$

Hint. There is a path $q_0 \xrightarrow{\lambda} q_1 \xrightarrow{a} q_3 \xrightarrow{\lambda} q_2$. So you should have a transition $q_0 \xrightarrow{a} q_2$ in your revised transition table. [Forget about this].

Update. Sorry for the confusion, but actually I am not sure to understand your algorithm, but here is one. Let us call null path a path labeled by the empty word. For each state $p$, let $$ R(p) = \{ q \mid \text{there is a null path from $p$ to $q$}\} $$ Now take as set of initial states the set $$ \bigcup_{\text{p initial}} R(p) $$ and as set of final states the set $$ \{p \mid R(p) \cap F \not= \emptyset \} $$ In your case $q_0, q_1, q_2$ will become initial states. Then for each transition $p \xrightarrow{a} q$, add the transitions $p \xrightarrow{a} r$ for each $r \in R(q)$. Finally remove all the empty transitions. In your case, you will only need to add the transitions $q_1 \xrightarrow{a} q_2$ and $q_0 \xrightarrow{b} q_2$. This is simpler.

$\endgroup$
  • $\begingroup$ i am more concerned towards solving it fundamentally... Its quite clear that there must be a transition from q0 to q2 but How ?? Is there any theoretical way to say ??? $\endgroup$ – Shubham Oct 20 '13 at 17:22
  • $\begingroup$ Still Not able to understand it properly... $\endgroup$ – Shubham Nov 15 '13 at 12:11
0
$\begingroup$

You should change the start state to $CL(q_0)$ where $q_0$ is the start state. This makes $q_1,q_2$ re-appear in the transition table. Why should you do this? Because, if the start state has null transitions and if you want to remove $\lambda$-transitions, then you have to make these states start states too.

$\endgroup$
0
$\begingroup$

You may try removing $\epsilon$-moves in your NFA from vertex $v_1$ to vertex $v_2$ using following steps :

  1. Find all the edges starting from $v_2$.
  2. Duplicate all these edges starting from $v_1$, without changing the edge labels.
  3. If $v_1$ is an initial state, make $v_2$ also an initial state.
  4. If $v_2$ is a final state, make $v_1$ also a final state.

If you still want to do it in your way, I will read your procedure.

$\endgroup$

protected by Community Aug 10 '17 at 7:00

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.