in Theory of Computation
1,764 views
0 votes
0 votes
Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with only
one final state. Can we make a similar claim for dfa’s?
in Theory of Computation
1.8k views

1 Answer

2 votes
2 votes
Every NFA with more than one final state can be converted into a NFA with a single final state.Add a new state to the NFA and introduce epsilon transitions from every old final state to the new state.Make the new state as the final state and all the old final states as non final states.This new NFA accepts the same language as the old NFA.

Related questions