Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-08-30
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 G.

[L1]

Useless symbols can be eliminated without changing the language, by Eliminating useless symbols preserves the generated language.

[L2]

Epsilon-productions can be eliminated except for the special start-symbol exception, by Epsilon-productions can be eliminated except possibly at the start symbol.

[L3]

Unit productions can be eliminated without changing the language, by Unit productions can be eliminated.

[L4]

Chomsky normal form allows only productions of the shapes listed in Chomsky normal form.

Proof

technique · direct
1.1

Apply [L1], [L2], and [L3] in order to obtain an equivalent grammar G1 in which every remaining production is nonunit and every ε-production is removed except possibly a start-symbol rule.

L1L2L3construct
2.1

For each terminal a that appears in a right-hand side of length at least 2, introduce a fresh variable Ta with production Taa, and replace that occurrence of a by Ta. This changes no generated word, because each use of Ta can immediately be expanded to the terminal a. After this step, every right-hand side is either a single terminal or a word of variables only.

constructstep 1.1
3.1

For each production AB1B2Bk with k3, introduce fresh variables C1,,Ck2 and replace the production by AB1C1,CiBi+1Ci+1  (1ik3),Ck2Bk1Bk. The middle family is empty when k=3, so that case is the two-rule chain AB1C1 and C1B2B3. 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.

constructstep 2.1
4.1

After steps 2.1 and 3.1, every production is either ABC, Aa, or the exceptional start-symbol rule Sε. Therefore [L4] says the resulting grammar is in Chomsky normal form, and the preceding steps preserved the language.

L4step 2.1step 3.1

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