context-free-grammar - 以上下文无关语言抽取引理

Question

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

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

Answer 1

目标是证明对于长度 >= 最小抽吸长度的任何弦，该弦不能被抽吸。也就是说，如果将其拆分为 substrings uvxyz，则由复制（或删除副本）得到的字符串v和y仍然是 language A。

请注意，您只需表明该语言中的一个字符串不能被抽取（只要它满足最小抽取长度 p）

考虑这种语言及其与以下内容的关系A：

Answer 2

第一步：计算出你的最小泵送长度 (2^p+1)，其中 p 是变量的数量。第二步：制作一些该长度的字符串。第三步：开始将字符串切割成 vwxyz 使得 |wy|> 0（注意 |x| 可以为零）和 |wxy| <= 2^p+1。查看可以定义 w 和 y 的各种方法，以及当您开始在适当位置重复这些子字符串时会发生什么。

关键可能在 0 和 1 之间的分界线上。