# Regular expression (ab U a)* to NFA with two states (Sipser)?

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!

-
@Theolodis The alphabet is, implicitly, $\{a,b\}$ even if the alphabet is bigger, the NFA doesn't need any more states or transitions, because the accepted language contains only $a$s and $b$s. –  David Richerby Jul 21 at 14:03
There is a standard construction from regular expressions to automata, usually employed to prove the equivalence of both concepts. Did you try that? –  Raphael Jul 21 at 15:51
@Raphael He did: the standard construction from Slipres-book gives eight states (rather than two). –  Hendrik Jan Jul 21 at 19:41
@HendrikJan: The next question then is: do you know how to make a finite automaton smaller? (cc @HendrikJan; the point is, the OP probably saw everything in class but has not yet connected the points.) –  Raphael Jul 21 at 20:18
For some reason, I kept seeing + instead of *. So the correct answer looked wrong because it accepts the empty string which, in my mind, wasn't part of the language. Talk about tunnel vision. Thank you so much, guys. You've been very helpful. –  Garp Jul 22 at 4:31

Mouse-over the yellow box to see an NFA that accepts the language.

-
You can correct the asker's spelling by editing the question; no need to comment on it in an answer. –  David Richerby Jul 21 at 14:00
And why would that be correct? What should Garp do about the next fish? –  Raphael Jul 21 at 15:51

One way to approach this problem is to use Chang's method. This method produces NFAs with the following properties:

• The number of states is equal to the number of terminal symbols in the input regular expression.
• There are no lambda/epsilon transitions.

It's also simple enough that you can do it by hand for modest regular expressions.

Now you may have noticed that there are in fact three terminal symbols in your regular expression $(ab \cup a)^*$; two $a$'s and a $b$. However, if you allow the "optional" operator $?$, you can easily get it down to two:

$$(ab?)^*$$

Chang's method is a great substitute for Thompson's method (which is what you probably know) most of the time. About the only thing it can't handle cleanly is the lex trailing context operator (which is a hack anyway).

C.H. Chang, From Regular Expressions to DFAs using Compressed NFAs (1992). http://ftp.cs.nyu.edu/web/Research/Theses/chang_chia-hsiang.pdf

-
Cool, I'd never heard of that method! –  Raphael Jul 22 at 7:06

This question is a special instance of the following question. Given a finite sequence of words $u_1, ..., u_k$, find an NFA for the language $L = \{u_1, ..., u_k\}^*$. The so-called flower automaton gives a simple construction. Just draw a flower with $k$ petals with the initial state and unique final state in the center. Now spell the words on the petals (one word per petal) just like in Rick Decker's example. This gives you a NFA with $|u_1| + |u_2| + \dotsm + |u_k| - k + 1$ states. In your case, $u_1 = ab$, $u_2 = a$, so $|u_1| + |u_2| - 2 + 1 = 2$.

This construction is interesting when $\{u_1, ..., u_k\}$ is a length-variable code, which means that $\{u_1, ..., u_k\}^*$ is a free monoid. In this case, the NFA is not a DFA, but it is unambiguous: every accepted word has only one accepting path.

EDITED. Just changed "David's example" to "Rick Decker's example". In any case, I mean the NFA in the yellow box.

-
Nice. I didn't know the construction had such a felicitous name. –  Rick Decker Aug 20 at 16:54

Hint: the language is (almost) the set of all strings in $\{a,b\}^*$ that don't have two consecutive $b$'s. So all you need to remember is whether or not the last character you saw was a $b$.

-

1. Do I know any way to systematically transform regular expressions into finite automata?

Yes: Do so, go to 2.
No: Look into the textbook and go to step 1, or be creative (see other answers)¹.

2. Is the automaton small enough?

Yes: Cool, done!
No: Go to 3.

3. Do I know a way to make finite automata smaller?

Yes: Apply it and go to step 2.
No: Look into the textbook and go to step 3.

Follow-up question: do you see why there is an infinite loop in this algorithm if and only if the problem is ill-posed, that is there is no such automaton?

Yes: Congrats, you have understood why the class of regular languages (and similar ones) are oh so nice.
No: Off to the textbook you go!

1. While being creative is nice, note that if you don't use algorithms proven to be correct, it's you who have to prove that your automaton is correct.
-
Systematically exploring the space of approaches gets you far in undergrad situations, and sometimes even later. –  Raphael Jul 21 at 20:24

I think the following NFA would be correct:

N = ({q1, q2}, Sigma, delta, q1, {q1, q2})
Sigma = {a,b}
delta(q1, a) = {q1, q2}
delta(q1, b) = {}
delta(q2, a) = {q1}
delta(q2, b) = {q1}


But I'm not sure if q2 can be an accept state or not. In Rick's answer q2 is not an accept state, but I don't see why it can't be an accept state, because the only way to get to q2 is to have at least 1 a in your string, and if you have 2 consecutive b's then you'd get nowhere, so I don't see why q2 can't be an accept state.

-
You posted an answer to a textbook exercise without being (reasonably) sure it's correct? Probably not a good idea. Furthermore, how did you get there? How can the OP solve the next, similar problem? –  Raphael Aug 19 at 14:17
Your NFA is also a correct answer (with $q_2$ final), since the standard NFA-to-DFA construction yields the same DFA for yours and mine. There are many roads to the top of the mountain, grasshopper. –  Rick Decker Aug 19 at 14:20