TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-09-08 (gpt-6-astra)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The subset construction preserves the recognized language

Statement

Let $N$ be an NFA with epsilon-moves, and let $D_{N}$ be its subset-construction DFA. Then $L (D_{N}) = L (N) .$

Facts & Assumptions

Given: An NFA $N$ and its subset-construction DFA $D_{N}$ .

[L1]

The finite-run transition and its word recursion are supplied by Acceptance of a word by an NFA and the recognized language. Put $E (S) = \hat{δ} (S, ε)$ and define $D_{N} = (P (Q), Σ, μ, E ({q_{0}}), G), μ (S, a) = E ⁣ (⋃_{q \in S} δ (q, a)), G = {S \subseteq Q : S \cap F \neq \emptyset} .$ The state set is finite by $∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$ , contains the indicated start state, and every transition is a uniquely defined subset of $Q$ . Thus this is a total DFA as in Deterministic finite automata, including the empty subset as a state. Its extended transition $μ^{*}$ exists by The extended transition function exists and is unique.

[L2]

By Acceptance of a word by a DFA and the recognized language, $D_{N}$ accepts $w$ exactly when its reached DFA state is accepting.

[L3]

By Acceptance of a word by an NFA and the recognized language, $N$ accepts $w$ exactly when its reachable state set on $w$ contains an accepting state.

Proof

technique · direct

1.1L1giveninduction

Induct on the word length to show $μ^{*} (E ({q_{0}}), w) = \hat{δ} (q_{0}, w)$ . For the empty word, both sides equal $E ({q_{0}})$ . If the equality holds for $w$ , the DFA recursion and [L1] give the value at $w a$ as $E (⋃_{q \in \hat{δ} (q_{0}, w)} δ (q, a))$ , which is exactly $\hat{δ} (q_{0}, w a)$ by the finite-run recursion. This proves the identity for every word.

2.1L2step 1.1

In the subset construction, a DFA state is accepting exactly when it contains an accepting NFA state. Therefore [L2] and step 1.1 show that $D_{N}$ accepts $w$ exactly when $\hat{δ} (q_{0}, w)$ contains an accepting state.

3.1L3step 2.1∎

By [L3], the condition from step 2.1 is exactly the statement that $N$ accepts $w$ . Thus $D_{N}$ accepts precisely the words that $N$ accepts, so $L (D_{N}) = L (N)$ .

Depends on

Used by

A language is regular if and only if some regular expression denotes it Theorem

Dependency tree · two levels

21 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Jean Gallier and Jocelyn Quaintance, Introduction to the Theory of Computation: Some Notes for CIS511 (standard reference, not scraped)
John Watrous, Introduction to the Theory of Computing, Lecture 3: Nondeterministic finite automata (standard reference, not scraped)