# Find the NFA for the language $\{ w | \text{ w contains an even number of 0s, or contains exactly two 1s } \}$

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:

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:

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.

-
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