PropositionStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12

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.

Deterministic context-free languages are closed under complement

Statement

If $L \subseteq Σ^{*}$ is deterministic context-free, then $Σ^{*} ∖ L$ is also deterministic context-free.

Facts & Assumptions

Given: A deterministic context-free language $L \subseteq Σ^{*}$ .

[L1]

By Deterministic pushdown automata and deterministic context-free languages, some DPDA recognizes $L$ on marked inputs $w ⊣$ .

[F1]

The standard DPDA complementation construction first modifies a DPDA so that it reads the endmarker before accepting and has no dead-end or spurious-loop behavior, and then swaps the terminal accept/reject outcomes; the resulting DPDA recognizes exactly the marked complement. This is the construction proved in Kozen's Supplementary Lecture F and in Lewis-Papadimitriou Theorem 3.7.1.

Proof

technique · direct

1.1L1givenchoose

Choose a DPDA $M$ recognizing $L$ by [L1].

2.1F1step 1.1construct

Apply the complementation construction from [F1] to $M$ . It produces a DPDA $M^{c}$ over the same alphabet that accepts exactly the marked words $w ⊣$ not accepted by $M$ .

3.1L1F1step 2.1∎

Because $M^{c}$ recognizes exactly the marked complement of the language of $M$ , it recognizes $Σ^{*} ∖ L$ . Therefore $Σ^{*} ∖ L$ is deterministic context-free.

Depends on

Deterministic pushdown automata and deterministic context-free languages

Used by

FALSE: swapping the accepting states of a DPDA automatically complements its language False statement

Dependency tree · two levels

3 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

Dexter C. Kozen, Automata and Computability (standard reference, not scraped)
Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation, Theorem 3.7.1 (standard reference, not scraped)