Imagine you are reading a long binary string one symbol at a time and you must say whether it ends with 01. A DFA has to keep careful track of "what were the last two symbols?" at every step. Wouldn't it be easier if the machine could simply guess: "this 0 is the start of the final 01", and then check that guess?
That is exactly the freedom a Nondeterministic Finite Automaton (NFA) gets. At any moment it may have several possible moves (or none at all), and it accepts if at least one of its choices leads to a final state.
An NFA is a finite automaton in which, for a given state and input symbol, the machine may move to zero, one or several next states. A string is accepted if some sequence of choices consumes the whole string and ends in a final state.
In this chapter we will define NFAs formally, learn two ways to "run" an NFA on a string (the computation tree and the set-of-states method), design several NFAs, and compare them with the DFAs from the previous chapters. Every NFA in this chapter was tested with a small simulator against its language for all strings up to length 12.
Why Nondeterminism?
In a DFA, the next state is completely fixed: for every state and every symbol there is exactly one arrow. An NFA relaxes this in two ways:
Several arrows may leave a state on the same symbol. The machine can follow any of them.
No arrow may leave a state on some symbol. If the machine is in that state and reads that symbol, that particular attempt simply dies (it is rejected along that path). No dead/trap state needs to be drawn.
There are three equally good ways to think about this:
Lucky guessing. The NFA always "knows" which choice will work. If any choice works, it makes that one.
Parallel copies. At each choice point the machine clones itself, one copy per option. A copy with no move disappears. If any copy is in a final state when the input ends, the string is accepted.
Set of current states. Instead of one current state, keep the set of all states the machine could be in. This view is the one we use for calculation, and it leads directly to the NFA → DFA conversion in the next chapter.
Nondeterminism is not randomness. Nothing is decided by a coin toss. It is a mathematical way of saying "accept if some path accepts", which makes many machines much smaller and easier to design.
Formal Definition
An NFA is a 5-tuple:
N = (Q, Σ, δ, q0, F)
Q finite set of states
Σ finite input alphabet
δ transition function δ : Q × Σ → 2^Q
q0 start state, q0 ∈ Q
F set of final (accepting) states, F ⊆ QEverything is the same as a DFA except the type of δ. In a DFA, δ(q, a) is one state. In an NFA, δ(q, a) is a set of states, an element of the power set 2Q. That set may be empty (∅), which means "no move".
Extended transition function
To talk about whole strings we extend δ to δ̂ : Q × Σ* → 2Q, defined by induction on the length of the string:
δ̂(q, ε) = { q }
δ̂(q, wa) = ⋃ δ(p, a) over all p ∈ δ̂(q, w)In words: to process wa, first find every state reachable on w, then take every a-move from each of them and collect the results.
Language of an NFA
L(N) = { w ∈ Σ* : δ̂(q0, w) ∩ F ≠ ∅ }A string is accepted if the set of states reachable on it contains at least one final state. It does not matter how many other paths die or end in non-final states.
Example 1: Strings Ending with 01
Σ = {0, 1}, L = { w : w ends with 01 }.
The idea: stay in q0 while reading the "front" of the string. When we see a 0 that we guess is the second-last symbol, jump to q1. Then a 1 must follow, and it must be the last symbol.
──► q0 ──0──► q1 ──1──► ((q2))
⟲ 0,1
──► start state
((q2)) final state
⟲ 0,1 self-loop on 0 and on 1State | 0 | 1 |
|---|---|---|
→ q0 | {q0, q1} | {q0} |
q1 | ∅ | {q2} |
* q2 | ∅ | ∅ |
(→ marks the start state and * marks a final state, the usual convention in transition tables.)
Notice three NFA features at once:
δ(q0, 0) = {q0, q1} has two choices.
δ(q1, 0) = ∅: no move. A path that guessed too early dies here.
q2 has no outgoing arrows. If anything comes after "01", that path dies, which is exactly right: then 01 was not at the end.
Running it: the computation tree
Input 0101. Each branch is one possible sequence of choices:
q0 ─0─► q0 ─1─► q0 ─0─► q0 ─1─► q0 ends in q0 (not final)
└─0─► q1 ─1─► q2 ends in q2 ✓ ACCEPT
└─0─► q1 ─1─► q2 ─0─► (no move, dies)One branch reaches q2 exactly when the input ends, so 0101 is accepted. The other two branches failing does not matter.
Running it: the set-of-states method
Drawing trees gets messy for long strings. Instead, track the set of all possible current states, using δ̂:
Input: 0 1 0 1
{q0} ──► {q0,q1} ──► {q0,q2} ──► {q0,q1} ──► {q0,q2}
contains q2 → ACCEPTEach step: for every state in the current set, collect its moves on the symbol. For example from {q0, q2} on 0: δ(q0, 0) ∪ δ(q2, 0) = {q0, q1} ∪ ∅ = {q0, q1}.
Now input 0110:
Input: 0 1 1 0
{q0} ──► {q0,q1} ──► {q0,q2} ──► {q0} ──► {q0,q1}
no final state → REJECTCorrect: 0110 ends with 10, not 01.
Example 2: Third Symbol from the End Is 1
Σ = {0, 1}, L = { w : |w| ≥ 3 and the third-last symbol of w is 1 }.
Guess which 1 is the third-last symbol, then insist that exactly two more symbols follow.
──► q0 ──1──► q1 ──0,1──► q2 ──0,1──► ((q3))
⟲ 0,1State | 0 | 1 |
|---|---|---|
→ q0 | {q0} | {q0, q1} |
q1 | {q2} | {q2} |
q2 | {q3} | {q3} |
* q3 | ∅ | ∅ |
Trace on 110 (third-last symbol is the first 1):
{q0} ─1─► {q0,q1} ─1─► {q0,q1,q2} ─0─► {q0,q2,q3} contains q3 → ACCEPTTrace on 1011 (third-last symbol is 0):
{q0} ─1─► {q0,q1} ─0─► {q0,q2} ─1─► {q0,q1,q3} ─1─► {q0,q1,q2} no q3 → REJECTThis NFA has only 4 states. Any DFA for the same language needs 8 states, because a DFA must remember all of the last three symbols (23 possibilities). In general, "the n-th symbol from the end is 1" has an NFA with n + 1 states, but its smallest DFA has 2n states. We will see this blow-up concretely in NFA to DFA Conversion (Subset Construction), and prove minimality with the tools of DFA Minimization.
Example 3: Strings Containing abb
Σ = {a, b}, L = { w : w contains abb as a substring }.
Guess where the substring starts, read abb, then accept anything afterwards.
──► q0 ──a──► q1 ──b──► q2 ──b──► ((q3))
⟲ a,b ⟲ a,bState | a | b |
|---|---|---|
→ q0 | {q0, q1} | {q0} |
q1 | ∅ | {q2} |
q2 | ∅ | {q3} |
* q3 | {q3} | {q3} |
Compare this with a DFA for the same language: in the DFA, after reading ab and then an a, you have to work out carefully that you should go back to the "seen a" state, not the start. The NFA never needs that "fall-back" reasoning: wrong guesses just die, and q0 keeps trying new starting positions.
Trace on babba:
{q0} ─b─► {q0} ─a─► {q0,q1} ─b─► {q0,q2} ─b─► {q0,q3} ─a─► {q0,q1,q3} contains q3 → ACCEPTExample 4: Starts with a and Ends with b
Σ = {a, b}, L = { w : w starts with a and ends with b }.
──► q0 ──a──► q1 ──b──► ((q2))
⟲ a,bState | a | b |
|---|---|---|
→ q0 | {q1} | ∅ |
q1 | {q1} | {q1, q2} |
* q2 | ∅ | ∅ |
A string starting with b dies immediately at q0 (δ(q0, b) = ∅). No trap state is needed. In a DFA you would have to add a dead state explicitly.
How to Design an NFA: A Recipe
Describe the pattern you are looking for ("ends with 01", "contains abb", "n-th from the end is 1").
Let the start state loop on every symbol if the pattern can appear anywhere (or at the end). This loop lets the NFA "wait" until the right moment.
Build a straight chain of states that spells out the pattern. Leave out all transitions that do not match; they simply die.
Add a loop on the final state only if anything may follow the pattern (like "contains"). Do not add one for "ends with".
Test on a few accepted and rejected strings, including the empty string and strings shorter than the pattern.
The minimum number of NFA states for "ends with a fixed string x" or "contains x" is usually |x| + 1: one state per prefix of x.
DFA vs NFA
Feature | DFA | NFA |
|---|---|---|
Transition function | δ : Q × Σ → Q | δ : Q × Σ → 2Q |
Moves per (state, symbol) | Exactly one | Zero, one or many |
Dead state | Must be drawn if needed | Not needed (missing arrow = path dies) |
Acceptance | The single run ends in F | At least one run ends in F |
Running on a string | Follow one path, O(|w|) | Track a set of states, O(|w| · |Q|2) in the worst case |
Ease of design | Harder for "ends with / n-th from end" patterns | Usually much easier and smaller |
Number of states | Can be up to 2n for a language with an n-state NFA | Often exponentially fewer |
Languages accepted | Exactly the same: the regular languages | |
Relationship | Every DFA is an NFA (just read δ(q, a) = p as the set {p}) | |
Are NFAs More Powerful than DFAs?
No. This is the single most important fact in this chapter.
For every NFA there is a DFA that accepts exactly the same language. So NFAs and DFAs both recognise exactly the class of regular languages.
The intuition comes from the set-of-states method. If the NFA has n states, the set of current states is always one of the 2n subsets of Q. That is a finite number, so a DFA can use each subset as one of its own states. That is the subset construction, covered step by step in the next chapter.
So nondeterminism buys convenience and size, not extra power. (This is not true for every machine model: nondeterministic pushdown automata are strictly more powerful than deterministic ones, as you will see in Pushdown Automata.)
Common Mistakes
Thinking a string is rejected because one path fails. Acceptance needs only one successful path. Rejection needs all paths to fail.
Accepting when a final state is visited in the middle. The path must be in a final state when the whole input has been read. In Example 1, the string 010 visits q2 after "01", but that path dies on the last 0, and the string is rejected.
Making a complement by swapping final and non-final states. This works for a (complete) DFA but not for an NFA. Swap the states in Example 1 so that q0 and q1 are final: since q0 is reachable on every string, the new machine accepts every string, including 01. It is not the complement. Convert to a DFA first, then swap.
Adding a loop on the final state for "ends with" languages. That changes the language to "contains".
Believing NFAs accept more languages. They accept the same class; they are only smaller or easier to build.
Confusing nondeterminism with probability. There are no probabilities; it is "exists a path".
Practice and GATE-Style Questions
Q1. Using the NFA of Example 1, which of these are accepted: ε, 1, 01, 001, 0110, 11101?
The NFA accepts exactly the strings ending in 01. So 01, 001 and 11101 are accepted; ε, 1 and 0110 are rejected. For instance on ε the set of states is {q0}, which contains no final state.
Q2. What is the minimum number of states of an NFA (without ε-moves) for strings over {0, 1} whose 4th symbol from the end is 1? And of a DFA?
NFA: 5 states (q0 with a self-loop, then a chain of 4 transitions). DFA: 24 = 16 states, because the DFA must remember the last four symbols; every one of the 16 possibilities behaves differently on some future input.
Q3. An NFA has 5 states. What is the maximum number of states in the equivalent DFA produced by subset construction?
25 = 32 (one per subset of Q, including ∅). In practice usually far fewer subsets are reachable.
Q4. True or false: the class of languages accepted by NFAs is a proper superset of the class accepted by DFAs.
False. Both accept exactly the regular languages. Every DFA is already an NFA, and every NFA can be converted into a DFA by subset construction.
Q5. Design an NFA for strings over {a, b} that end with aa or bb.
Use 4 states. q0 loops on a and b. From q0: on a go to q1, on b go to q2. From q1 on a go to q3; from q2 on b go to q3. q3 is the only final state and has no outgoing arrows. (Both branches can share the same final state because both patterns end there.)
Q6. Interview: why are NFAs useful in practice if DFAs are just as powerful?
They are much easier to build from a description such as a regular expression, and they can be exponentially smaller. Tools like lexer generators and regex engines first build an NFA from the pattern (see Regular Expression to Finite Automata), then either simulate it directly with sets of states or convert it to a DFA for fast matching.
Summary
An NFA is a 5-tuple (Q, Σ, δ, q0, F) with δ : Q × Σ → 2Q: zero, one or many moves per symbol.
A missing transition means that path dies; no dead state is needed.
A string is accepted if at least one path ends in a final state after reading the whole input.
Simulate an NFA by tracking the set of current states, step by step, using δ̂.
NFAs are often much smaller and easier to design (n + 1 states vs 2n for "n-th symbol from the end is 1").
NFAs and DFAs accept exactly the same languages: the regular languages.
Swapping final states does not complement an NFA.
An NFA says "yes" if any path says yes. Keep track of the set of states, and nondeterminism becomes simple bookkeeping.