Regular Expression converted to NFA

Question

Hello, all,

First time poster, here. Anyways, here is my question from the textbook Introduction to the Theory of Computation, 2nd Ed. (Sipser, 2006). Question 1.19 is asking us to convert a regular expression to a nondeterministic finite automaton. The regular expression is given as:

(0 union 1)* 000 (0 union 1)*

Which I interpret as:

"Any number of 0's or 1's, followed by 000, followed by any number of 0's or 1's."

This is the solution that I came up with:

However, the professor of this course I am taking provided a solution, albeit unsimplified, that is different from mine. I am wondering where I went wrong. I have asked this same question to my professor via e-mail (distance ed.), but since I am not expecting a reply based on past experience, I have also asked this question here. Any help you can provide would be greatly appreciated.

Answer 1

Notice that the word 000 is not accepted by your automaton. To see why your automaton is wrong. Look at the strongly connected component that includes the initial state (the first two states in your figure, lets call them $q_0$ and $q_1$). This component is meant to read the (0|1)* prefix. Hence, you must be allowed to get out of this component(i.e., guess when to start reading the 000 part of the word) from either $q_0$ or $q_1$. To fix your solution, you should add a transition, labeled with 0, from $q_0$ to the third state in your figure (lets call it $q_3$). Or you can replace the whole component with a single state q. such that q is initial, has a self-loop labeled with 0,1 and has a transition, labeled with 0, to $q_3$.