Reputation: 6992
My question is:
Let L = { x in {a,b}* | x has an equal number of a's and b's}
I know this is a context free language because I can create a grammar for it (e is epsilon):
S -> aX | bY | e
X -> bS | aXX
Y -> aS | bYY
You can also prove it is context free by using the fact that a context free language intersected with a regular language is context free.
Since it is a context free language, according to the pumping lemma for CFL's, any string longer than the pumping length p should be able to be pumped. However, if I choose the string s = a^p b^p a^p b^p, this string cannot be pumped, so the language should not be context free.
Where am I going wrong?
Upvotes: 3
Views: 1576
Reputation: 45115
Let u = a^p, v = b^(p-1), x = ba, y = a^(p-1), z = b^p, so that your string s = uvxyz.
Then any string of the form u v^i x y^i z is in the language, so the conditions of the CFL pumping lemma are satisfied.
The pumping length isn't "p" for your example...maybe that's where you're getting confused?
Edit: sepp2k correctly points out that my choice of vxy violates the condition that |vxy| < = p, the pumping length of the language. His solution v=b, x=e, y=a is correct. For this language, any string of length 2 or greater will pump -- "ab" or "ba" must appear somewhere, so vy = ab or vy = ba will always work.
Upvotes: 1
Reputation: 370425
Sure the string can be pumped. Let u = a^p b^(p-1), v = b, x = e, y = a, z=a^(p-1) b^p
. Now uvxyz = s
and for any i u v^i x y^i z
has an equal amount of as and bs.
Upvotes: 4