Alphabeta Math
PropositionStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 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 unambiguous

Statement

Every deterministic context-free language has an unambiguous context-free grammar.

Facts & Assumptions

Given: A deterministic context-free language L.

[L2]

By A DPDA has at most one computation on each input, computations of a DPDA on one marked input are linearly ordered by extension and have at most one maximal computation.

[L3]

By If a PDA has at most one accepting computation on each word, the standard PDA-to-CFG construction is unambiguous, a PDA with at most one accepting computation on each word yields an unambiguous fragment-variable grammar for the same language.

Proof

technique · direct
1.1L1givenchoose

Choose a DPDA M recognizing L by [L1].

2.1L1step 1.1

Form an equivalent DPDA M^ that records whether the endmarker has been consumed. Before ⊣ it simulates M in a pre-endmarker copy of the state set; a transition consuming ⊣ enters the post-endmarker copy; and all subsequent ε-moves remain in that copy. Declare a post-endmarker copy accepting exactly when its underlying state lies in F, and delete every outgoing move from those accepting copies. This preserves determinism by [L1]: it only duplicates states and removes moves.

3.1L1step 2.1

The machine M^ recognizes the same language as M. Indeed, an accepting computation of M has consumed the marked input and hence reaches a post-endmarker accepting copy in M^; conversely, every accepting copy projects to an accepting configuration of M. Halting at the first such copy does not change whether that configuration is reachable.

3.2L2step 2.1

Every accepting computation of M^ is maximal because its accepting states have no outgoing moves. By [L2], there is therefore at most one accepting computation on each marked input.

4.1L3step 3.1step 3.2∎

Applying [L3] to M^ yields an unambiguous context-free grammar generating its language, which is L by step 3.1. Therefore every deterministic context-free language is unambiguous.

Depends on

Used by

Dependency tree · two levels

10 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