1
A = {0^a 1^b 2^c | a < b < c}

I need to show that A is not context-free. I'm guessing I have to use the Pumping Lemma for this, but how?

Clint
  • 21
  • 2
  • 2
    This looks like homework, if so, please add the homework tag. – Daniel Renshaw Nov 04 '10 at 10:04
  • 1
    Move to cstheory.stackexchange.com? – Sven Marnach Nov 04 '10 at 10:08
  • 3
    I doubt that people in cstheory.SE would find this question interesting – P Shved Nov 04 '10 at 11:17
  • 1
    I have been recommended to cstheory.stackexchange a few times, and they have a reasonably strict no-homework policy. They get upset when people post homework problems, and SO gets upset (understandably) when people post non-programming problems. – prelic Nov 05 '10 at 03:21
  • 2
    If you'd like to see the pumping lemma applied to a very similar language, here's an answer I gave to a recent CFL pumping lemma question: http://stackoverflow.com/questions/4149357/pumping-lemma-with-context-free-languages/4150029#4150029 – William Nov 12 '10 at 18:52

2 Answers2

2

The goal is to prove that for any string with length >= a minimum pumping length, the string cannot be pumped. That is, if you split it into substrings uvxyz, the string that results from making copies (or removing copies) of v and y are still in language A.

Note that you only have to show that one string in the language cannot be pumped (as long as it meets the minimum pumping length p)

Consider this language and how it relates to A:

alt text

prelic
  • 4,450
  • 4
  • 36
  • 46
0

Step one: figure out your minimum pumping length (2^p+1), where p is the number of variables. Step two: make some strings of that length. Step three: start cutting the strings up into vwxyz such that |wy|> 0 (note tha |x| CAN be zero) and |wxy| <= 2^p+1. Look at various ways you can define w and y and what happens when you start repeating those substrings in place.

The key is probably going to be on the dividing line between 0 and 1.

philosodad
  • 1,808
  • 14
  • 24