Removing Null moves from NFA

Question

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...

Initial transition Table :

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 :

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...

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.