Finite Automata & Regular Expressions

A finite automaton recognizes an unbounded input with bounded memory. Its state is not merely a node in a picture: it is the complete summary of the prefix already read that can still affect the answer. Regular expressions describe the same class of languages algebraically, while residual languages and Myhill–Nerode equivalence explain why the necessary states exist and when no finite number can suffice.

This chapter develops those views as one connected mechanism. A single running language will move through a deterministic automaton, a nondeterministic automaton, a regular expression, derivatives, and residual equivalence; each conversion comes with the invariant that makes it correct.

Words, languages, and three kinds of emptiness #

An alphabet $\Sigma$ is a finite set of symbols. A word is a finite sequence of symbols from $\Sigma$; $\Sigma^*$ is the set of all such words, including the empty word $\varepsilon$. A language is any subset $L\subseteq\Sigma^*$.

Three notations that look like “nothing” have different meanings:

A missing transition is different again. It may be shorthand for rejection in a partial diagram, but a formally complete DFA has a transition for every state/symbol pair, usually by routing otherwise missing cases to a rejecting sink.

Deterministic finite automata #

Extend the one-symbol transition to words:

$$\delta^*(q,\varepsilon)=q, \qquad \delta^*(q,wa)=\delta(\delta^*(q,w),a).$$

The automaton accepts $w$ exactly when $\delta^*(q_0,w)\in F$. It does not accept merely because it visited an accepting state partway through: the entire word must be consumed.

Worked invariant: words ending in 01 #

Let

$$L_{01}=\{w\in\{0,1\}^*\mid w\text{ ends in }01\}.$$

Three distinct prefix summaries are sufficient:

flowchart LR
  start([start]) --> A(("q∅"))
  A -- "0" --> B(("q0"))
  A -- "1" --> A
  B -- "0" --> B
  B -- "1" --> C((("q01 · accept")))
  C -- "0" --> B
  C -- "1" --> A

The diagram is correct because the state labels are invariants. For the empty prefix, $q_\varnothing$ has the claimed meaning. Each table entry preserves the appropriate suffix information after appending one symbol. At end of input, exactly the prefixes in state $q_{01}$ end in 01. This induction pattern—base case, one-symbol preservation, final interpretation—is the reusable proof technique behind hand-built automata.

Nondeterminism tracks possible runs #

A nondeterministic finite automaton replaces the single next state by a set of possibilities:

$$\Delta:Q\times\Sigma\to\mathcal P(Q).$$

After a word, the machine occupies a set of states. The word is accepted when at least one possible run ends in an accepting state. A branch that gets stuck does not reject the word if another branch succeeds.

For $L_{01}$, an NFA can remain in a scanning state $n_s$ on either bit and, whenever it sees 0, also guess that this 0 begins the final suffix:

The accepting branch must finish exactly at the end of the word. Earlier guesses die when more input remains; that is harmless because $n_s$ continues scanning.

Some NFA definitions also permit $\varepsilon$-transitions, which change state without consuming input. That is an explicit extension, not a silent property of every NFA definition. For an $\varepsilon$-NFA, define the epsilon-closure $E(S)$ as all states reachable from $S$ using only $\varepsilon$-transitions; close the initial set and every post-symbol set under $E$.

Subset construction makes the uncertainty explicit #

The deterministic simulation has one state for each NFA-state set it may need to remember. If the current subset is $S$ and the next symbol is $a$, then

$$\delta_D(S,a)=\bigcup_{q\in S}\Delta(q,a).$$

For an $\varepsilon$-NFA, use $E(\bigcup_{q\in S}\Delta(q,a))$ and begin at $E(\{q_0\})$. A subset is accepting iff it intersects the NFA's accepting set.

For the NFA above, only three subsets are reachable:

The correctness invariant is exact:

$$\delta_D^*(\{q_0\},w) = \{q\in Q\mid\text{the NFA has a run from }q_0\text{ to }q\text{ labeled }w\}.$$

The base case is the initial set. For the inductive step, appending $a$ follows every $a$-transition from every state reachable after $w$, which is precisely the union in the construction. Therefore the subset intersects $F$ exactly when the NFA has an accepting run.

An $n$-state NFA has $2^n$ possible subsets, so determinization has that upper bound. It is not a prediction that all $2^n$ states will be reachable: the example has eight possible subsets but only three reachable ones.

Regular expressions are language algebra #

A formal regular expression denotes a language. Its atoms are:

$$L(\varnothing)=\varnothing, \qquad L(\varepsilon)=\{\varepsilon\}, \qquad L(a)=\{a\}\quad(a\in\Sigma).$$

The constructors are union, concatenation, and Kleene star:

$$\begin{aligned} L(R\mid S) &= L(R)\cup L(S),\\ L(RS) &= \{xy\mid x\in L(R),\ y\in L(S)\},\\ L(R^*) &= \bigcup_{k\ge 0}L(R)^k. \end{aligned}$$

Because the $k=0$ term is $\{\varepsilon\}$, every starred expression contains the empty word. Concatenation binds more tightly than union, and star binds to its immediate operand, so (0|1)*01 denotes exactly $L_{01}$.

Two expressions are equivalent when they denote the same language, not when their syntax trees match. For example, $R\mid R$ and $R$ are semantically equivalent even though one has more syntax.

Why automata and regular expressions have equal power #

Kleene's theorem is constructive in both directions.

Expression to automaton #

Build small $\varepsilon$-NFAs for $\varnothing$, $\varepsilon$, and each symbol. Then combine them recursively:

• Union: a fresh start has epsilon paths to both alternatives; their accepting paths lead to a fresh accept state.
• Concatenation: epsilon-connect each accepting state of the first automaton to the second's start.
• Star: a fresh start can accept immediately or enter the body; completion can exit or loop back.

Each construction mirrors the corresponding language operation. An accepting path through the union chooses one operand; through concatenation it splits into one path for each factor; through star it splits into zero or more body paths. Structural induction over the expression proves correctness. Epsilon elimination and determinization may follow, but they are not what makes the construction correct.

Automaton to expression #

A generalized NFA labels an edge by a regular expression rather than one symbol. Add a unique start and accept state, then eliminate internal states. When removing $k$, update every remaining edge $i\to j$ by

$$R_{ij}\ \leftarrow\ R_{ij}\mid R_{ik}(R_{kk})^*R_{kj}.$$

The two alternatives are exactly the paths that avoid $k$ and the paths that enter $k$, loop there zero or more times, and leave. The invariant is that each label denotes all paths between its endpoints whose eliminated internal states come from the set processed so far. Once only start and accept remain, their edge denotes the automaton's language.

Elimination order can radically change expression size without changing its denotation. A larger result is not a different language.

Derivatives turn prefixes into states #

The left derivative of a language $L$ by a word $u$ is its residual future:

$$u^{-1}L=\{v\in\Sigma^*\mid uv\in L\}.$$

Brzozowski's derivative $D_a(R)$ is a regular expression denoting $a^{-1}L(R)$. Define nullable as the predicate $\nu(R)$ that is true exactly when $\varepsilon\in L(R)$. Then the central rules are:

$$\begin{aligned} D_a(R\mid S)&=D_a(R)\mid D_a(S),\\ D_a(RS)&=D_a(R)S\mid \begin{cases} D_a(S),&\nu(R),\\ \varnothing,&\text{otherwise}, \end{cases}\\ D_a(R^*)&=D_a(R)R^*. \end{aligned}$$

Differentiate successively by each symbol of $w$. Then

$$w\in L(R)\quad\Longleftrightarrow\quad \nu(D_w(R)).$$

This is already a DFA construction: normalized derivative languages are states, taking a derivative is a transition, and nullable derivatives are accepting. The word “normalized” matters. Raw expression syntax can grow indefinitely even though a regular language has only finitely many distinct residual languages.

For (0|1)*01, the semantic derivative states correspond to the same three questions as the hand-built DFA:

The automaton state is therefore literally a future language.

Myhill–Nerode explains minimality #

For a language $L$, define right-context equivalence on prefixes:

$$x\equiv_L y \quad\Longleftrightarrow\quad \forall z\in\Sigma^*,\ xz\in L\iff yz\in L.$$

Two prefixes are equivalent when no future suffix can distinguish them. The relation is right-invariant: appending the same symbol to equivalent prefixes keeps them equivalent.

Why both directions hold:

1. Any DFA puts two prefixes in the same class whenever they reach the same state, because all future transitions are then identical. A finite DFA therefore induces only finitely many future behaviors.
2. If $\equiv_L$ has finitely many classes, use those classes as states. Appending $a$ sends $[x]$ to $[xa]$; right invariance makes this well-defined. Mark $[x]$ accepting iff $x\in L$.

For $L_{01}$, the three DFA states are pairwise distinguishable. The empty suffix separates $q_{01}$ from each rejecting state. Suffix 1 separates $q_0$ from $q_\varnothing$: a prefix ending in 0 becomes accepted, while one with no useful trailing 0 does not. Therefore no two-state DFA can recognize the language.

A nonregularity proof #

Let $E=\{0^n1^n\mid n\ge 0\}$. Prefixes $0^i$ and $0^j$ with $i\ne j$ are distinguishable: suffix $1^i$ completes $0^i$ into a member of $E$ but does not complete $0^j$. There are infinitely many distinguishable prefixes, so $E$ is not regular.

This proof identifies the missing memory: a finite machine would need to retain an unbounded exact count of preceding zeros.

Minimization is quotienting by observable behavior #

For a complete DFA, remove unreachable states and partition the remaining states into classes that cannot be distinguished by any continuation. A refinement algorithm starts with accepting versus rejecting states and repeatedly splits a block when some input sends its members to different blocks.

The stable blocks are the residual equivalence classes. Merging within each block preserves the language; merging across blocks creates a distinguishing suffix on which behavior changes.

Products give closure and counterexamples #

For complete DFAs $A$ and $B$ over the same alphabet, their synchronous product has states $Q_A\times Q_B$ and transition

$$\delta((p,q),a)=(\delta_A(p,a),\delta_B(q,a)).$$

After any word $w$, the product is at the pair of component states reached by $w$. That invariant makes several Boolean operations differ only in the accepting predicate:

Complement is simpler: flip accepting and rejecting states of a complete deterministic automaton. For a partial diagram, first make every omitted transition explicit by adding a rejecting sink; otherwise a missing run has no state whose acceptance can be flipped.

The product has at most $|Q_A||Q_B|$ states, but only reachable pairs need be generated. Products, cascade wiring, and decomposition develops this construction in depth.

Decision procedures are graph problems plus invariants #

Once a language is represented by a finite graph, several questions become finite searches:

• Emptiness: is any accepting state reachable from the start?
• Equivalence: is any accepting state reachable in the symmetric-difference product?
• Inclusion: is $L(A)\setminus L(B)$ empty?
• Finiteness: is there a reachable cycle from which an accepting state is reachable?

To explain a failed equivalence check, retain each visited product state's predecessor and incoming symbol. The first reached symmetric-difference state reconstructs a shortest distinguishing word. A Boolean answer becomes a reproducible counterexample.

Formal regex and regex engines are different layers #

The algebra above defines whole languages using union, concatenation, and star. A concrete regex specification also chooses syntax, search scope, and match-selection policy. POSIX, for example, separately specifies Basic and Extended Regular Expressions and a leftmost-longest selection rule.

Other engines may add captures, backreferences, lookaround, or implementation-specific search behavior. Three questions must therefore remain separate:

1. Which set of strings does the pattern notation denote?
2. If several substrings qualify, which match is selected?
3. Which algorithm finds it, and with what performance behavior?

The product name “regex” does not prove that every feature stays within regular-language expressive power.

Diagnostic checklist #

• Did you distinguish $\varepsilon$, $\{\varepsilon\}$, and $\varnothing$?
• Does a DFA consume the entire word before acceptance is tested?
• For an NFA, did you retain every possible current state rather than choose one branch greedily?
• If epsilon transitions exist, did you close the start and every post-symbol set?
• Does each hand-designed state have a prefix invariant that every outgoing transition preserves?
• In subset construction, are you counting only reachable subsets when describing the actual result?
• Before complement, is the automaton deterministic and complete?
• Are two regular expressions being compared by denotation rather than syntax?
• Can a claimed merge survive every continuation, or is there a distinguishing suffix?
• Is a programming regex claim really about language expressiveness, match selection, or engine execution?

The unifying view is residual behavior: DFA states, determinized NFA subsets, normalized derivatives, and Myhill–Nerode classes all record what continuations remain possible after a prefix. Once that view is internalized, the constructions stop looking like unrelated recipes.