证明L= {a^n ^m\ n>=m}是不规则语言

Question

我被困在寻找S的泵引理。有什么办法证明L= {a^n ^m\ n>=m}是一种不规则语言吗？

Answer 1

抽水引理指出：

如果L是一种正则语言，则存在一个自然数p，使得长度至少为p的任何字符串w都可以写成w= uvx，其中uv_v_v_x=0，且对于所有自然数n，u(v^n)_x也在该语言中。

为了证明语言不是正则的，我们需要设计一个字符串w，使语句的其余部分失败:也就是说，没有有效的u、v和x赋值。

我们的语言L要求a的个数与b的个数相同，满足字符串w至少有p的假设的最短字符串是a^(p/2) b^(p/2)。我们可以猜到这是我们的弦。如果我们这样做了，我们有几个案例：

condtradiction.

• v v完全由a's构成。但是，抽水会导致a's和b's的数目不同，因此产生的字符串不在语言中；a

• 跨a's和b's。但是，抽水会导致a和b在中间混在一起，而我们的语言要求a和b放在第一位。这也是一个完全由b构成的contradiction.

• v。但是，我们和案例#1.

有相同的矛盾。

在任何情况下，这种选择都会导致矛盾。这意味着猜测成功了。

这里对于w有一个更简单的选择:选择w= a^p ^p，然后只有一个情况。但我们的选择很成功。如果我们的选择没有成功，我们就可以从这一选择中了解到哪里出了问题，选择了另一位候选人。

Answer 2

对于之前的评论，(1)没有意义，因为我们可以有更多的a's然后b's. n>=m。由于这个问题，我昨天可能对期中考试进行了轰炸，但发现答案实际上是在抽水部分。解决办法是，我们既可以往上，也可以往下。正则语言的抽吸引理表示对于所有的i>=0，w=x(y^i)z。

案例1: y= a's，所以通过使用a^n ^m和w= a^p ^p，如果y是a的一定量，那么我们看到：

x = a^p-l
y = a^l
z = b^m

现在，如果使用y^0，则a小于b，接下来的两种情况应该很容易证明，但不管怎么加，我都会加进去。

案例2: y=只有b's

x = a^p
y = b^l
z = b^(p-l)

抽到xy^2z会产生比a更多的b's，所以在L中这不是一个可接受的词。

案例3: y=a和b

x = a^(p-l)
y = (a^l)(b^k)
z = b^(p-k)

泵浦x(y^2)z给出了不包含在L中的a^(p-l) (a^l)(b^k)(a^l)(b^k) b^(p-k)。