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 \cup 1)^* \cdot 000 \cdot (0 \cup 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

Note that the word 000 is not accepted by the suggested automaton. To see why, consider the strongly connected component $C$ that contains the initial state -- $C$ consists only of the initial state and its successor, which we denote by $q_0$ and $q_1$, respectively. The component $C$ should capture the language of the regex $(0 \cup 1)^*$. Hence, a run of the automaton should be able to get out of $C$ (i.e., guesses when to start reading the infix 000 of the input word) from either $q_0$ or $q_1$. To fix the solution, we can add a transition, labeled with 0, from $q_0$ to the third state (lets call it $q_2$). Or we can replace the whole component $C$ with a single state $q$, where $q$ is initial, has a self-loop labeled with $0,1$, and has a transition to $q_2$ that is labeled with 0.

Answer 2

I’d like to add that your professor might have followed an algorithm for converting a regular expression to an NFA that’s based on Lemma 1.55. In these kinds of questions, you're usually expected to follow the algorithm as presented; this typically results in an unsimplified but correct NFA. Refer to examples 1.56 and 1.58 in the textbook for more details.