Here's the problem:
Prove that the context-free languages are closed under reversal.
Here's my work:
We want to show that if $L$ is a context-free language, then $L^R$ is a context-free language. So let $G$ be the context-free grammar that generates $L$. We construct a new context-free grammar $G'$ as such: for every production $X \rightarrow x$ in $G$, where $X$ is a variable and $x$ is a string of variables or terminals, we add to $G'$ the production $X \rightarrow x^R$. Thus, $G$ generates a word $w$ if and only if $G'$ generates a word $w^R$. Thus, $G'$ generates the language $L^R$, and as $G'$ is a CFG, $L^R$ must be a context-free language.
Is my proof sufficient? Are there any details I should add? Would I want to show "Thus, $G$ generates a word $w$ if and only if $G'$ generates a word $w^R$" by induction?
Best Answer
It depends on the level of rigor that’s required. If you want (or need) to be a bit more rigorous, you could sketch an argument by induction on the length of a derivation. The key point is that if $w=uXv$ is derivable in $G$, $w^R=v^RXu^R$ is derivable in $G'$, and $G$ has a production $X\to x$ that allows the further derivation $w\Rightarrow uxv$, then the production $X\to x^R$ in $G'$ allows the further derivation $w^R\Rightarrow v^Rx^Ru^R=(uxv)^R$.