语言L ={a^n ^k^m\ k>=0，n>m}正则吗？

Question

我必须用pummping-引理来解释这种语言：

L ={a^n b^k c^m | k>=0, n>m}

是不正常的。

有人能解释一下这门语言是如何做到的吗？

Answer 1

编辑:我在这里犯了两个错误，第一，抽水必须与你使用的单词有关(或者至少在看了很多例子之后看起来是这样的)，其次，如果你找到了一个好的匹配，那么你就不能用它作为一个错误的例子。如果我的答案是错误的，我将编辑它如何才能真正被证明。

pummping引理是关于通过使用矛盾来证明非正则语言的，首先必须假设一个字符串必须对L是正则的，然后按照一些规则将这个字符串分成三个部分：

1. Y>0
2. <= P (P表示单词的最小长度)
3. 带有n>=0的xy^nz包含在语言(L)中

让我们以P是1为例：

如果语言允许，我将不使用任何b's。这意味着我将以L={ a^P+1 c^P }的方式表达我的语言，它包含在L中，并且是有效的，所以让我们假设aac (这是L中的)

• 除以它的唯一方法是(x:a，y:a，z:c)

记住这一点，您可以证明使用这3条语句中的2条是不正常的。

因为P是1，xy是2，所以xy比P大。 如果我们使用n= 0，则结果将是ac，它不包含在语言中。