NFAs

An NFAs, or nondeterministic finite automaton, is a theoretical machine used in formal language theory to recognize regular languages. It consists of a finite set of states Q, an input alphabet Σ, a transition relation δ that maps a state and an input symbol (including the empty string) to a set of possible next states, a designated start state q0 ∈ Q, and a set F ⊆ Q of accepting states. Formally, an NFA accepts a string w if there exists a path, following transitions labeled with symbols of w (and possibly including ε moves that consume no input), that starts at q0 and ends in a state in F.

Nondeterminism means that from a given state and input symbol, the automaton may move to any one of several possible next states. ε-transitions allow moves without consuming input, so an NFA can explore multiple computation paths in parallel. A string is accepted if at least one computation path ends in an accepting state after consuming the entire input.

NFAs and deterministic finite automata (DFAs) recognize exactly the same class of languages: the regular languages. A DFA has at most one possible next state for each state and input symbol. Every NFA has an equivalent DFA, obtainable via the subset (powerset) construction; the resulting DFA may have exponentially more states.

NFAs are often more compact to design and are convenient for representing patterns described by regular expressions and for certain parsing and lexical analysis tasks. They can be extended with ε-transitions to simplify constructions, and in practice are typically simulated or converted to DFAs for efficient implementation.