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.
Best Answer
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.