How can an arbitrary non-deterministic finite automate be converted into one with only one accept stage? If so, what is the proof that this can always be done?

  • 2
    $\begingroup$ It's a standard homework question in many first courses in automata theory. $\endgroup$ Aug 17 '10 at 14:38
  • $\begingroup$ I am far too old to do homework :p $\endgroup$
    – txwikinger
    Aug 17 '10 at 14:41
  • $\begingroup$ Fair enough, but I think it's not exactly in the scope of "for theoretical computer scientists and researchers in related fields." $\endgroup$ Aug 17 '10 at 14:44
  • 2
    $\begingroup$ @txwikinger: There is no witchhunt against you. The close decisions are being made solely on the basis of what the question is and whether it fits the scope of this site (see Joshua's comment). For instance this question would be more suitable for stackoverflow. FWIW, I did not even look at the username before casting the close vote. $\endgroup$
    – Aryabhata
    Aug 17 '10 at 15:19
  • 3
    $\begingroup$ The scope was laid out in the very first proposal of the site by Anand Kulkarni (area51.stackexchange.com/proposals/8766?phase=definition): "dedicated to research-level questions in theoretical computer science" $\endgroup$ Aug 17 '10 at 16:09

If you allow $\epsilon$ transitions, then the answer is yes. Simply introduce a new accepting state and have epsilon transitions from the original accepting states to it.

Proof is by construction.


Even if you don't allow epsilon transitions, yes. Create a new state and for each edge that would lead to a final state in the original NFA create another nondeterministic one that points to this new state.

  • 1
    $\begingroup$ Although this question has long been closed, I need to point out that this approach fails (in general) if the language contains the empty word (e.g, for the language $\{\epsilon,a\}$). $\endgroup$ Feb 7 '11 at 15:51

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