我在测试中弄错了这个问题，想知道是否有人可以解释它，显示得出结论所采取的步骤。任何帮助，将不胜感激。
在 L_neq = {0^i1^j | 的 PL 证明中 i < j} 给定一个 m-state DFA，有人选择字符串 0^(m/2)1^(m/2+1)。然后他们选择 y = 0 并表明通过抽水，我们可以到达 L_neq 之外的字符串 0^(m/2+1)1^(m/2+1)。这个证明正确吗？为什么或者为什么不？
此外，如果这个证明是错误的，请写下一个正确的证明。
谢谢
问问题
1363 次
1 回答
4
使用抽水引理时，虽然允许您选择要抽水的字符串（我们称之为 w），但您不能选择如何将 w 拆分为 xyz 三个部分。相反，您需要做的是证明对于任何可以将 w 拆分为 xyz 的方式，都可以选择 i 使得 xy i z 使得 xy i z ∉ L neq。因此，虽然您是正确的，如果 y = 0 则字符串可以从 L neq中取出，但您不能保证 y = 0。相反，您需要证明对于 y 的任何选择，这样 |xy| ≤ m 和 |y| > 0，您可以将字符串从语言中取出。
作为提示，请尝试使用字符串 0 m 1 m。现在，对于 y 的任何选择，因为 |xy| ≤ m，你知道对于某个自然数 j > 0，y 必须具有 0 j的形式。那么你的论点可以用来证明 xy i z 不再在 L neq中。
有关抽水引理以及这些证明如何工作的另一个资源，请随时查看我在本季度早些时候在计算理论课程中使用的这些演讲幻灯片。他们浏览了一些引理示例，并且（重要地）展示了思考这些证明的对抗模型。
希望这可以帮助！
于 2011-12-01T21:41:16.793 回答