Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with only one final state. Can we m

Question

almond37 [142]

3 years ago

8

Prove that for every nfa with an arbitrary number of final states there is an equivalent nfa with only one final state. Can we m

ake a similar claim for dfa’s?

Computers and Technology

1 answer:

Vlad1618 [11] · Answer 1 · 2022-02-09T20:29:36+03:00

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.