# prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free

Given that $$\#\notin \Sigma$$ and $$L\subseteq \Sigma^*\#\Sigma^*$$, prove that if $$L$$ is context-free language then $$L' = \{w_2\#w_1 \mid w_1\#w_2\in L\}$$ is context-free. I'm trying to prove this in this way:

1. because $$L$$ is context-free then $$G$$ is context-free grammar for $$L$$, then $$L(G)=L$$.
2. by showing that the reversed grammar $$F$$ of $$G$$ is the same grammar of $$L$$ and because $$G$$ is context-free then $$F$$ is context-free then $$L(F)=L'$$ is also context-free. but can't figure out a way to prove this, so I need help to do this.
• Note that $u\in L$ does not mean that the mirror word $\overline{u}\in L'$ (and conversely). May 15 at 11:38
• then I can't prove the question by this way? May 15 at 11:50
• Indeed, I don't think so. May 15 at 12:04
• any hint of another way that can work? May 15 at 12:07

There is a unique path in the derivation tree that leads from the axiom $$S$$ to the terminal symbol $$\#$$. An idea would be to turn this tree upside down along that path.

This solution follows the construction for the closure under cyclic shift for context-free languages, as suggested in the book by Hopcroft and Ullman.

• What do you mean by "to turn this tree upside-down along that path", is that to switch between the variables from the right side and left side? May 15 at 14:01
• I tried to explain that in the linked answer. May 15 at 14:05
• Yeah, very nice and simple explanation thank you so much! May 15 at 14:09