Theory of Computation

Generalized NFA

1 1 91 42 0 0 (a) Construct a GNFA (call it No) for this machine following rules (a)-(e) above. That is, add a new initial state, a new accept state, and connect all intermediate states to one another with transitions labeled with regular expressions. Your GNFA should have 5 states, and each state (other than the accept state) should have 4 outgoing transitions (any transition labeled with the 0 means it's a transition that didn't exist in the original machine) (b) What is the GNFA that results from ripping state q1 out of No? Call this machine Ni. (c) What is the GNFA that results from ripping state q2 out of N1? Call this machine N2- (d) What is the GNFA that results from ripping state q3 out of N2? Call this machine N3. (e) Using N3, determine a regular expression that describes the language of the original DFA