Subset construction from an NFA to a DFA

Mathematical statement

The DFA start is epsilon-closure({q0}). For subset S and symbol a, delta_D(S,a)=epsilon-closure(move(S,a)). A subset accepts exactly when its intersection with the NFA final set is nonempty. Empty subset is a legal dead state. Restriction to reachable subsets is allowed only when explicit. For every word prefix, the DFA subset equals all epsilon-closed NFA states reachable after that prefix; finite-word testing alone does not prove language equivalence.

Representative formula (exact TeX)

D(S,a)=E(M(S,a))

Assumptions

• The source epsilon-NFA has complete finite states, alphabet and transition relation; null denotes epsilon without input consumption.
• Subsets are canonically sorted, each symbol move is followed by epsilon closure, and traces begin at the epsilon-closed start.

Symbol scope

• D — DFA subset transition
• S — NFA state subset
• a — input symbol
• E — epsilon closure
• M — symbol move

Intuition, definition, and misconceptions

Close epsilon reachability for the start subset first.

Each symbol transition uses move followed by closure.

The arbitrary-prefix invariant, not finitely many accept/reject samples, supports general language equivalence.

Do not omit epsilon closure, delete the empty subset without handling dead transitions or claim language equivalence from finitely many test words.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Nondeterministic finite automaton — Use epsilon-NFA semantics.
• Deterministic finite automaton — The target structure is a DFA.
• Subset — Powerset states include the empty dead subset.

Verification boundary

Exact traces check each supplied word; general equivalence rests on prefix induction, not a sample count.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add regular-expression equivalence and automata minimization.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.