Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm working on the problem sets from "Introduction to the Theory of Computation" 2nd edition - Michael Sipser. This problem is in chapter 1 page 85,

1.7 part c)

Give the state diagrams of NFA for the language $\{ w | \text{ w contains an even number of 0s, or contains exactly two 1s } \}$ with 6 states.

I understand DFA quite well because its simplicity, a finite number of states, where each state must have a branch out for each input in $\Sigma$. However, I'm very confused about NFA, it only makes sense after I see the solution.
Using DFA, I break this problems into two parts then combine them as follows: enter image description here

enter image description here

The solution for DFA is straightforward, furthermore I can easily verify my own answer by some arbitrary inputs. And here is my attempt using NFA:
enter image description here

The problem I'm having is I don't know whether it is correct or not. I tested with some inputs and thought it should be ok. The reason that I was so negative with NFA because the bad reputation that I had with it before. Whenever I solve a NFA with a given solution, I got it wrong or slightly different than the author. I wonder if is there a way to verify the correctness of a NFA in general? Sipser's book is great however, he talks so fast, especially I'm self-teaching, I feel it difficult to check my work against a certain concept. Any idea or suggestion would be greatly appreciated. Thank you.

share|cite|improve this question
Your NFA looks fine to me. – Gerry Myerson Aug 3 '11 at 6:08
Personally, I think the NFA construction for union is straight-forward. It also leads to smaller automata (which blow up while determinising, of course). "I can easily verify my own answer by some arbitrary inputs" -- this statement is wrong, but equally valid for both DFA and NFA. The only difference is that you might have to check many runs in the NFA as opposed to one run in the DFA. Your automaton is correct, btw. – Raphael Aug 3 '11 at 6:09
@Gerry Myerson: Thanks a lot for your comment. – Chan Aug 3 '11 at 6:17
@Raphael: Great thanks. – Chan Aug 3 '11 at 6:18
An anonymous user wanted to add the following comment: "if you pass the input 100 then its will not work ,because in OR operation we now that if one condition is false and one is true then overall result is true which contradict our statement" in a suggested edit – t.b. Nov 18 '11 at 19:21
up vote 2 down vote accepted

Have you read the NFA to DFA conversion algorithm yet? Just convert the NFA to a DFA or even go a step further and get the regular expression. 1-2 examples should be enough, since the process is straight-forward but time-consuming.

You can verify if two NFAs (that includes DFAs of course) are equivalent in quadratic time, see also these slides.

While doing those exercises, I didn't bother formally check equivalence, but rather I was checking the NFA,DFA or regular expression . The probability of slip-up mistakes decreases in that order, although some people feel more comfortable working with DFAs than regexes.

share|cite|improve this answer
Determinising and (afaik) regex-ifying can cause exponential blowup in representation size. Therefore, I do not think going that path is helpful for seeing correctness. Equivalence checks are a good pointer, of course, if you have some formal representation. – Raphael Aug 3 '11 at 17:33
@chazisop: Thanks a lot. However, I think the link you gave is broken :(. Could you fix that? – Chan Aug 3 '11 at 19:23
Raphael , you are right. The extra advice that small examples from exercise books will be ok, even if there is an exponential blowup (still , it can be time-consuming). As for the link, it was downloading a .pdf.gz file that wasn't working with my reader, so I changed it to a plain html view of the slides. – chazisop Aug 4 '11 at 7:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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