在上下文无关的语言中抽取引理 [英] Pumping Lemma in context-free languages

问题描述

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

我需要证明A不是上下文无关的。我猜我必须为此使用Pumping Lemma，但是如何使用？

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

推荐答案

目标是证明对于任何长度大于等于最小抽运长度的字符串，无法抽运该字符串。也就是说，如果将其拆分为子字符串 uvxyz ，则该字符串是由于复制（或删除副本） v 和 y 仍使用语言 A 。

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.

请注意，您只需要显示该语言中的一个字符串就不能被泵送（只要满足最小泵送长度p）即可。

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)

请考虑该语言及其相关性到 A ：

Consider this language and how it relates to A:

这篇关于在上下文无关的语言中抽取引理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！