3

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?

Chandrahas Aroori
  • 955
  • 2
  • 14
  • 27
Neal
  • 6,722
  • 4
  • 38
  • 31

2 Answers2

4

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
  • 363,768
  • 54
  • 674
  • 675
1

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
  • 43,505
  • 7
  • 82
  • 96
  • 1
    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 Aug 22 '09 at 20:03
  • 1
    Your solution seems to be wrong. |vxy| is greater than p, which it's not allowed to be. – sepp2k Aug 22 '09 at 20:08
  • 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 Aug 22 '09 at 20:10
  • However, you're right about my choice of vxy being wrong. Your solution is better. – Jim Lewis Aug 22 '09 at 20:13
  • 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 Aug 22 '09 at 20:20
  • 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 Aug 22 '09 at 20:33
  • 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 Aug 22 '09 at 21:31