CODEWITHSUNDEEP
context-free-grammarcomputation-theorypumping-lemma
Clint
Clint

Reputation: 21

Pumping Lemma in context-free languages

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?

Upvotes: 1

Views: 1667

Answers (2)

philosodad
philosodad

Reputation: 1808

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.

Upvotes: 0

prelic
prelic

Reputation: 4518

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

Upvotes: 2

Related Questions