Use pumping lemma to prove grammar is not context free?

0
votes

I'm trying to prove that L={y#x|(y is a substring of x) ∧x,y∈{a,b}^* } is not context free using the pumping lemma, but I can't seem to do that. If 

|vy|≠ε ,|vxy|≤k , uv^n xy^n z∈L ,∀n≥0

Then either vxy has both a and b, or only b or only a.

How can I pump it in order to show that?

1
context-free-grammarformal-languagespumping-lemma
Isn't the pumping lemma only useful for showing a language isn't context free? ie: Even if it satisfies the conditions, it might still not be? – cHao
This is off topic for SO. It belongs on cstheory.stackexchange.com. – andand
@andand No, it does not; Theoretical Computer Science is only for research level TCS. This belongs to Computer Science which has in fact a good reference question on the matter. – Raphael

1 Answers

-2
votes

I agree with cHao, use the pumping lemma to show that a language isn't Context Free. To prove that a language is context free build a Context Free grammar or a DFA.

{y#x | y is a subset of x} over the alphabet {a, b}* does not appear to be context free just with a quick look.

Let s = (a|b)^p#(a|b)^(2p) so this is the string where p characters precede the # and 2p after to make this an easy subset.

We now need to decompose this string into x y^i z parts where |y| > 0 and |xy| = p. So the y must be made of any string of characters before the #. We can "pump up" this string now s.t. the first string before the # is larger than the second. This is no longer a subset of the second half. This is a contradiction so this language is not context free.