Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 59 · Finite Automata

Nondeterministic Finite Automata and ε-Moves

Learn nondeterministic finite automata: multiple transitions, guessing, ε-moves and epsilon closure, with a Python simulator that tracks sets of states.

A DFA has exactly one move for every state and symbol. A nondeterministic finite automaton (NFA) relaxes that rule: from a state, a symbol may lead to several next states, to one, or to none at all. The machine accepts a string if at least one sequence of choices ends in an accepting state.

Nondeterminism is not a real-world computer feature; it is a mathematical convenience. It lets you describe many languages far more simply, and, as the next lessons show, it adds no recognizing power: every NFA can be converted to an equivalent DFA.

The formal definition

An NFA is a 5-tuple (Q, Σ, δ, q0, F), the same as for a DFA except that the transition function returns a set of states:

δ : Q × Σ → P(Q), where P(Q) is the set of all subsets of Q.

A transition that returns the empty set means "stuck": that computation branch dies. An NFA accepts w if some path of choices through the machine reads all of w and ends in a state in F. It rejects only if every path fails.

There are two equivalent ways to picture this: the machine "guesses" the correct path (always picking a branch that leads to acceptance, if one exists), or it explores all paths at once, as parallel copies. The code below uses the second view: it keeps the set of states the machine could currently be in.

Example: the third symbol from the right is a

A DFA for this needs 8 states because it must remember the last three symbols. An NFA needs only 4: it loops in the start state while "guessing" when the interesting a has just been read, then counts exactly two more symbols.

flowchart LR
    start(( )) --> q0
    q0(("q0")) -->|"a, b"| q0
    q0 -->|"a"| q1(("q1"))
    q1 -->|"a, b"| q2(("q2"))
    q2 -->|"a, b"| q3((("q3")))

From q0 on input a, the NFA has two choices: stay in q0, or guess that this a is the third from the end and go to q1. The guess succeeds only if exactly two symbols follow.

Python Simulating an NFA by tracking a set of states

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the trace you can watch the set of "possible states" grow and shrink. The word baab is accepted because one of the surviving copies of the machine, the one that guessed correctly at the first a, reaches q3. Words shorter than 3 symbols can never reach q3, so ab and ε are rejected.

ε-NFAs: moves that read no input

An ε-NFA (epsilon-NFA) allows transitions labeled ε: the machine may move from one state to another without consuming any input symbol. They are mostly a drawing convenience, for example for gluing smaller machines together, as in converting a regular expression to an automaton. The transition function becomes δ : Q × (Σ ∪ {ε}) → P(Q).

The key tool is the ε-closure of a state q, written ECLOSE(q): the set of all states reachable from q by following ε-arrows only (zero or more). q is always in its own closure. To simulate an ε-NFA you:

  1. Start with ECLOSE(q0).
  2. For each input symbol, compute every state reachable by that symbol from the current set, then take the ε-closure of the result.
  3. Accept if the final set contains an accepting state.

Here is an ε-NFA for the language a*b*c*: any number of a's, then b's, then c's. The ε-arrows let the machine skip a phase.

flowchart LR
    start(( )) --> p0
    p0(("p0")) -->|"a"| p0
    p0 -->|"ε"| p1(("p1"))
    p1 -->|"b"| p1
    p1 -->|"ε"| p2((("p2")))
    p2 -->|"c"| p2

p0, p1 and p2 are the a-phase, b-phase and c-phase. p2 accepts because any of the phases may be empty.

Python Epsilon closure and an epsilon-NFA

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

ECLOSE(p0) contains all three states, so even the empty string is accepted and ccc works: the machine takes both ε-arrows before reading the first c. The words ba and acb are rejected because they break the a, then b, then c order.

DFA versus NFA at a glance

Feature DFA NFA
Moves per (state, symbol) exactly one zero, one or many
ε-moves no allowed in ε-NFAs
Acceptance the single path ends in F some path ends in F
Easy to implement yes, one table lookup per symbol needs a set of states
Size for some languages sometimes exponentially larger usually smaller
Languages recognized regular regular (same class)

NFAs are easier to design, DFAs are easier to run. The next lesson turns an NFA into a DFA by a mechanical procedure, which is how regex engines work internally.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. When does an NFA accept a string?

    Acceptance is existential: one successful computation path is enough, even if all other paths fail or get stuck.
  2. 2. What is the ε-closure of a state q?

    ECLOSE(q) follows ε-arrows only, zero or more times, and always includes q itself.
  3. 3. In the 'third symbol from the right is a' NFA, why is 'ab' rejected?

    Reaching q3 requires reading the guessed 'a' plus two more symbols, so at least three symbols. A 2-symbol string cannot get there.
  4. 4. Which statement about NFAs and DFAs is correct?

    Every NFA can be converted to an equivalent DFA, so nondeterminism does not add recognition power, only convenience and possibly succinctness.

Summary

  • An NFA's transition function returns a set of states; it accepts if some path ends in an accepting state.
  • Simulate by tracking the set of all currently possible states.
  • ε-moves consume no input; ECLOSE(q) is the set of states reachable from q by ε-moves alone.
  • NFAs can be exponentially smaller than DFAs (third symbol from the right: 4 states versus 8) but recognize exactly the regular languages.

Next: Converting an NFA to a DFA