ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 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.

One family of grammars realizing union, concatenation, star, and homomorphism

Example

Let $L_{1} = {a^{n} b^{n} : n \geq 0}, L_{2} = {c^{n} d^{n} : n \geq 0} .$ Standard grammars for them are $S_{1} \to a S_{1} b ∣ ε, S_{2} \to c S_{2} d ∣ ε .$

Then:

$L_{1} \cup L_{2}$ is generated by $S \to S_{1} ∣ S_{2}$ ,
$L_{1} L_{2}$ is generated by $S \to S_{1} S_{2}$ ,
$L_{1}^{*}$ is generated by $S \to ε ∣ S_{1} S$ ,
if $h (a) = 0$ and $h (b) = 1$ , then $\hat{h} (L_{1}) = {0^{n} 1^{n} : n \geq 0}$ .

Facts & Assumptions

Given: The two grammars for $L_{1}$ and $L_{2}$ , and the alphabet map with $h (a) = 0$ and $h (b) = 1$ .

[L1]

Context-free languages are closed under union, concatenation, Kleene star, and homomorphism, by Context-free languages are closed under union, concatenation, Kleene star, and homomorphism.

Verification

technique · direct

1.1given

The bridge rules $S \to S_{1} ∣ S_{2}$ and $S \to S_{1} S_{2}$ give the listed grammars for the union and concatenation constructions, and the rule $S \to ε ∣ S_{1} S$ lists any finite concatenation of words from $L_{1}$ .

1.2given

Replacing each terminal $a$ by $0$ and each terminal $b$ by $1$ turns the grammar for $L_{1}$ into one for ${0^{n} 1^{n} : n \geq 0}$ , which is exactly $\hat{h} (L_{1})$ .

2.1L1step 1.1step 1.2∎

These concrete constructions realize all four closure operations asserted in [L1].

Depends on

Context-free languages are closed under union, concatenation, Kleene star, and homomorphism

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

3 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 9 (standard reference, not scraped)