语言的规律性与抽取引理

Question

将字符串解释为二进制Z ≥0中的数字（可能带有前导零，此处没有模运算）。 {0, 1}的以下语言是常规的{xyz : |x| = |y| = |z| and x + y = z}？

我想要证明这种语言的非规律性，我应该应用Pumping Lemma并且表明没有可能的设置使得泵浦引理的所有三个条件都得到满足。

Answer 1

考虑长度为3p + 3的字符串（0 ^ p）1（0 ^ p）1（0 ^ p-1）10。这是语言中的字符串，因为选择| x | = | y | = | z |意味着x =（0 ^ p）1，y =（0 ^ p）1和z =（0 ^ p-1）10，并且1 + 1 = 10.现在，泵浦引理说这可以写成rst在哪里：

• | RS | <= p
• | S | > 0
• r（s ^ k）t是所有自然数k的语言

请注意，在我们的例子中，s必须完全由我们的组件x中的前导0组成。假设我们选择k = 0.有几种情况需要考虑：

• | RT |不能被3整除。在这种情况下，由于条件| x |，字符串不可能是我们的语言= | y | = | z |不能满足。
• 如果| rt |可以被3整除，考虑我们新的x，y和z：我们删除了一些3m的前导0。这意味着| x | = | y | = | z | = p + 1 - m。原来在旧x末尾的1将在新字符串中左移（m-1）个位置; y末尾的1将在新字符串中左移（m-2）个位置;并且z结尾处的1将保持在z中的倒数第二个位置。 如果m = 1，则y将不再包含任何1，因此不能满足x + y + z 如果m> 1，则x将表示大于或等于10的数字，y将表示正数。然而，大于或等于10的数字和正（非零）数的总和不能等于10.因此，这里也不能满足x + y + z。

因此，m = | s |没有选择这样选择k = 0就可以得到语言中的r（s ^ k）t。这是一个矛盾，因此我们隐含的假设语言是规则的必须是假的。