3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Your NFA looks fine to me. $\endgroup$ Aug 3, 2011 at 6:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Aug 3, 2011 at 6:09
  • $\begingroup$ @Gerry Myerson: Thanks a lot for your comment. $\endgroup$
    – roxrook
    Aug 3, 2011 at 6:17
  • $\begingroup$ @Raphael: Great thanks. $\endgroup$
    – roxrook
    Aug 3, 2011 at 6:18
  • $\begingroup$ 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 $\endgroup$
    – t.b.
    Nov 18, 2011 at 19:21

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Aug 3, 2011 at 17:33
  • $\begingroup$ @chazisop: Thanks a lot. However, I think the link you gave is broken :(. Could you fix that? $\endgroup$
    – roxrook
    Aug 3, 2011 at 19:23
  • $\begingroup$ 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. $\endgroup$
    – chazisop
    Aug 4, 2011 at 7:53
  • $\begingroup$ @chazisop can you please fix the link ? $\endgroup$
    – ankit
    Mar 9, 2020 at 17:09

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.