9. No. The string abc has three different symbols and there is no way this can be
accepted with fewer than three states.
16. This is the kind of problem in which you just have to try different ways.
Probably most of your tries will not work. Here is one that does.
18. Introduce a single starting state p 0 . Then add a transition
Next, remove starting state status from Q 0 . It is straightforward to see that
the new nfa is equivalent to the original one.
21. Introduce a nonaccepting trap state and make all undefined transitions to
this new state. Solution:
accepted with fewer than three states.
16. This is the kind of problem in which you just have to try different ways.
Probably most of your tries will not work. Here is one that does.
18. Introduce a single starting state p 0 . Then add a transition
Next, remove starting state status from Q 0 . It is straightforward to see that
the new nfa is equivalent to the original one.
21. Introduce a nonaccepting trap state and make all undefined transitions to
this new state. Solution: