1
$\begingroup$

Given an NFA with more than one initial or final state, it is possible to convert it to another NFA with only one initial or final state by using epsilon transitions. To remove the epsilon transitions, we may need to add final or initial states, depending on the method used (backwards removal vs forward removal).

Is there an efficient way to convert an NFA to an equivalent NFA with only one initial and final state, and no epsilon transitions? Converting it to a DFA can be exponential, so is there a better way to achieve this?

$\endgroup$

1 Answer 1

2
$\begingroup$

Yes, in fact we can. Provided the original automaton does not accept the empty string $\varepsilon$.

The construction is as follows. We start with the usual NFA with a single initial state (and no $\varepsilon$-edges). Add a new final state $f$. Whenever there is a transition $(s,a,t)$ into a final state $t$ we add a copy $(s,a,f)$ into new final $f$. Now demote every original final state into ordinary.

Voila, the new automaton accepts the original language except for $\varepsilon$, but has only a single final state.

$\endgroup$
1
  • $\begingroup$ Nice idea, it's the type of thing that when I read it, I ask myself, “Why didn't I think of that?” $\endgroup$
    – ricardorr
    Feb 14, 2023 at 16:37

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.