# Showing that $\mathscr{L}$ is not context-free-grammar language

Let $"t"$ and $"s"$ be a words we will say that two words are "completly different" if for all $1\leqslant i\leqslant |t|$ the $i$ letter in $t$ diffrent from the $i$ letter in $s$.

Prove that the language $\mathcal{L}=\{ts|t,s\in \{0,1\}^*,|t|=|s|,t,s \text{ completly different} \}$ is not a free-context-language

Attempt :

Suppose that $\mathcal L$ is regular so exists a word '$z=uxvyw$' with length of at least $n$ such that:

$(1)\,\,\,|xvy|\leqslant n$

$(2)\,\,\,|xy|\geqslant 1$

$(3)\,\,\,ux^ivy^iw \in \mathcal L\,\,\,\,\,\,\,\,\,i\geqslant 0$

Now, let's choose the word $\color{blue}{z=0^n1^n}$ it is obvious that $|z|\geqslant n$ so we can use $(1)-(3)$

$z=0^{\alpha}0^{\beta}0^{\gamma}0^{\lambda}1^n$

So $\alpha+\beta+\gamma+\lambda=n$

I am stuck here.

Consider $z=0^p1^p0^p1^p0^p1^p\in \mathcal{L}$ since $|z|>p$, there are $u,v,w,x,y$ such that $z=uvwxy,|vwx|\leqslant p, |vx|>0$ and $uv^iwx^iy\in \mathcal{L}$

$vwx$ must straddle the midpoint of $z$ there are fore possibilities:

• $vwx$ is in $0^p$ part.

• $vwx$ is in $1^p$ part.

• $vwx$ is in $1^p0^p$ part.

• $vwx$ is in $0^p1^p$ part.

Thus, it is not of the form that we want

For $i=2$ $z\notin \mathcal{L}$

• Unfortunately, you don't give us much of an attempt to work with. Plus, your ansatz is flawed already; be more careful reading the theorem! I recommend you check out our reference question and just try out some candidate words. Seeing what works and what does not, you gain experience that helps you picking suitable words faster. – Raphael Jan 9 '16 at 9:32
• Your attempt is still incomplete. Have you read the reference question? You have to prove for all partitionings of the word as per the PL that something bad happens. – Raphael Jan 9 '16 at 9:41
• By the way, community votes please: is this a duplicate of the reference question? As long as the problem is "please explain the Pumping lemma to me", it provides an elaborate answer. – Raphael Jan 9 '16 at 9:42
• @Raphael yes, I read the referance question, it is almost like to read in wikipedia about the pumping lemma. – 3SAT Jan 9 '16 at 9:44
• So? To be blunt, I'm afraid that if you don't understand these resources, you won't understand answers either. – Raphael Jan 10 '16 at 20:49

• You are choosing a decomposition for $z$. That is wrong too. You have to prove that the decomposition does not exist to get the contradiction. If you read the answer I linked you can easily think of a decomposition so your word $z=a^nb^n$ is useless. You will have to try another word or try to generate a PDA to prove that $\mathscr{L}$ is CFL. – Renato Sanhueza Jan 9 '16 at 18:51
• It's seems that the word works fine but It is unnecessarily complex. I would use $\sigma=1^p0^p0^p1^p$ instead and remember that you have to explain why the four posibilities do not work. – Renato Sanhueza Jan 10 '16 at 16:37