regular-language - 证明不规则性

Question

假设我有一种语言 L = {wxwR}，其中 wR 是 w 的倒数，w 和 x 的最小长度为 1，w 可以由 0 或 1 组成，而 x 只能由 1 组成。

我如何证明这种语言不规则？除了使用抽水引理之外，还有其他方法吗？如果使用抽引引理，我仍在弄清楚我应该为字符串 s=xyz 选择什么 x、y 和 z，如果您能给我任何提示，我将不胜感激。

谢谢！

Answer 1

您应该再看看如何使用抽水引理。您必须选择一个字符串s，这样对于每个分区x，y，z，其中一个泵引理条件被违反。

所以，让我们n成为“抽水引理数”。挑选s= 0^n 1 0^n。从 1) 你知道|xy| <= n。从 2) 你知道|y|>=1。因此y只包含0s.

以下 3)uv^2w也必须在 中L，但第一个块0s比第二个块长。这意味着 3) 被违反，因此L不规则。