42
$\begingroup$

I remember coming across the following question about a language that supposedly is context-free, but I was unable to find a proof of the fact. Have I perhaps misremembered the question?

Anyway, here's the question:

Show that the language $L = \{xy \mid |x| = |y|, x\neq y\}$ is context free.

$\endgroup$
  • 5
    $\begingroup$ Oh, that's a good one! <3 $\endgroup$ – Raphael Mar 13 '12 at 13:01
35
$\begingroup$

Claim: $L$ is context-free.

Proof Idea: There has to be at least one difference between the first and second half; we give a grammar that makes sure to generate one and leaves the rest arbitrary.

Proof: For sake of simplicity, assume a binary alphabet $\Sigma = \{a,b\}$. The proof readily extends to other sizes. Consider the grammar $G$:

$\qquad\begin{align} S &\to AB \mid BA \\ A &\to a \mid aAa \mid aAb \mid bAa \mid bAb \\ B &\to b \mid aBa \mid aBb \mid bBa \mid bBb \end{align}$

It is quite clear that it generates

$\qquad \mathcal{L}(G) = \{ \underbrace{w_1}_k x \underbrace{w_2v_1}_{k+l}y\underbrace{v_2}_l \mid |w_1|=|w_2|=k, |v_1|=|v_2|=l, x\neq y \} \subseteq \Sigma^*;$

the suspicious may perform a nested induction over $k$ and $l$ with case distinction over pairs $(x,y)$. Now, $w_2$ and $v_1$ commute (intuitively speaking, $w_2$ and $v_1$ can exchange symbols because both contain symbols chosen independently from the rest of the word). Therefore, $x$ and $y$ have the same position (in their respective half), which implies $\mathcal{L}(G) = L$ because $G$ imposes no other restrictions on its language.


The interested reader may enjoy two follow-up problems:

Exercise 1: Come up with a PDA for $L$!

Exercise 2: What about $\{xyz \mid |x|=|y|=|z|, x\neq y \lor y \neq z \lor x \neq z\}$?

$\endgroup$
  • $\begingroup$ If we use this grammar, we can generate a string like: $ S \rightarrow AB $ $ A \rightarrow a $ $ B \rightarrow bBa, then B \rightarrow b $ After that, we got a S as abba! This is not equal to the raw language L, is there a mistake here? $\endgroup$ – George.Zhao Mar 15 at 7:28
  • $\begingroup$ @George.Zhao I don't follow. Cleary, $abba \in L$ with $x = ab$ and $y=ba$? $\endgroup$ – Raphael Mar 15 at 9:14

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.