computation-theory - 为没有顺序的语言抽取引理

Question

我一直在做一些课本上的问题来练习期末考试，但我遇到了一个我无法弄清楚的问题。基本上是为了

令 L = {w | w 包含的 0 多于 1 }

它暗示常规语言的引理应该有所帮助。

虽然当存在某种模式时很容易证明语言非常规，例如 0 的第一个后跟 1 或回文，因为您可以通过抽水来打破模式，但这里唯一的要求是单词，它可以包含 0 和 1任何顺序，都有更多的 0。

我试图考虑一些情况，最明显的情况是如果 y=0，你可以抽 y 直到你的 0 多于 1。但是我们必须考虑所有可能的情况，以证明泵引理是错误的，并且看起来 y 可以是任何字符串，只要 |xy| < p（其中 p 是泵送长度）。y 可以包含 0 和 1，或仅包含 1。我在这里遗漏了一些明显的东西吗？提前谢谢。

Answer 1

你可以像这样选择一个词：
给定一个数字 n，这个词是 z=0^(2n)1^n，它在
L.z=uvw 中，并且 |uv|<=n，所以 uv 只包含零。
因此，v 也只包含零，并且|v|>=1。
如果我们假设 L 是正则的，那么由于引理 uv^0w 在 L 中。
但是 v=0^k (k>=1)，所以 uv^0w=0^(2n-k)1^n，其中不在 L 中，因为 k>0。