Context Free Language Question (Pumping Lemma)

Question

I know this isn't directly related to programming, but I was wondering if anyone know how to apply the pumping lemma to the following proof:

Show that L={(a^n)(b^n)(c^m) : n!=m} is not a context free language

I'm pretty confident with applying pumping lemmas, but this one is really irking me. What do you think?

Immemorial

mathoverflow.net check it out – Dagney

I'd say that this is one of those areas where Math and CS theory overlap. – Cadmann

@Jonathan: This question would typically be covered in a CS class, not a math class. It's kind of a fuzzy area, though. I would definitely classify it as "of interest to programmers". – Aphotic

@Jonathan: This is definitely not a mathoverflow.net question. This result is widely taught in undergraduate CS; mathoverflow is for research-level mathematics. – Missymist

@Charles and @Dietrich: There's a computer science tag at mathoverflow.net mathoverflow.net/questions/tagged/computer-science. Thought that would be a good place to ask this question. My apologies!!!!! – Dagney

Answer 1

Edit: I was totally leading you down the wrong track. That's what happens when I try to help out when I haven't completely solved the problem myself.

Ogden's Lemma

Suppose L is context free. By Ogden's lemma, there exists an integer p that has the following properties:

Given a string w in L at least p symbols long, where at least p of those symbols are "marked", w can be represented as uvxyz, which satisfy:

1. x has at least one marked symbol,
2. either u and v both have marked symbols or y and z both have marked symbols,
3. vxy has at most p marked symbols, and
4. u vⁱ x yⁱ z is in L for i >= 0

That's Ogden's lemma. Now, let q be an integer divisible by every positive integer no greater than p. Let w = a^p+q b^p+q c^p. Mark every c. By #2, u or v must contain at least one c. If either u or v contains any other symbol, then #4 fails, so u and v must contain only c. But then #4 fails when i = q/|uv|. We know q is divisible by |uv| because p > |uv| > 0, and q is divisible by all positive integers less than p.

Note that Ogden's lemma turns into the pumping lemma when you mark all symbols.

Pumping Lemma

Suppose L is context free. By the pumping lemma, there is a length p (not necessarily the same p as above) such that any string w in L can be represented as uvxyz, where

1. |vxy| <= p,
2. |vy| >= 1, and
3. u vⁱ x yⁱ z is in L for i >= 0.

Given a string w in L, either m > n or m < n. Suppose p = 2.

Suppose that m > n. (Note that Λ denotes the empty string.)

• Let u = aⁿ bⁿ c^m-1
• Let v = c
• Let x = Λ
• Let y = Λ
• Let z = Λ

Suppose that n > m.

• Let u = a^n-1
• Let v = a
• Let x = Λ
• Let y = b
• Let z = b^n-1 c^m

This demonstrates that no string from L provides a counterexample using the pumping lemma to the supposition that L is a context free language (even though it is context sensitive).

Aphotic

I don't follow...though this would prevent the pumped selection from including all 3 characters, it wouldn't stop the selected pump section from being all C's, which necessarily be pumped to equal n – Immemorial

I'm sorry, I misread the pumping lemma when I looked it up. I believe this requires Ogden's lemma, which is stronger. Fixed. – Aphotic

'requires Ogden's lemma' in that it's not provable w/ the pumping lemma? – Immemorial

I put up my proof with Ogden's lemma. Sorry for the unhelpful hints earlier. – Aphotic

So ogden's lemma is the only choice? Thanks a bunch for the insight! – Immemorial