上下文无关语言中的抽吸引理

Question

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

我需要证明A不是上下文无关的。我猜我必须使用Pumping引理来解决这个问题，但是如何？

Answer 1

目标是证明对于长度> =最小抽吸长度的任何弦，弦不能被泵送。也就是说，如果将其拆分为子条形码uvxyz，则制作v和y的拷贝（或删除拷贝）所产生的字符串仍然是语言A。

请注意，您只需要表明，在语言中的一个字符串不能抽（只要满足最低的泵送长度P）

考虑这个语言，它与A：

Answer 2

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

的关键是可能会是0和1