Peter Linz Edition 4 Exercise 2.3 Question 7 (Page No. 62)

Question

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?

Answer 1

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.