# Can every non-deterministic finite automate be changed into one with only one acceptance state? [closed]

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?

• It's a standard homework question in many first courses in automata theory. Aug 17 '10 at 14:38
• I am far too old to do homework :p Aug 17 '10 at 14:41
• Fair enough, but I think it's not exactly in the scope of "for theoretical computer scientists and researchers in related fields." Aug 17 '10 at 14:44
• @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. Aug 17 '10 at 15:19
• 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" Aug 17 '10 at 16:09

## 2 Answers

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.

• 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\}$). Feb 7 '11 at 15:51