Nondeterministic finite automaton

Formally, an NFA is a 5-tuple (Q, Σ, δ, q₀, F), where Q is a finite set of states, Σ is a finite input alphabet, δ is a transition function mapping Q × (Σ ∪ {ε}) to a set of subsets of Q, q₀ is the start state, and F is the set of accepting states. The key difference from a DFA is that δ returns a set of possible next states, not a single state. For example, from state q₁ on symbol 'a', an NFA might transition to both q₂ and q₃, representing a choice. ε-transitions allow moving between states without reading any input, which is useful for modeling optional components or concatenation in regular expressions.

The language of an NFA is the set of strings for which there exists at least one accepting computation path. This existential interpretation is what gives NFAs their expressive convenience, but it also means that simulating an NFA on a string can require exploring multiple paths simultaneously, leading to the exponential blow-up in the worst case when converting to a DFA.

The fundamental result, proved by Rabin and Scott, is that NFAs and DFAs recognize exactly the same class of languages—the regular languages.¹ This is shown by the subset construction: given an NFA with n states, one can construct a DFA whose states are subsets of the NFA's states, yielding up to 2ⁿ states. This exponential blow-up is not just theoretical; there exist families of regular languages for which any DFA requires exponentially more states than an NFA, such as the language of strings where the n-th symbol from the end is 'a'.

Despite this worst-case cost, NFAs are often more concise and easier to design than DFAs. For instance, a regular expression like (a|b)*abb can be directly translated into an NFA with a handful of states, whereas the minimal DFA might require more. This conciseness is exploited in practice: many regex engines internally convert regular expressions to NFAs or simulate them directly using backtracking or Thompson's construction, which builds an NFA in linear time.

NFAs are not just theoretical curiosities; they are the backbone of lexical analysis in compilers. Tools like Lex and Flex generate scanners by converting regular expressions into NFAs and then to DFAs for efficient tokenization. The subset construction ensures that the resulting DFA runs in linear time per input character, which is critical for processing source code quickly.

In pattern matching, NFAs underlie the algorithms used in text editors and programming languages. Ken Thompson's 1968 paper introduced a method to compile regular expressions into NFAs and simulate them efficiently, a technique still used in many grep implementations.² More recently, NFAs have been applied to network intrusion detection, where they model patterns in packet payloads, and to XML schema validation, where they check document structure against regular expressions.

One often-overlooked fact is that NFAs can be exponentially more concise than DFAs, but the reverse is not true: any DFA is trivially an NFA, so NFAs are never less concise. This asymmetry is a classic example of the power of nondeterminism in finite-state systems.

Another niche area is the study of ambiguous NFAs, where a string may have multiple accepting paths. Unambiguous NFAs, where each string has exactly one accepting path, are strictly less powerful than general NFAs in terms of state complexity, yet they still recognize all regular languages. This was proven by Stearns and Hunt in 1985.³

In quantum computing, the notion of a quantum finite automaton (QFA) generalizes NFAs by allowing superpositions of states, and some QFA variants can recognize certain non-regular languages with bounded error, a surprising departure from classical automata.⁴ Additionally, NFAs with ε-transitions are not more powerful than those without, but they can reduce the number of states needed, a fact used in minimizing regular expression representations.

ε-transition

A transition that does not consume any input symbol, allowing the automaton to change states spontaneously.

Subset construction

An algorithm that converts an NFA to an equivalent DFA by treating sets of NFA states as DFA states.

Regular language

A language that can be recognized by a finite automaton, equivalently described by regular expressions.

State complexity

The number of states in the minimal automaton recognizing a given language, used to measure conciseness.