1
$\begingroup$

I'm stuck with this problem:

Given $L$ a CFL on the alphabet $\Sigma$. Prove that $L^r=\{x^r|x\in L\}$, where for each $a\in\Sigma$ and $y\in\Sigma^*$, $$\epsilon^r=\epsilon,$$ $$(ay)^r=y^ra,$$ is context free or not.

Since I don't have the alphabet I cannot think of a grammar that generates this language, so I decided to prove that it's not context free by applying the pumping lemma for CFL. So I started with the hypothesis that $L^r$ is context free, thus if $x\in L^r$ that $x^r\in L$.

Then I tried to find different possible strings that once pumped didn't belong anymore to $L^r$, but I'm not able to find such string.

Is this a bad aproach? Where am I wrong?

$\endgroup$
2
$\begingroup$

Informally, by construction $L^r$ consists of the strings in $L$ reversed. Since $L$ is context-free, it has a Grammar in Chomsky normal form. All production rules in this grammar will fall in one of three classes:

  1. $A \rightarrow BC$
  2. $A \rightarrow a$
  3. $S \rightarrow ε$

Thus by reversing the order of non-terminals in the RHS of all rules of category 1., a new grammar can be derived that produces $L^r$.

This new grammar is also in Chomsky normal form, thus $L^r$ is context-free.

$\endgroup$
  • $\begingroup$ Oh! I was so wrong... Anyway, thank you very much now I understand. $\endgroup$ – tokenizer Jul 26 '18 at 10:18
  • $\begingroup$ There is absolutely no need to use CNF here. Any context-free grammar would do. $\endgroup$ – Yuval Filmus Jul 26 '18 at 18:24

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.