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?


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$.

  • $\begingroup$ That's reasonable. Cheers! $\endgroup$ – Newb Nov 21 '13 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.