<p>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.</p>

<p>Proof is by construction.</p>

CC BY-SA 2.5
2010-08-17T14:20:44.497Z
2010-08-17T14:20:44.497Z
Dave Clarke
<p>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.</p>

CC BY-SA 2.5
2011-02-07T15:51:59.830Z
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
CC BY-SA 2.5
2010-08-17T14:42:19.533Z
2010-08-17T14:42:19.533Z
Alexandre Passos
<p>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?</p>

CC BY-SA 2.5
2010-08-17T14:38:26.997Z
It's a standard homework question in many first courses in automata theory.
Joshua Grochow
CC BY-SA 2.5
2010-08-17T14:41:12.983Z
I am far too old to do homework :p
txwikinger
CC BY-SA 2.5
2010-08-17T14:44:34.253Z
Fair enough, but I think it's not exactly in the scope of "for theoretical computer scientists and researchers in related fields."
Joshua Grochow
CC BY-SA 2.5
2010-08-17T15:03:59.403Z
We (or at least I) don't intend to be hostile.  But I think this site is aimed more at the advanced undergrad / graduate student level and above (unlike, say, StackOverflow).  This meta-discussion fleshes this out in more detail, and parts of it should probably be added to the FAQ to clarify: http://meta.cstheory.stackexchange.com/questions/17/scope-of-questions
Joshua Grochow
CC BY-SA 2.5
2010-08-17T15:19:47.237Z
@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
CC BY-SA 2.5
2010-08-17T15:22:21.823Z
Well. According to the majority of comments, it seems to me my questions are within the scope. Maybe the setting of the scope should have happened in the proposal stage not now!!
txwikinger
CC BY-SA 2.5
2010-08-17T16:09:08.060Z
The scope was laid out in the very first proposal of the site by Anand Kulkarni (http://area51.stackexchange.com/proposals/8766?phase=definition): "dedicated to research-level questions in theoretical computer science"
Joshua Grochow
<fl.formal-languages><automata-theory>
Can every non-deterministic finite automate be changed into one with only one acceptance state?
txwikinger
# Can every non-deterministic finite automate be changed into one with only one acceptance state?

(Asked by: username_0 on 2010-08-17)

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?

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: It's a standard homework question in many first courses in automata theory.  
> **username_0**: I am far too old to do homework :p  
> **username_1**: Fair enough, but I think it's not exactly in the scope of "for theoretical computer scientists and researchers in related fields."  
> **username_1**: We (or at least I) don't intend to be hostile.  But I think this site is aimed more at the advanced undergrad / graduate student level and above (unlike, say, StackOverflow).  This meta-discussion fleshes this out in more detail, and parts of it should probably be added to the FAQ to clarify: http://meta.cstheory.stackexchange.com/questions/17/scope-of-questions  
> **username_2**: @username_0: 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.  
> **username_0**: Well. According to the majority of comments, it seems to me my questions are within the scope. Maybe the setting of the scope should have happened in the proposal stage not now!!  
> **username_1**: The scope was laid out in the very first proposal of the site by Anand Kulkarni (http://area51.stackexchange.com/proposals/8766?phase=definition): "dedicated to research-level questions in theoretical computer science"  

---

## 2 answers

### Answer by username_3 on 2010-08-17. Score: 5 | Accepted answer

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.


---

### Answer by username_4 on 2010-08-17. Score: 3

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.

> **Comments:**
> **username_5**: 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\}$).  

---

