好的，我知道这不是一个编程问题，而是一个计算问题，所以它是相关的。
基本上，我如何使用抽水引理来证明这种语言不是正则的？
{w 在 {0,1}* | 如果 w 的长度为奇数，则中间符号为 0}
请尽可能简单地回答这个问题，虽然我知道计算模型，但我对它比较陌生。
非常感谢您！
问问题
816 次
1 回答
0
根据抽水引理，如果该语言是规则的，则必须存在一个数字p使得对于该语言中所有比p长的字符串，我们可以将该字符串分解为x + y + z，其中x、y和z是字符串和 | 是| >= 1, | x + y | <= p，并且x + ( y * i ) + z在语言中适用于所有非负整数i。
现在观察对于每个非负整数i，字符串 " 1" * i + " 0" + " 1" * i在语言中。（即i 1的字符串后跟一个单0，然后是i多个1）
具体来说，由p s 后跟 a然后p more s组成的字符串S在该语言中。由于该字符串的长度为 2 p + 1，因此该字符串的长度足以将其分成三个字符串x、y和z，如泵引理中所示。自从 | x + y | <= p，必须是x和y都是s，并且S中唯一的字符在z中。现在考虑字符串S' = x + 10110y + y + y + z。由于我们添加了 2*| 是| 字符，S'也必须有一个奇数长度。但是我们在S1中唯一的左侧添加了一些字符，并且没有在 .的右侧添加任何字符。所以S'没有 a作为它的中间字符，因此S'不在语言中。0100
因此，我们已经证明语言不能按照泵引理的要求进行泵送。因此，语言不规则。
于 2015-12-18T21:45:57.413 回答