3

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

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

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

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

编辑：
对不起，忘了说字母表是字符串{0,1,+,=}的#二进制值。喜欢#(00101) = 5和#(110) = 6。

4

2 回答 2

2

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

  1. 首先要注意的是 the+和 the=可能只出现一次。因此，当您将字符串写w为w = abc时，抽水部分 ,b不能包含+，=否则您会遇到一个微不足道的矛盾（我没有使用更标准的w = xyz符号来避免与L' 的定义混淆）。

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

证明（剧透）：

因此，让我们w成为其中的任何字符串L，|w| ≥ P并且x, y, z不包含前导0's。通过抽引引理，我们可以写成w通过w = abc抽引引理，我们知道b它不是空的。由于b不能包含+or =，所以它完全包含在x, y,orz中。用任何 i ≠ 1抽水w会导致二元方程不再成立，因为其中一个x, y, z将是不同的数字（这就是我们需要无前导0位的原因）。

于 2013-03-14T15:50:21.063 回答
2

选择作为字符串1(0^n+1) + 1(0^n) = 11(0^n)。

换句话说，您的字符串将显示“2 的 n+2 次方加上 2 的 n+1 次方之和等于 11，后跟 n 个零”。

由于要抽取的字符串将完全由第一个加数中的符号组成，因此抽取必须更改表示的数字（向数字添加或删除数字会改变数字；这是真的，因为我们的字符串不包含前导零）并且如果x + y = z成立，x' + y = z则不成立 if x' != x（至少在整数上）。

由于抽水引理要求抽水字符串在语言中，并且抽水该字符串失败，因此我们认为该语言不规则。

于 2013-03-14T16:51:33.920 回答