By Equation (3.1), the language accepted then is L(r), where
10. (b) First, we have to modify the nfa so that it satisfies the conditions
imposed by the construction in Theorem 3.2, one of which is
. This is
easily done.
Then remove state 3.
Next, remove state 4.
The regular expression then is r = (ab + (aa + b)(ba) * bb * ) * .
16. (a) This is a hard problem until you see the trick. Start with a dfa with