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?

Question

Miranda Aguirre

Computers & Technology

16 September, 18:50

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?

+2

Answers (1)

Know the Answer?

Stephen Nichols · Answer 1

Answer and Explanation:

Each NFA can be changed over into a proportional NFA that has a solitary accept state.

Basically add another last state to the first automaton, include epsilon advances from each old last state to the new last state, and change each old last state into a regular state.

This new NFA acknowledges the very same language as the first NFA.

We cannot make similar guarantee for dfa's.