Nondeterministic Finite Automaton¶
A finite-state string recognizer with set-valued transitions that accepts when at least one complete run reaches an accepting state.
Core Idea¶
A nondeterministic finite automaton (NFA) recognizes strings using finitely many states. From a state and input symbol it may have no successor, one successor, or several. It accepts a word if some complete run consumes every symbol and finishes in an accepting state, even if all other runs fail. Nondeterminism here is existential choice, not randomness or necessarily a physical machine executing paths in parallel.[^ref-e791fd3c8154]
In the conventional single-start model, its transition is \(\delta:Q\times\Sigma\to\mathcal P(Q)\). An ε-NFA additionally permits transitions that consume no symbol; ε-moves are useful for regular-expression construction but not required for the NFA identity.[^ref-a7f12a30d720] Rabin and Scott proved that tracking reachable subsets of \(Q\) gives an equivalent DFA. Thus NFAs and DFAs recognize exactly the regular languages, although their representations and execution costs can differ.[^ref-e791fd3c8154]
Scope of Application¶
NFAs are used to specify regular-language recognizers and to construct recognizers compositionally from classical regular expressions. A pattern alternation can split into two branches, and an implementation can advance the set of states reachable after each input character rather than sample one path. Cox's original engine exposition demonstrates both construction and state-set simulation.[^ref-a7f12a30d720]
Lexical analysis uses adjacent regular-language machinery, but the NFA is not an entire lexer: the original Lex report describes a deterministic generated recognizer plus longest-match and action policies. Likewise, regex extensions such as backreferences are not covered by the classical NFA equivalence theorem merely because they are called “regular expressions.”[^ref-682edfd84651]
Clarity¶
Specify finite states, alphabet, start state or states, accepting set, and set-valued transitions. For a word, follow only transitions matching successive symbols; after consuming the whole word, ask whether any reachable state is accepting. A dead branch does not reject the word if another branch survives. With ε-links, take ε-closure without consuming input.[ref-e791fd3c8154][ref-a7f12a30d720]
The recognized language is the set of accepted words, not the NFA itself. A DFA is the singleton-successor specialization; an unambiguous finite automaton may branch but limits each word to at most one accepting run. A probabilistic automaton instead assigns weights or chances. These distinctions concern machine structure or acceptance semantics, not just names.
Manages Complexity¶
Branching can make a pattern description or proof construction compact, but “NFA is smaller” is not a universal statement. Determinization collects all possible NFA states after a prefix into one DFA state; as many as \(2^{|Q|}\) subsets are possible, though many may be unreachable. Direct NFA simulation can compute the currently reachable set on demand without materializing the whole DFA.[ref-e791fd3c8154][ref-a7f12a30d720]
The distinction between specification size and recognition work is essential. A backtracking interpreter may revisit paths; a reachable-set simulator merges their equivalent current-state information. Both can implement the same existential recognition rule but have different costs.[^ref-a7f12a30d720]
Abstract Reasoning¶
To prove an NFA correct, show that every accepted word has a valid complete witness run and every intended word has at least one. For example, to recognize binary strings whose nth symbol from the end is \(1\), loop in the start state and branch on a \(1\) into a chain that demands exactly \(n-1\) further symbols. Only a correctly timed guess can reach the final state exactly at input end. In a regex for abab|abbb, the abab path fails on abbb, but the abbb path accepts; failed alternatives do not negate that one witness.[ref-e791fd3c8154][ref-a7f12a30d720]
Knowledge Transfer¶
The model shows how existential path semantics can be simulated by maintaining the set of still-possible states. That method transfers to related finite-state algorithms, but the exact subset bound and regular-language theorem depend on finite control and whole-word acceptance. The proposed DAG parent is the live Automaton identity; DFA and unambiguous finite automaton are related specializations, not strict parents of this general branching recognizer.
[^ref-e791fd3c8154]: Michael O. Rabin and Dana Scott, “Finite Automata and Their Decision Problems,” IBM Journal of Research and Development 3, no. 2 (1959): 114–125, especially Definitions 9–11 and Theorem 11, pp. 120–121. Original paper PDF. [^ref-a7f12a30d720]: Russ Cox, “Regular Expression Matching Can Be Simple And Fast,” sections on NFA construction, simulation, and DFA caching. Author's original article and code. [^ref-682edfd84651]: M. E. Lesk and E. Schmidt, “Lex—A Lexical Analyzer Generator” (1975), Abstract and Introduction. Original report mirror.
Relationships to Other Abstractions¶
Current abstraction Nondeterministic Finite Automaton Domain-specific
Parents (1) — more general patterns this builds on
-
Nondeterministic Finite Automaton is a kind of Automaton Domain-specific
A nondeterministic finite automaton is an automaton specialized to finite-word, finite-state existential recognition.
Hierarchy paths (2) — routes to 2 parentless roots
- Nondeterministic Finite Automaton → Automaton → Abstract Machine → Formal System → Formalization → Representation → Abstraction
- Nondeterministic Finite Automaton → Automaton → Abstract Machine → Formal System → Formalization → Transformation → Function (Mapping)
Neighborhood in Abstraction Space¶
Nondeterministic Finite Automaton sits in a moderately populated region (42nd percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Formal Sequences & Language Structure (16 abstractions)
Nearest neighbors
- Turing Machine — 0.90
- Automaton — 0.88
- Moore machine — 0.87
- Generalized Büchi Automaton — 0.87
- Powerset Construction — 0.86
Computed from structural-signature embeddings · 2026-10-08