Describe in words how we can take any NFA N QsF and get an

Describe in words how we can take any NFA N = (Q,,,s,F) and get an NFA N = (Q,,,s,F) such that L(N) = L(N) but F consists of a single state f. Essentially make the NFA so that it has just one accepting state

Solution

we have to N to N\' in such a way that , L(N\') = L(N) and , N\' has only one accepting state,

1)first take N, now have to create a new state qf .

2)now N, create epsilon transitions from all final states in N to new state qf..

3)make all final states in N to non final sates and make this new state as final state.

now the resulting machine is N\' which has one accepting state, which acts like same as N

and L(N\') = L(N).