← 🔁 Finite Automata (DFA, NFA, ε-NFA)
Subtopic 2 of 5

1.2NFA and ε-NFA

The idea

An NFA may have several moves (or none) for a symbol, and may move on ε. It accepts if at least one path accepts.

Think of it like this: Exploring a maze by cloning yourself at every fork: if any clone reaches the exit, you win.

Why it exists

Guessing makes some machines much smaller (the third symbol from the end needs 4 NFA states but 8 DFA states), yet no new languages appear.

How it works

  1. At each symbol, follow all allowed moves at once (a set of current states).
  2. ε-moves can be taken any time without reading.
  3. Accept if some current state is final when the input ends.
  4. NFA, ε-NFA and DFA all accept exactly the regular languages.

Worked example: Third symbol from the end is a

The NFA stays in q0 until it guesses it has reached the right a, then counts two more symbols. On babb one clone does this correctly and ends in the final state q3.

Now play with it

  • →Pick the NFA preset and run babb: several states can be gold at once.
  • →Try bbb: the clones die and the string is rejected.
a,baa,ba,bq0q1q2q3
babb
  • Start: ε-closure of q0 = {q0}
  • read "b" → {q0}
  • read "a" → {q0, q1}
  • read "b" → {q0, q2}
  • read "b" → {q0, q3}
  • End of input and at least one active state is final: ACCEPT

Check yourself

Which statement is true?

Remember: NFA = guess and accept if any path works; same power as a DFA.
Exam notes (the dense version)

An NFA may have several or no moves on a symbol, and an ε-NFA may also move without reading. A string is accepted if some path ends in a final state. NFAs are easier to design but recognise exactly the same languages as DFAs: the regular languages.

Previous year questions: Finite Automata (DFA, NFA, ε-NFA) (6)

PYQs are grouped by topic, so this is the full set for Finite Automata (DFA, NFA, ε-NFA); try the ones that match this subtopic. Open all 6 on the topic page.