NDFA importance; two consecutive a or b

Why NDFA is important

Although every NFA can be converted to an equivalent DFA, NFAs are useful because:

1. Easier design. An NFA can "guess" (for example, where a pattern begins), so it is often much simpler to design than a DFA.
2. Fewer states. An NFA with n states may need up to 2ⁿ states as a DFA. For example, "the n-th symbol from the end is 1" needs n + 1 NFA states but 2ⁿ DFA states.
3. Constructions are easy. Union, concatenation, star and the conversion from regular expressions (Thompson's construction) are natural with NFAs and ε-moves.
4. Theoretical tool. Proofs of closure properties and Kleene's theorem are simpler with NFAs. Nondeterminism is also a key idea for more powerful models: nondeterministic PDAs are strictly more powerful than deterministic PDAs, and nondeterministic Turing machines (which are no more powerful than ordinary TMs) are used to define the class NP.

NFA for strings containing aa or bb

The NFA guesses where the two equal symbols begin.

M = ({q0, q1, q2, q3}, {a, b}, δ, q0, {q3})

              a
        ┌──► q1 ──a──┐
 ──► q0 │            ├──► ((q3)) ↻a,b
  ↻a,b  └──► q2 ──b──┘
         (q0 -a-> q1, q0 -b-> q2)

(q0 –a→ q1 –a→ q3 detects "aa"; q0 –b→ q2 –b→ q3 detects "bb"; q3 loops on a and b.)

Test

• "abba": q0 →a q0 →b q2 →b q3 →a q3 (final). Accepted, since it contains bb.
• "abab": every path that leaves q0 for q1 or q2 dies on the next symbol (there is no aa or bb), so no path reaches q3 and the string is rejected.