Clever Geek Handbook

Pumpdown lemma for CFL

My question is:

Let L = {x in {a, b} * | x has equal numbers of a and b}

I know it is a context free language because I can create a grammar for it (e epsilon):

S -> aX | bY | e

X -> bS | aXX

Y -> aS | bYY

You can also prove that it is context free by using the fact that a context free language that overlaps with regular language is context free.

Since it is a context free language, according to the pumping lemma for CFL, any string longer than the pumping length p must be pumped. However, if I choose the line s = a ^ pb ^ pa ^ pb ^ p, this line cannot be pumped, so the language should not be context free.

Where am I going wrong?

+3


source to share


2 answers


Of course the string can be swapped. 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 number of as and bs.



+4


source


Let u = a ^ p, v = b ^ (p-1), x = ba, y = a ^ (p-1), z = b ^ p, so your string is s = uvxyz.

Then any string of the form uv ^ i xy ^ i z is in the language, so the conditions of the CFL forwarding lemma hold.



The pump length is not "p" for your example ... maybe where are you getting confused?

Edit: sepp2k correctly indicates that my choice of vxy violates the condition that | vxy | <= p, length of tongue pumping. His solution v = b, x = e, y = a is correct. For this language, any string of length 2 or more will pump up - "ab" or "ba" must appear somewhere, so vy = ab or vy = ba will always work.

+1


source






More articles:


All Articles