3
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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$.) $\endgroup$
    – John L.
    May 7 at 21:32
  • 1
    $\begingroup$ @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. $\endgroup$
    – Hendrik Jan
    May 7 at 23:28

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – John L.
    May 7 at 22:44
  • 2
    $\begingroup$ Regarding your comment's conjecture: $a^mb^nc^nd^m$. $\endgroup$
    – Kelly Bundy
    May 8 at 17:43
3
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ I was like "what the heck is this?" when I wrote my wrong answer. Now I see this answer is also simple and correct. $\endgroup$
    – John L.
    May 7 at 22:43
  • 1
    $\begingroup$ @JohnL. Thanks. Of course your final solution is a "deserved winner". $\endgroup$
    – Hendrik Jan
    May 7 at 23:02

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.