# NFA for binary words that do not end in 10

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.comAug 30 '12 at 4:54

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

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

• This method won't give you pretty automata, but always correct ones (barring technical mistakes). You can always determinise and minimise afterwards. – 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.

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

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