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.
Context-free languages are closed under union, concatenation, Kleene star, and homomorphism
Statement
If are context-free languages over an alphabet , and if is an alphabet map, then the following languages are context-free:
- ,
- ,
- ,
- .
Facts & Assumptions
Given: Context-free languages and , together with grammars and generating them, and an alphabet map .
A language is context-free exactly when it is generated by some context-free grammar, by The language generated by a CFG.
The induced word map is obtained by replacing each letter of a word by the word and concatenating the results, by Alphabet maps into and their induced maps on words.
Proof
Rename variables of and apart, and add a fresh start variable . The grammar with productions of and together with and generates exactly . Similarly, adding only the bridge rule yields a grammar for the concatenation .
For Kleene star, keep and add a fresh start variable with productions and . Repeating the second rule any finite number of times and then using generates exactly a concatenation of finitely many words from , so the new grammar generates .
For homomorphism, first rename the variables of the chosen grammar for so that they are disjoint from . Then replace every terminal letter occurring in a production by the word , keeping that renamed variable set unchanged. The result is still a context-free grammar over , and if a derivation in the source grammar yields , then the corresponding derivation in the rewritten grammar yields by [L2].
Conversely, any terminal derivation in the rewritten grammar follows the same variable-expansion pattern as a terminal derivation in the renamed source grammar, because the only change was to replace each source terminal occurrence by its prescribed image word . Therefore the terminal word produced at the end is exactly the image under of a word of , so the new grammar generates exactly .
Steps 1.1, 1.2, 1.3, and 2.1 construct grammars for all four languages, so [L1] shows that context-free languages are closed under union, concatenation, Kleene star, and homomorphism.
Depends on
Used by
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
- John Watrous, Introduction to the Theory of Computing, Lecture 9 (standard reference, not scraped)
- Alfred V. Aho, COMS W3261 CS Theory, Lecture 11: Properties of CFL's (standard reference, not scraped)