title: "Nondeterministic Finite Automaton"

Nondeterministic Finite Automaton

Definition. A nondeterministic finite automaton (NFA) is a five-tuple $N = (Q, \Sigma, \delta, q_0, F)$ that differs from a DFA only in its transition function, $\delta : Q \times \Sigma \to \mathcal{P}(Q)$, which returns a set of states rather than one. $N$ accepts $w$ if some sequence of choices ends in an accepting state.

Read it two ways: the machine guesses a branch and accepts if some guess works, or the machine tracks the whole set of states it could be in. The second reading is the subset construction, which turns any NFA into an equivalent DFA, so nondeterminism adds no power. What it adds is compactness: a language may need exponentially fewer NFA states than DFA states. Introduced in Lecture 3.