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:

enter image description here

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.

  • $\begingroup$ There are infinitely many automata for every language, so it's not too surprising. Determinise and minimize both, then check for isomorphism. When you construct automata and are not sure about correctness, try proving it! $\endgroup$ – Raphael Sep 27 '17 at 17:09
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Sep 27 '17 at 17:09

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.