# 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?

## closed as off topic by András Salamon, Joshua Grochow, Aryabhata, Serge Gaspers, MoritzAug 17 '10 at 15:05

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

• It's a standard homework question in many first courses in automata theory. – Joshua Grochow Aug 17 '10 at 14:38
• I am far too old to do homework :p – txwikinger 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." – Joshua Grochow 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. – Aryabhata 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" – Joshua Grochow 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.
• 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\}$). – Dominik D. Freydenberger Feb 7 '11 at 15:51