2
$\begingroup$

I am well-aware of the result showing that one can convert an epsilon-NFA (that is, an NFA with epsilon transitions) $A$ to an NFA without epsilon transitions $A'$, where $L(A) = L(A')$.

Is there a similar result comparing the state complexities of $A$ and $A'$? That is, if one has an epsilon-NFA $A$ with $n$ states, is it true that there exists an equivalent NFA without epsilon transitions $A'$ that also has $n$ states?

$\endgroup$
2
$\begingroup$

Yes, we can transform an epsilon NFA into a NFA by keeping the same state set, basically adding new edges. If there is an $\varepsilon$ path from state $p$ to state $q$, and an edge from state $q$ to state $r$, then add an $a$ edge from $p$ to $r$. Also, if from state $p$ we can reach a final state then state $p$ can be made accepting. After these two steps we can remove the original $\varepsilon$ edges without changing the language.

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Of course, it never occurred to me that you can simply keep the states instead of removing "useless" states (like state 8 in your figure). Thank you! $\endgroup$ – user121787 May 28 at 19:21

Your Answer

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

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