Construct an NFA over $\{0, 1\}$ whose language contains only words that do not end with $10$.

This is one of the first problems in the book, so it's supposedly easy. I just can't figure it out. It's easy using a DFA, but I'm not so sure using an NFA. Maybe I'm not understanding a particular concept in the NFA.


migrated from cstheory.stackexchange.com Aug 30 '12 at 4:54

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 9
    $\begingroup$ Every DFA is also an NFA. $\endgroup$ – Yuval Filmus Aug 30 '12 at 2:40
  • 1
    $\begingroup$ @YuvalFilmus you should make that an answer. $\endgroup$ – Luke Mathieson Aug 30 '12 at 7:16
  • 1
    $\begingroup$ Presumably you mean "...whose language is the set of strings that do not end with 10." $\endgroup$ – JeffE Aug 30 '12 at 11:48
  • $\begingroup$ I presume you mean an NFA over the alphabet $\{0,1\}$, which recognizes a language that is a subset of $\{0,1\}^*$. $\endgroup$ – Gilles 'SO- stop being evil' Aug 30 '12 at 12:55

Every DFA is also, in particular, an NFA. Therefore if you have constructed a DFA for some language, then you have a fortiori constructed an NFA for it.


If you are more comfortable with regular expressions, try to define your language as one.

For example $(0 + 1)^*(00 + 01 + 11) + 1 + 0 + \varepsilon$

Now convert the regular expression into an automaton with the simple method (which I assume you know).

  • $\begingroup$ This method won't give you pretty automata, but always correct ones (barring technical mistakes). You can always determinise and minimise afterwards. $\endgroup$ – Raphael Aug 30 '12 at 21:30

Create one that accepts strings over $\{0,1\}^*$ that end with the suffix $00$, another one for strings that end with $01$, and a third one for strings that end with $11$ then take their union.NFA accepting strings over {0, 1}* not ending with 10

EDIT Now NFA handles strings whose length $\lt 2$ and has an initial state.

  • 2
    $\begingroup$ (1) Your diagram does not specify the initial state. (2) You forgot to handle strings whose length is less than two. $\endgroup$ – Tsuyoshi Ito Aug 30 '12 at 14:59
  • 5
    $\begingroup$ Now the NFA in your diagram accepts all strings. $\endgroup$ – Tsuyoshi Ito Aug 30 '12 at 19:16

Your Answer

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