0
$\begingroup$

I am converting NFA with $\varepsilon$-moves to the NFA without $\varepsilon$-null moves. I understand that if, there is a $\varepsilon$-move between, $q_i$ and $q_j$, then all edges from $q_j$ have to be repeated from $q_i$. And if the $q_j$ is a final state, then $q_i$ will also be a final state.

But, if $q_j$ does not contain any transition, i.e., there are no edges starting from $q_j$, then what has to be done?

$\endgroup$

2 Answers 2

2
$\begingroup$

If $q_j$ is a final state, you already said you would make $q_i$ into a final state. If there's no transitions from $q_j$ to another state in the FSM, then you are staying there forever- either as an accepting state or as a trap state. Either way, staying in $q_i$ is the same as staying in $q_j$ if you can't go anywhere from $q_j$.

$\endgroup$
0
$\begingroup$

Simply put, you do exactly as you said. If $q_j$ does not contain any transition you don't have anything to do so you do nothing more than removing $q_j$ and updating $q_i$ as final if $q_j$ is final.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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