# Use Pumping Lemma to show that $L_7$ is not context-free

I was studying an old test and struggled to answer this question:

Let $$L_7$$ be the language $$\{ w@y \mid y \text{ is a substring of } w\}$$, where $$w, y \in \{c,d\}^*$$. Use the Pumping Lemma for context-free languages to show that $$L_7$$ is not context-free.

• What is w@y mean? Is that concatenation? – Theo Bendit Oct 29 '18 at 0:37
• Yes @TheoBendit – Jack Oct 29 '18 at 0:59
• I think there must be something wrong with this question; the language looks regular to me. In fact, if $y$ is allowed to be empty, then the language is simply $\{c, d\}^*$, as any such string $w$ could be written as $w\varepsilon$, where $\varepsilon$ is a substring of $w$. Even if you restrict $|y| \ge 1$, then the language is regular, since the only strings it doesn't include are $c^* d$ and $d^* c$. Does the $7$ in L7 play a part at all? – Theo Bendit Oct 29 '18 at 1:20
• @theo: i think @ is a symbol. Otherwise, the question doesn't make much sense. – rici Oct 29 '18 at 3:31
• @rici That's a good point. And now I can see how my first comment is ambiguous. – Theo Bendit Oct 29 '18 at 3:54

Suppose $$L7$$ satisfies the Pumping Lemma and let $$p$$ satisfy the conditions of the Pumping Lemma as stated on Wikipedia. Let $$s = c^pd^p @ c^pd^p \in L7$$ Note that $$|s| > p$$. Let $$u, v, w, x, y \in \{c, d, @\}^*$$ satisfy the conditions of the theorem (again, as stated on Wikipedia). First, let's consider the $$@$$. It obviously cannot lie in $$v$$ or $$x$$, as precisely one $$@$$ is allowed. It cannot lie in $$u$$, since considering $$n > 1$$ will make $$uv^nwx^ny$$ into the form $$a@b$$ where $$|a| < |b|$$. For the same reason, this time considering $$n = 0$$, we cannot have $$@$$ be in $$y$$. So, the $$@$$ must lie in $$w$$.
Since $$|vwx| \le p$$, it follows that $$v = d^m$$ and $$x = c^l$$ for some natural numbers $$m$$ and $$l$$. Then, it follows that $$uv^2wx^2y = c^pd^{p+m}@c^{p+l}d^p \notin L7,$$ which is a contradiction.
• $x$ can be empty (only $v$ and $x$ cannot be empty at the same time) and consequently $l=0$. Then $uv^2wx^2y = c^pd^{p+m}@c^{p+l}d^p = c^pd^{p+m}@c^p d^p \in L7$. But in that case $v$ must be non-empty and the case of $n=0$ leads to a word not in $L_7$. – Peter Leupold Oct 30 '18 at 11:53
I suggest to first intersect $$L_7$$ with the regular language $$ddd\cdot\{cc,cd,dc\}^+ddd@ddd\cdot\{cc,cd,dc\}^+ddd.$$ This takes away all strings where the substring is not the entire string (and some more). The result is $$\{ddd\cdot w\cdot ddd@ddd\cdot w\cdot ddd: w\in \{cc,cd,dc\}^+\}$$ which is very close to the copy language over three letters. Therefore you can apply the pumping lemma in the same way.