pumping-lemma - 是语言 L ={a^nb^kc^m | k>=0, n>m} 正则？

Question

我必须使用语言的抽水引理来解释：

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

不规律。

有人可以解释一下这种特定语言是如何完成的吗？

标签： pumping-lemma

Answer 1

编辑：我在这里犯了两个错误，首先抽水必须与您使用的单词有关（或者至少在看了很多示例之后看起来如此），其次，如果您找到任何合适的匹配项，则相反，那么您不能用它作为一个错误的例子。如果我的回答是错误的，我将编辑如何真正证明它。

抽水引理是关于通过使用矛盾来证明它不是常规语言，您首先必须假设您提供的必须对 L 有效的字符串是常规的，然后您必须按照一些规则将此字符串分成 3 部分：

1. |是| > 0
2. |xy| <= P（P代表单词的最小长度）
3. n>=0 的 xy^nz 包含在语言 (L) 中

因此，让我们以 P 为 1 为例：

为了使用这个，只要语言允许，我不会使用任何 b。这意味着我将用这种方式表达我的语言 L = { a^P+1 c^P } 它包含在 L 中并且是有效的，所以可以说 aac（这个在 L 中）

• 唯一的划分方法是 (x:a,y:a,z:c)

考虑到这一点，您可以使用 3 个语句中的 2 个来证明它是不规则的

|xy| 大于 P，因为 P 为 1，xy 为 2

xy^nz 如果我们使用 n = 0，那么结果将是 ac，它不包含在语言中。