证明不规范

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是不规则的。