开发者

Pumping Lemma in context-free languages

A = {0^a 1^b 2^c | a &开发者_运维技巧lt; 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?


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:

Pumping Lemma in context-free languages


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜