0
$\begingroup$

Prove that the following language is non-context free by using the pumping lemma
L2 = {w#x | w is a substring of x for w, x ∈ {0, 1}}.

Assume that L2 is context-free. Let p be the pumping length of L2 and s = 10p#10p. By the pumping lemma for context-free languages, we have s = uvxyz satisfying the following:
• $uv^ixy^i$ z ∈ L2 for i = 0, 1, 2, . . ., and
• |vy| > 0, and
• |vxy| ≤ p.
We do a case analysis here.
• Either v or y contains #. Then uvvxyyz contains more than one #’s, which contradicts uvvxyyz ∈ L2.
• vxy occurs before #. Then uvvxyyz = w1#w2 for some w1, w2 such that w1 is longer than w2. Therefore, w1 cannot be a substring of w2, contradicting uvvxyyz ∈ L2.
• vxy occurs after #. Then uxz = w1#w2 for some w1, w2 such that w1 is longer than w2. Therefore, w1 cannot be a substring of w2, contradicting uxz ∈ L2.
• x straddles #. We have two subcases.
– y begins with 1. Then uxz = w1#w2 for some w1, w2 such that w1 begins with 1 and w2
consists of 0’s. Therefore, w1 cannot be a substring of w2, contradicting uxz ∈ L2.
– y = $\epsilon$. Then uvvxyyz = w1#w2 for some w1, w2 such that w1 is longer than w2. Therefore, w1 cannot be a substring of w2, contradicting uvvxyyz ∈ L2. Therefore, L2 is not context-free.

Hello everyone, I am having a hard-time understanding how the pumping lemma for context free languages work when it comes to splitting the task into cases. I have the following questions:

How do we see all the cases that we have to cover?

I am having troubles understanding the last step of the latter proof. What does straddle mean in that context?.

why do we need to cover all those cases if just one case would contradict the whole thing?

$\endgroup$
  • $\begingroup$ "$x$ straddles #" simply means that it starts to its left of it and ends to its right. $\endgroup$ – Fabio Somenzi Mar 10 '17 at 7:18
  • $\begingroup$ Yes(.............) $\endgroup$ – daniel Mar 10 '17 at 7:20
  • $\begingroup$ You need all the cases because you want to prove that you've found a word that, when pumped, is definitely not in $L2$. Since you can only conjecture how this word is decomposed into $u$, $v$, $x$, $y$, and $z$, you need to consider all ways in which that may happen. $\endgroup$ – Fabio Somenzi Mar 10 '17 at 7:22
  • $\begingroup$ What does finding a word mean?. By proving the cases, we are finding different words that disprove the claim right? $\endgroup$ – daniel Mar 10 '17 at 7:23
  • $\begingroup$ No, as I clarified in my edit, we are considering all ways in which it may be split. The pumping lemma only guarantees that there is some way in which our word $s$ may be written as $uvxyz$. $\endgroup$ – Fabio Somenzi Mar 10 '17 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.