In the 3rd edition of Sipser's Introduction to the Theory of Computation (example 1.56, p.68), there is a step-by-step procedure to transform (ab U a)* into a NFA.And then the text ends with: In this example, the procedure gives an NFA with eight states, but the smallest equivalent NFA has only two states. Can you find it?Nope. I can't.After a good deal of head scratching, I've convinced myself that it's not doable. But being a novice, I'm probably wrong.Can anyone help? Thanks!
Regular expression (ab U a)* to NFA with two states (Sipser)?
finite automata;regular expressions