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.

Unit productions can be eliminated

Statement

A unit production is a production $A \to B$ whose left- and right-hand sides are both single variables.

For every context-free grammar $G$ there exists a context-free grammar $H$ such that $L (H) = L (G)$ and $H$ has no unit productions.

Facts & Assumptions

Given: A context-free grammar $G$ .

[L1]

By Epsilon-productions can be eliminated except possibly at the start symbol, we may first replace $G$ by an equivalent grammar whose only possible $ε$ -production is a special start-symbol rule.

[L2]

The generated language is defined by derivability from the start symbol, by The language generated by a CFG.

Proof

technique · direct

1.1

Replace $G$ by an equivalent grammar $G_{1}$ as in [L1]. For variables $A, B$ , write $A ⇝ B$ when $A \Rightarrow_{G_{1}}^{*} B$ using only unit productions. Now form $H$ by deleting all unit productions and, whenever $A ⇝ B$ and $B \to α$ is a nonunit production of $G_{1}$ , adding the copied production $A \to α$ .

L1construct

2.1

Any derivation of a terminal word in $G_{1}$ can be compressed to a derivation in $H$ by replacing each maximal block of unit productions followed by one nonunit production $B \to α$ with the copied rule $A \to α$ placed into $H$ . Therefore every word of $L (G_{1})$ lies in $L (H)$ .

step 1.1L2

2.2

Conversely, every copied production $A \to α$ of $H$ came from some unit chain $A ⇝ B$ in $G_{1}$ and a nonunit production $B \to α$ of $G_{1}$ . Expanding one use of $A \to α$ back into that unit chain followed by $B \to α$ turns any derivation in $H$ into a derivation in $G_{1}$ . So every word of $L (H)$ lies in $L (G_{1})$ .

step 1.1L2

3.1

Steps 2.1 and 2.2 give $L (H) = L (G_{1}) = L (G)$ , and $H$ has no unit productions by construction.

L1step 2.1step 2.2∎

Depends on

Used by

Every context-free language has an equivalent grammar in Chomsky normal form Theorem

Dependency tree · two levels

5 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)