# Subset construction from an NFA to a DFA

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

Use epsilon-NFA state subsets as DFA states, defining start, transitions and acceptance with epsilon closure to preserve the language.

mko-subset-construction-nfa-to-dfa · theorem · v0.10.0



## 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 complete reachable-subset DFA of an epsilon-NFA](https://ocme.evemisslab.com/en/derivations/derivation-mko-subset-construction-nfa-to-dfa-01/)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](https://ocme.evemisslab.com/en/mko/mko-nondeterministic-finite-automaton/) — Use epsilon-NFA semantics.
- [Deterministic finite automaton](https://ocme.evemisslab.com/en/mko/mko-finite-automaton/) — The target structure is a DFA.
- [Subset](https://ocme.evemisslab.com/en/mko/mko-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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/subset-construction-nfa-to-dfa.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-subset-construction-nfa-to-dfa/index.md)