views:

380

answers:

2

This isn't a programming question, but I don't know of any good places on the Internets to ask computer science questions. Sorry if this is too off-topic.

I'm reviewing some old CS material and I'm stuck on the following:

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?

+3  A: 

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.

sepp2k
+1  A: 

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.

Jim Lewis
What do you mean by "the pumping length isn't p"? If he chose p to be the pumping length, then p is the pumping length.
sepp2k
Your solution seems to be wrong. |vxy| is greater than p, which it's not allowed to be.
sepp2k
The pumping length is a property of the language, not a property of a particular string, subset of strings, or choice of u v x z y in the proof.
Jim Lewis
However, you're right about my choice of vxy being wrong. Your solution is better.
Jim Lewis
Yes, it's a property of the language. However there's nothing to prevent you from building a string which is based on that property of the language. There's no reason why I can't say "there's a string of the form a^p b^p a^p b^p where p is the pumping length of the language". Since the pumping length is finitie that string obviously exists and needs to be pumpable.
sepp2k
And for this language, the pumping length appears to be 2. Either ab or ba must occur, so by choosing vy to be that pair, x null, u and v the prefix and suffix, the string pumps.
Jim Lewis
Sorry, was a little hasty in selecting a solution. I verified sepp2k's partition of s, then saw Jim's comment about 'p', which made me realize what my misunderstand was and just assumed his partition was correct. I was making a silly mistake and for some reason thinking that each substring of a's and b's had to be of length p, but that is not the case.
Neal
I'm glad it worked out in the end!
Jim Lewis