# Is this language a context-free language or not?

I try to determine if the following statement is true:

for any given language $$L \subseteq A^*$$ if $$L$$ is a context-free language then $$L_1 = \{u^Rv^R \ | \ uv \in L, |u|=|v| \}$$ is also a context-free language.

Initially I tried to come up with a counterexample but now I start to believe this statement could be true. As far as I know I could prove that language is not a context-free language using pumping lemma but how can I prove this language is a context-free one (if it's true)? I would be grateful for any hints.

Edit: I found interesting and maybe related question: Show that { xy ∣ |x| = |y|, x ≠ y } is context-free

Based on the question from the above link I started to wonder if language $$L = \{uv \ | \ |u|=|v| \}$$ is a context-free language only if $$u \neq v$$. If it's true then answer to my question is obvious.

• Consider $L_2=\{vu \ | \ uv \in L, |u|=|v| \}$. Since $L_2=L_1^R$, $L_1$ is context-free iff $L_2$ is context-free. So the statement in the question is the same as "$L$ is context-free iff $L_2$ is context-free", assuming all words in $L$ are of even length. ($L=(L_2)_2$.) May 7 at 21:32
• @JohnL. Interesting observation. I would bet that your $L_2 = \{ vu \mid uv\in L, |u|=|v| \}$ is the topic of an old question here, but cannot find it. May 7 at 23:28

No, $$L_1$$ is not necessarily context-free.

For example, let $$L=\{0^n1^{3n}\mid n\ge0\}$$.

If $$uv=0^n1^{3n}$$ and $$|u|=|v|$$, then $$u=0^n1^n$$ and $$v=1^{2n}$$. We have $$u^Rv^R=1^n0^n1^{2n}$$.

So, $$L_1=\{1^n0^n1^{2n}\mid n\ge0\}$$, which is not context-free.

• Conjecture: If all words in $L$ are of even length and both $L$ and $L_1$ are context-free, then both of them are regular. May 7 at 22:44
• Regarding your comment's conjecture: $a^mb^nc^nd^m$. May 8 at 17:43

I do not think the linked question is relevant.

Consider the context-free language $$L = \{a^n b^n c^m d^m \mid m,n\ge 0\}$$.

Let us consider an example string, $$uv = a^3 b^3 c^8 d^8$$. Assuming $$u$$ and $$v$$ are of equal length, $$u= a^3 b^3 c^5$$ and $$v= c^3 d^8$$. Thus $$u^Rv^R = c^5 b^3 a^3 d^8 c^3$$. We see that the letters are in a rather scrambled order.

Now study the minimally scrambled strings in the new language, meaning $$L_1 \cap b^* a^* d^* c^*$$.

What is that language?

• I was like "what the heck is this?" when I wrote my wrong answer. Now I see this answer is also simple and correct. May 7 at 22:43
• @JohnL. Thanks. Of course your final solution is a "deserved winner". May 7 at 23:02