regular-language - 有人可以帮助我使用泵引理证明这个证明吗？

Question

我刚刚开始阅读有关泵送引理的内容，并且知道如何进行一些证明，主要是通过反证法。我似乎找不到答案，只是这个特殊问题。我不知道如何开始。我可以假设必须有一个泵浦长度 P 并且对于 L 的所有 w 元素，LENGTH(w) >= P 。当然，我们可以用泵引理的三个正常条件将 w 写为 xyz。

我必须证明以下语言是非常规的:

L = {x + y = z | x,y,z element of {0,1}* and #(x) + #(y) = #(z) }

有人可以帮我解决这个问题吗，我真的很想掌握证明此类问题的过程？

编辑:
抱歉，忘了说字母表是 {0,1,+,=} ，而 # 表示字符串的二进制值。例如 #(00101) = 5 和 #(110) = 6。

Answer 1

既然你想掌握这个过程，我会在展示证明之前指出一些事情。

1. 首先要注意的是 +和 =每个只能出现一次。因此，当您编写字符串 w 时如w = abc ，泵送部分，b ，不能包含+或=否则你会遇到一个微不足道的矛盾(我没有使用更标准的 w = xyz 符号以避免与 L 的定义混淆)。

2. 另一件事需要注意的是，通常情况下，您会选择一个特定的字符串 w泵。在这种情况下，选择共享特定属性的字符串类可能会更容易。泵引理只要求您使用一个字符串达到矛盾，但没有理由不能使用多个字符串达到矛盾。

证明(剧透):

所以让w可以是 L 中的任意字符串这样|w| ≥ P和x, y, z不包含前导0的。通过泵引理我们可以写 w如w = abc通过抽引理，我们知道 b不为空。自 b不能包含+或= ，它完全包含在 x, y, 中或z 。抽水w任何 i ≠ 1 都会导致二元方程不再成立，因为 x, y, z 恰好之一将是一个不同的数字(这就是为什么我们需要无前导的 0 位)。