Nondeterministic Finite Automata (NFA): Definition and Example

A nondeterministic finite automaton, or NFA, is a machine that reads a string one symbol at a time and is allowed to branch. It belongs to the study of formal languages, where it is the first step beyond the deterministic automaton and a useful way to write down regular languages.

What is a nondeterministic finite automaton?

A finite automaton has a finite set of states, reads its input from left to right and, after the last symbol, either accepts or rejects. In a deterministic automaton each state and each input symbol lead to exactly one next state. In a nondeterministic one that is relaxed: from the same state, the same symbol may lead to several states, and it may also lead to none.

The intuition is a machine that can branch. At each choice it follows all possibilities at once, or equivalently it guesses well. The word does not mean that the machine behaves randomly. Rabin and Scott, who introduced the concept in 1959, put it this way: a nondeterministic automaton "is not a probabilistic machine but rather a machine with many choices in its moves."

Nondeterminism does not give the machine extra power over the regular languages. It lets some automata be written in fewer states, and it makes certain constructions easier to describe. Some course notes abbreviate the machine as NDFA, and the meaning is the same.

What is the formal definition of an NFA?

An NFA is a five-tuple (Q, Σ, δ, q₀, F). The transition function δ does not return a single state but a set of states, which is what allows several moves, or none, for one symbol.

Here P(Q) is the set of all subsets of Q. An empty set as a result means the machine has no move for that state and symbol. Presentations differ in small details. The original paper by Rabin and Scott allows a set of start states instead of a single one, and some courses write the transition as a relation rather than a function. These variants describe the same class of machines, and this page uses a single start state and a function into subsets.

An NFA is usually drawn as a diagram: circles for the states, an arrow into the start state, a double circle for each accepting state, and an arrow between states for every transition, labeled with the symbol it reads. Two arrows with the same label leaving one state are the visible sign of nondeterminism. The same automaton can also be written as regular grammar rules, a translation that the page on converting between left-linear and right-linear grammars uses in both directions.

When does an NFA accept a string?

A string is accepted if there is at least one sequence of states that starts in the start state, follows the transitions for the symbols of the string one after another, and ends in an accepting state. The existence of one such run is enough. It does not matter that other runs get stuck or end in a state that does not accept.

Two pictures help. In the first, the machine makes the right choice at every branch, as if lucky, and the string is accepted whenever a lucky run exists. In the second, the machine clones itself at every branch and runs all copies in parallel. A clone with no move for the next symbol dies, and the string is accepted if any surviving clone ends in an accepting state.

The empty string is a special case. It has no symbols to read, so it is accepted exactly when the start state is itself an accepting state. The second picture leads to a simple way to follow a computation by hand:

1. Start with the set that contains only the start state.
2. For each symbol, replace the set by all states reachable from any member of the set on that symbol.
3. After the last symbol, accept if the set contains an accepting state.

This set of current states is exactly what the converted DFA remembers, a point that returns in the section on the conversion below.

Worked example: strings that end in 1

Take the NFA M with states p and q, alphabet {0, 1}, start state p and accepting state q. The transitions are δ(p, 0) = {p} and δ(p, 1) = {p, q}, and q has no moves at all.

The machine stays in p while it reads symbols. On a 1 it may also guess that this is the last symbol and move to q. If the guess is right, the string ends there and is accepted. If it is wrong, the run in q has no further move and dies, while the run in p continues.

The set method on the string 1011 gives:

1. Before reading, the set is {p}.
2. After the first 1, the run branches and the set is {p, q}.
3. After the 0, the run in q dies because q has no move on 0, and the set is {p}.
4. After the next 1, the set is {p, q}.
5. After the last 1, the set is {p, q}.

The final set contains q, so 1011 is accepted. The accepting run is p, p, p, p, q. For the string 10, the set after the 1 is {p, q}, the 0 leaves {p}, and q is missing, so 10 is rejected. The same trace shows why the state q is a dead end: it can accept only at the exact moment the string ends, and any further symbol removes that run. In general the machine accepts exactly the strings whose last symbol is 1. Following the set method, searching all paths and applying the plain rule "the last symbol is 1" give the same answer for all 8,191 strings over {0, 1} up to length 12, and 4,095 of them are accepted. Such a comparison tests the example but does not prove it for every length; the argument above does.

What is the difference between an NFA and a DFA?

Every DFA is also an NFA, since one move is one of the allowed numbers of moves. The reverse holds as well: for every NFA there is a DFA that accepts the same language, so the two kinds of machine recognize exactly the regular languages. Rabin and Scott proved this in their 1959 paper.

The price of the conversion is size. A DFA built from an NFA with n states may need up to 2ⁿ states, and for some languages that growth cannot be avoided. The language of strings whose n-th symbol from the end is 1 needs only n + 1 NFA states, while every DFA for it needs at least 2ⁿ. The method is the topic of converting an NFA to a DFA.

In practice the choice follows the task. An NFA is often the shorter and clearer way to write a language down, especially when a pattern says that something must occur somewhere in the middle or near the end of a string. A DFA is the form that runs directly, one state per step, with nothing to track beyond the current state. A common workflow therefore describes a language with an NFA and converts it to a DFA only when a deterministic machine is needed.

What is an epsilon-NFA?

An epsilon-NFA, also called an NFA with epsilon moves, adds transitions that consume no input. The transition function becomes δ: Q × (Σ ∪ {ε}) → P(Q), so a state can move to another state without reading a symbol. The set of states reachable from a state through such moves alone is its epsilon-closure, and computing it is the extra step in simulating the machine.

The additional freedom does not add power either. An automaton with epsilon moves can be converted to an NFA without them, and the languages recognized by NFAs, epsilon-NFAs and DFAs coincide. Epsilon moves are mainly convenient for combining automata, for instance when building an automaton from a regular expression.

Is a pushdown automaton a finite automaton?

No. A pushdown automaton extends a finite automaton with a stack, and the stack makes it strictly more powerful. In the Chomsky hierarchy, regular languages correspond to finite automata at type 3, and context-free languages correspond to nondeterministic pushdown automata at type 2. The language aⁿbⁿ is context-free but not regular, so a pushdown automaton recognizes it and no finite automaton does.

The limits of finite automata can be proved with the pumping lemma, which shows for aⁿbⁿ that the number of states is too small to keep a count.