TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-12

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 reversal

Statement

If $L \subseteq Σ^{*}$ is context-free, then its reversal $L^{R} : = {w^{R} : w \in L}$ is also context-free.

Facts & Assumptions

Given: A context-free language $L$ .

[L1]

By Context-free grammars, a context-free grammar is a finite set of productions $A \to α$ with one variable on the left.

[L2]

By The language generated by a CFG, a language is context-free exactly when some CFG generates it.

[L3]

By Word reversal and language reversal, reversing a word reverses the order of its letters, and $L^{R}$ is the set of reversals of words of $L$ .

[L4]

By Derivations and parse trees correspond, parse trees and derivations determine exactly the generated words of a CFG.

Proof

technique · direct

1.1

Choose a grammar $G = (V, Σ, P, S)$ with $L = L (G)$ by [L2]. Define a new grammar $G^{R} = (V, Σ, P^{R}, S)$ by putting a production $A \to α^{R}$ in $P^{R}$ whenever $A \to α$ belongs to $P$ . This is again a context-free grammar by [L1].

L1L2givenconstruct

2.1

Mirror every parse tree of $G$ by reversing the left-to-right order of the children at each internal node. The mirrored tree uses exactly the reversed productions from step 1.1, so by [L4] it is a parse tree of $G^{R}$ . Its yield is the reversal of the original yield, by [L3]. Therefore $w \in L$ implies $w^{R} \in L (G^{R})$ . Mirroring back proves the converse implication.

L3L4step 1.1

3.1

Hence $L (G^{R}) = L^{R}$ , so $L^{R}$ is context-free by [L2].

L2step 2.1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

10 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

Alfred V. Aho, COMS W3261 CS Theory, Lecture 11 (standard reference, not scraped)