有人可以帮我用这个抽样引理证明吗？

我刚开始阅读关于抽象引理，并知道如何执行一些证明，主要是通过矛盾。只是这个问题我似乎没有找到答案。我不知道如何开始。我可以假设，必须有抽水长度为P，并且对于所有w元素L表示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。

来源

2013-03-14 n00b1990

有几个问题需要澄清：“L”字母表中的“+”和“=”是否是执行数学计算的一部分？＃（x）是否表示x的二进制值？ – DPenner1 2013-03-14 14:33:24

对不起，我忘了说字母是什么，以及＃的含义。我刚刚编辑了这个问题。 – n00b1990 2013-03-14 15:18:13

@ n00b1990这种语言甚至没有上下文免费语言（CFL）[**阅读我的这个答案**]（http://stackoverflow.com/questions/13904309/verifier-of-addition-not-regular-but-is- it-context-free？answertab = votes＃tab-top）让我知道你是否需要更多的帮助。 – 2013-03-15 15:51:33

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

要注意的第一件事是，+和=只能出现一次，每个。所以，当你写你的字符串作为ww = abc，泵送部分，b，不能包含+或=否则你会到达一个微不足道的矛盾（我没有使用更标准的w = xyz符号，以避免与L的定义相混淆）。
另一件需要注意的事情是，通常你会选择一个特定的字符串w进行泵送。在这种情况下，可能更容易挑选共享某个属性的字符串类。抽象引理只要求你使用一个字符串来达到一个约束，但没有理由你不能用多个字符串来达成矛盾。

证明（在扰流板）：

因此，让w在L使得|w| ≥ P和x, y, z不包含前导0的任何字符串。通过抽象引理，我们可以写w为w = abc通过抽象引理，我们知道b不是空的。由于b不能包含+或=，因此它完全包含在x, y,或z中。由于x, y, z中只有一个数字是不同的数字（这就是为什么我们需要无前导码0的位），因此二进制方程式中的结果不再存在，导致w与i ≠之间的差异。

来源

2013-03-14 15:50:21 DPenner1

非常感谢您的帮助。我现在知道了。由于方程不能改变，这意味着我们关于语言规则的假设是不正确的，因此它必须是不规则的。我现在明白了，谢谢！干得好破坏者:) – n00b1990 2013-03-14 21:06:34

虽然我很好奇。如何判断何时拾取一类字符串比单个字符串更容易？如果b包含'+或='，会发生什么？这难道不足以达到矛盾，从而证明吗？ – n00b1990 2013-03-14 21:11:45

至于选择一类字符串，对我而言稍微容易一些，因为我的思维过程是：“现在我需要抽b，这样数字才会变化。”并且总是满足的是那些没有前导零的元素。所以现在我知道了，我真的不需要找到一个特定的字符串，这只是一个额外的步骤。然而，就像@ Patrick87所做的那样，挑选特定的字符串仍然是完全有效的，并且根据您的思维过程，可能会更容易。 – DPenner1 2013-03-15 01:59:56

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

换句话说，你的字符串将会读出“两个和幂n + 2加上两个加上幂n + 1的和等于11跟n个零”。

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

由于抽运引理要求抽运字符串在语言中，并且抽这个字符串失败，所以我们认为语言是不规则的。

来源

2013-03-14 16:51:33 Patrick87

我部分理解你的解释，但你能告诉我为什么字符串是必要的吗？或者这是一类字符串？我感谢您的帮助 – n00b1990 2013-03-14 21:08:52

@ n00b1990这是一类以您的语言编写的抽象引理失败的字符串。使用抽象引理的证明通常是这样的：抽吸引理说明一定长度的所有字符串应该是可抽取的;这里至少有一串长度;它不是可以抽水的;假设语言满足抽词引理是错误的;该语言不规则。 – Patrick87 2013-03-14 21:17:52

有人可以帮我用这个抽样引理证明吗？

回答

相关问题