$L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$

Question

Consider the following language:

$$L= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$$

How we can show that $L$ isn't Contextfree?

Answer 1

This one is a middling difficult application of the pumping lemma for context-free languages, so perhaps it’s a good one to write up completely as a kind of tutorial.

Suppose that $L_a$ is context-free; the pumping lemma then says that there is a positive integer $p$, the pumping length, such that if $s\in L_a$, and $|s|\ge p$, then we can decompose $s$ into five parts, as $s=uvwxy$, in such a way that

• $|vwx|\le p$;
• $|vx|\ge 1$; and
• the string $uv^kwx^ky\in L_a$ for each integer $k\ge 0$.

(Here $|s|$ is the length of $s$, the number of symbols in $s$.)

The idea is to start with some string $s\in L_a$ such that $|s|\ge p$ and show that no matter how we break $s$ into five parts as $s=uvwxy$, there will be at least one integer $k\ge 0$ such that $uv^kwx^ky$ is not in $L_a$. If $L_a$ were really context-free, this would be impossible — that’s exactly what the pumping lemma tells us — so this would show that $L_a$ cannot be context-free.

The trick to using the pumping lemma successfully is finding a suitable string $s$ to start with. Experience helps here, and I can see that

$$s=(ba)^pba^pc(ba)^pba^p$$

is a good candidate. Suppose that we decompose $s$ as $s=uvwxy$, where $|vwx|\le p$ and $|vx|\ge 1$; there are several cases to consider depending on exactly where in $s$ the substring $vwx$ falls.

Case 1: $vwx$ lies entirely to the left of the $c$, somewhere in the first $(ba)^pba^p$.

Then changing $k$ from $1$ to anything else in $uv^kwx^ky$ changes the length of the substring to the left of the $c$ without changing the substring to the right of the $c$ at all, and the resulting string cannot possibly be in $L_a$: the substrings to the left and right of the $c$ cannot be identical. In this case the only $k\ge 0$ for which $uv^kwx^ky\in L_a$ is $k=1$. (This is more than we need: it’s enough to show that there is at least one $k\ge 0$ such that $uv^kwx^ky\notin L_a$, and sometimes that’s all that you can do.)

Case 2: $vwx$ lies entirely to the right of the $c$.

Then we can argue exactly as in Case 1 that the only $k\ge 0$ for which $uv^kwx^ky\in L_a$ is $k=1$, because changing $k$ from $1$ to any other non-negative integer changes the length of the substring to the right of the $c$ but does not change the substring to the left of the $c$.

Case 3: The $c$ is in the $v$ or the $x$ part of $s$.

Then $uv^kwx^ky$ will not contain any $c$ if $k=0$, and it will contain more than one $c$ if $k>1$. In either case $uv^kwx^ky\notin L_a$, and once again we find that the only $k\ge 0$ for which $uv^kwx^ky\in L_a$ is $k=1$.

Case 4: The $c$ is in the $w$ part of $s$.

This is the most difficult case, because $v$ lies to the left of $c$, and $x$ lies to the right of $c$, so that changing $k$ in $uv^kwx^ky$ affects both copies of $(ba)^pba^p$. It’s conceivable, therefore, that changing $k$ affects both copies in the same way, so that $uv^kwx^ky$ actually is in $L_a$ for each $k\ge 0$. In fact, however, I chose $s$ so that this would not happen.

Let $r=|v|,s=|w|$, and $t=|x|$; we know that $r+s+t=|vwx|\le p$, so $r\le p$, and therefore $v=a^r$: $v$ must be part of that $a^p$ immediately to the left of $c$ in $s$. Similarly, $t\le p$, so $x$ must be a substring of the $(ba)^p$ immediately to the right of the $c$, and the final $ba^p$ of $s$ must be part of $y$. This means that $uv^2wx^2y$ has $(ba)^pba^{p+r}$ to the left of the $c$ but still ends in $ba^p$, since replacing $x$ by $x^2$ does not affect the final $ba^p$. This means that if $r>0$, the parts of $uv^2wx^2y$ to the left and right of the $c$ aren’t the same, and $uv^2wx^2y\notin L_a$.

If $r=0$, then the requirement that $|vx|\ge 1$ ensures that $t>0$. But now we’re essentially back in Case 2: changing $k$ in $uv^kwx^ky$ has no effect on the part of the string to the left of the $c$, but it changes the length of the part to the right of the $c$. Consequently, $uv^kwx^ky\in L_a$ only when $k=1$.

We’ve now shown that in every case, no matter where in $s$ the substring $vwx$ lies, it is not true that $uv^kwx^ky\in L_a$ for each $k\ge 0$, and therefore $L_a$ cannot be context-free after all.

---

You might ask how I came up with the string $s$. I need a string in $L_a$, so it must have the form $zcz$ for some $z\in\{a,b\}^*$. It must have length at least $p$. And finally, no matter how I decompose it as $uvwxy$ with $|vwx|\le p$ and $|vx|\ge 1$, there must be some $k\ge 0$ such that $uv^kwx^ky\notin L_a$. I can see immediately that no matter how I choose $z$, if $vwx$ happens to be a substring of either copy of $z$, then changing $k$ from $1$ to any other non-negative integer will change the length of the substring on one side of $c$ while leaving the one the other side unchanged, and the resulting string definitely won’t be in $L_a$. This is my Case 1 and Case 2 above. It’s also clear to me that no matter how I choose $z$, Case 3 will be no problem, since changing $k$ will change the number of $c$’s in the string. It’s only to deal with Case 4 that I have to be careful in choosing $z$.

The key insight is that if the left end of $z$ looks very different from the right end, changes that take place near the centre of $zcz$ will affect the two copies of $z$ differently, and the resulting strings to the left and right of the $c$ will no longer be identical. There are many choices of $z$ that would accomplish this and are long enough; $(ba)^pba^p$ just happened to be the first that occurred to me.