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 language has an equivalent grammar in Chomsky normal form
Statement
Every context-free grammar has an equivalent context-free grammar in Chomsky normal form.
Facts & Assumptions
Given: A context-free grammar .
Useless symbols can be eliminated without changing the language, by Eliminating useless symbols preserves the generated language.
Epsilon-productions can be eliminated except for the special start-symbol exception, by Epsilon-productions can be eliminated except possibly at the start symbol.
Unit productions can be eliminated without changing the language, by Unit productions can be eliminated.
Chomsky normal form allows only productions of the shapes listed in Chomsky normal form.
Proof
Apply [L1], [L2], and [L3] in order to obtain an equivalent grammar in which every remaining production is nonunit and every -production is removed except possibly a start-symbol rule.
For each terminal that appears in a right-hand side of length at least , introduce a fresh variable with production , and replace that occurrence of by . This changes no generated word, because each use of can immediately be expanded to the terminal . After this step, every right-hand side is either a single terminal or a word of variables only.
For each production with , introduce fresh variables and replace the production by The middle family is empty when , so that case is the two-rule chain and . One use of the original long rule is equivalent to this forced chain of binary rules, and conversely the binary chain produces exactly the same string of variables.
After steps 2.1 and 3.1, every production is either , , or the exceptional start-symbol rule . Therefore [L4] says the resulting grammar is in Chomsky normal form, and the preceding steps preserved the language.
Depends on
Used by
Dependency tree · two levels
7 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
- John Watrous, Introduction to the Theory of Computing, Lecture 8 (standard reference, not scraped)
- Jean Gallier and Jocelyn Quaintance, Introduction to the Theory of Computation: Some Notes for CIS511 (standard reference, not scraped)