Pumping lemma for CFLs
computer-science, context-free-grammar, pumping-lemma
Solution
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.
Problem
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?