0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is w@y mean? Is that concatenation? $\endgroup$ – Theo Bendit Oct 29 '18 at 0:37
  • $\begingroup$ Yes @TheoBendit $\endgroup$ – Jack Oct 29 '18 at 0:59
  • 1
    $\begingroup$ 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? $\endgroup$ – Theo Bendit Oct 29 '18 at 1:20
  • 1
    $\begingroup$ @theo: i think @ is a symbol. Otherwise, the question doesn't make much sense. $\endgroup$ – rici Oct 29 '18 at 3:31
  • $\begingroup$ @rici That's a good point. And now I can see how my first comment is ambiguous. $\endgroup$ – Theo Bendit Oct 29 '18 at 3:54
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $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$. $\endgroup$ – Peter Leupold Oct 30 '18 at 11:53
-1
$\begingroup$

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.

I have read "substring" as "factor," but this should even work if "substring" means "scattered substring."

$\endgroup$
  • $\begingroup$ If somebody downvotes this answer, because they find something wrong with it, I think they should state what they do not like. Then I can improve or delete my answer. $\endgroup$ – Peter Leupold Oct 30 '18 at 11:55

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.