patternMinor
Is this language a context-free language or not?
Viewed 0 times
thisfreelanguagecontextnot
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#151337, answer score: 8
Revisions (0)
No revisions yet.