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.
Every context-free grammar has an equivalent PDA
Statement
Let be a context-free grammar. Then there exists a PDA such that
Facts & Assumptions
Given: A context-free grammar .
By The language generated by a CFG, is the set of terminal words derivable from the start variable .
By Leftmost and rightmost derivations, a leftmost derivation rewrites the leftmost variable at each production step.
By Acceptance by empty stack for a PDA, a PDA accepts by empty stack exactly when some full computation consumes the input and empties the stack.
Proof
Define a one-state PDA whose initial stack symbol is . If the top stack symbol is a variable and is a production of , the machine has an -move replacing by ; if the top stack symbol is a terminal , the machine may read an input symbol and pop it.
Every leftmost derivation of a word in yields an accepting computation of : keep the current sentential form on the stack, use the step from 1.1 to expand its leftmost variable exactly as the derivation does, and then match terminals against the input once only terminals remain on top. Therefore [L1], [L2], and [L3] give .
Conversely, every accepting computation of determines a leftmost derivation in , because the only -moves replace the current top variable by the right-hand side of one production and the only input-consuming moves match the current top terminal against the next input symbol. Reading those stack-replacement moves in order reconstructs a leftmost derivation of the accepted word. Hence .
Steps 2.1 and 2.2 prove .
Depends on
Used by
Dependency tree · two levels
8 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)