证明不规则性

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 成为 "pumping-lemma-number"。选择 s= 0^n 1 0^n。 从 1) 你知道 |xy| <= n。从 2) 你知道 |y|>=1。因此 y 只包含 0s.

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