问使用抽头引理证明语言不是无上下文的

EN

我认为你对单词的选择也是有效的，但我会选择一个简单的(对我来说)来展示同样的东西。您可能可以根据您的字符串选择来调整这一点。

选择w= (1^p)(2^p)(3^p)，其中p来自上下文无关语言的抽吸引理。首先，注意11.1+22.2=33.3都是p位数。现在，如果w=uvxyz，vxy的位置正好有五个简单的情况：

1. vxy仅由1组成。在这种情况下，抽吸(至少移除1中的一个)必然会导致字符串不是语言中的字符串。由于任何数字的加法都不能进行进位，所以字符串必须在a、b和c的三个等长部分中被分割；这些部分必须有相同的数字数。因此，将3k位数从前面移除，将2s的k拉进a，将2k的2k拉到b中。但是，a+b的最小有效数字必须是5，这不是w中的符号。
2. vxy由1和2组成。在这种情况下，抽吸(移除一些1和2的数)必然会导致字符串不是语言中的字符串。由于任何数字的加法都不能进行进位，所以字符串必须在a、b和c的三个等长部分中被分割；这些部分必须有相同的数字数。从1s和2s中删除3k位数必须将3s拉到b中。因此a+b的最小有效数字至少为4(因为w不包含0)，而4不是w中的数字。
3. vxy由2组成，这里的参数与上面的第二种情况相同。
4. vxy由2和3组成。在这种情况下，必须将2同时放进a和b中，以使数字重叠，因此我们得到了与上面相同的4/5数字问题。
5. vxy只包含3。同样，在这种情况下，必须最终将3放入b中，从而导致4/5数字问题。

插图：

1. W=1^p2^p3^p，向下抽至1^(p-3) 2^p3^p，a= 1^(p-3) 22，b= 2^(p-2) 3，c= 3^(p-1)，a+b的最小有效位数为5，过高，不能正确。
2. W=1^p2^p3^p，向下抽至1^(p-1) 2^(p-2) 3^p，a= 1^(p-1)，b= 2^(p-2) 3，c= 3^(p-1)，最小有效数字4也过高。
3. W=1^p2^p3^p，向下抽至1^p2^(p-3) 3^p，a= 1^(p-1)，b=1 2^(p-3) 3，c= 3^(p-1)。同样，最不重要的数字( 4 )太高了。
4. W=1^p2^p3^p，泵最大可达1^p2^(p+1) 3^(p+2)，a=1^p2，b=2^p3，c= 3^(p+1)。现在最不重要的数字太高了。
5. W=1^p2^p3^p，泵最大可达1^p2^p) 3^(p+3)，a=1^p2，b= 2^(p-1) 33，c= 3^(p+1)。LSD仍然过高。