-2
$\begingroup$

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?

$\endgroup$

closed as off topic by András Salamon, Joshua Grochow, Aryabhata, Serge Gaspers, Moritz Aug 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.

  • 2
    $\begingroup$ It's a standard homework question in many first courses in automata theory. $\endgroup$ – Joshua Grochow 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$ – Joshua Grochow 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$ – Joshua Grochow Aug 17 '10 at 16:09
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 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$ – Dominik D. Freydenberger Feb 7 '11 at 15:51

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