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?