state-machine - 我无法弄清楚这种语言是否是常规语言，它可以用 nfa 表示吗？

Question

这种语言是正规的吗？我找不到解决方案，而且我对它的感觉很复杂，顺便说一句，我最近两周才这样做。

Answer 1

这种语言不是正则语言，我们可以使用正则语言的抽引引理来证明这一点。假设语言是规则的。那么语言中的字符串 0^p 1^p 可以写成 uvx where |uv| <= p, |v| > 0 并且对于所有自然数 k，u(v^k)x 在语言中。但是，我们的 uv 必须只包含前导 0，并且由于我们可以通过选择 k = 0 来抽空，因此我们违反了 |w| <= n。这是一个矛盾，所以语言不可能是规则的。