Finite automata (DFA / NFA)

Parent: regular-languages

A machine with a finite set of states and nothing else — read the input left to right, changing state; accept if you end in an accepting state.

DFA

A deterministic finite automaton is (Q, Σ, δ, q₀, F): states Q, alphabet Σ, transition δ : Q × Σ → Q, start q₀, accepting F ⊆ Q. On input w, follow δ symbol by symbol from q₀; accept iff the final state is in F.

NFA

A nondeterministic finite automaton lets δ return a set of next states (δ : Q × Σ → a subset of Q) and allows ε-moves (change state reading nothing). It accepts w iff some run ends in F.

Key facts

• NFA = DFA. The subset (powerset) construction turns an NFA into a DFA whose states are sets of NFA states — same language, but up to 2ⁿ states (the blow-up is real).
• Minimal DFA is unique. Merging indistinguishable states (Hopcroft's algorithm) yields a canonical minimum-state DFA; its state count equals the number of Myhill–Nerode classes.
• No memory. The only "state" is one of finitely many Q — so a finite automaton can't count unbounded quantities (hence not aⁿbⁿ, regular-languages).

Finite automata are the machine face of the regular class; the expression face is regular-expressions and the grammar face is regular-grammar, all tied together by regular-equivalences.