使用 Pumping Lemma 证明语言的非正则性
Using Pumping Lemma to prove non regularity of a language
这是一般规则...
Let L be a regular language. Then there exists an integer p ≥ 1 depending only on L such that every string w in L of length at least p (p is called the "pumping length") can be written as w = xyz (i.e., w can be divided into three substrings), satisfying the following conditions:
|y| ≥ 1
|xy| ≤ p
for all i ≥ 0, x y^i z ∈ L
...到目前为止一切顺利。
但是为了证明给定的语言是非常规的，考虑一种情况就足够了吗（从而使第三点无效）？
例如：
L = {a b^n c^k d^m | k,n,m>0 AND m>n} <-- given language
w = {a b^n c d^m | n=1 AND m=2} = abcdd <-- arbitrary instance of the language
x = a
y = bc
z = dd
和i=2，x y^i z会变成abbccdd，因此n=2，这意味着m>n现在是false。
这足以作为证据吗？
OT: 你如何在 Whosebug 中写入 apex/superscript 个字符？
in order to prove that a given language is non-regular, is it sufficient to consider one case
是的，这是使用泵引理时的常见模式。证明应该是矛盾的，首先假设语言 是 规则。然后你会发现一个与抽取引理相矛盾的语言的示例字符串。泵引理说明了 每个 字符串（在某些条件下），因此找到一个反例就足以证明矛盾。
给出的语言是 L = {a b^n c^k d^m | k,n,m>0 AND m>n} - 这意味着在该语言的单词中 d 多于 b。
回答您的问题：
But in order to prove that a given language is non-regular, is it
sufficient to consider one case (and thus going to void the third
point)?
这个想法是正确的。您想对常规语言使用 Pumping Lemma，并且如果您可以证明将 Pumping Lemma 应用于给定语言的单词会产生不在该语言中的单词，那么您已经证明该语言不能是常规语言。
泵引理经常被使用并且在这个意义上很有用。
Is this enough as proof?
你给出的证明是正确的想法，但没有正确应用。您选择了
x = a
y = bc
z = dd
并且应用 Pumping Lemma 会导致 abcbcdd，这当然不是语言的一部分，但现在 pumping 长度开始发挥作用。
你有语言
L = {a b^n c^k d^m | k,n,m>0 AND m>n}
现在您要查找一个词并选择 p 和适当的子字符串，应用正则语言的抽取引理，并显示生成的词不在该语言中。然后您可以得出结论，该语言不规则。
您选择的子串不合适。有一个错误，我在对你的问题的评论中提到过。我会采用一般方法：
w = {a b^n c^k d^m | n,p,m > 0 and m > n and n < p }
x = a
y = b^n
z = c^k d^m
所以使用 Pumping Lemma 我们可以说：
|y| >= 1 因为根据定义 b^n with n > 0|xy| = |a b^n| <= p 其中 p 是泵送长度 - 因此我们可以假设
p = n + 1 即 |a b^n|
xy 至少包含 ab，因此 p >= 1|w| >= p，因为我们之前将p设置为n + 1，并且由于k > 0和m > n - 并且
x y^i z 在 L 中，所有 i >= 0
现在选择 n + 1 = m 处的单词，即单词中总是比 b 多 d 个。这个词在 L 中，看起来像 a b^n c^k d^m。现在我们应用 Pumping Lemma 并将单词抽取到 a b^n+1 c^k d^m。但这是一个矛盾，因为现在 pumped 单词中的 b 和 d 一样多，因此该单词不在语言 L。我们可以得出结论，L 不是正则的。
这是一般规则...
Let
Lbe a regular language. Then there exists an integerp ≥ 1depending only onLsuch that every stringwinLof length at leastp(pis called the "pumping length") can be written asw = xyz(i.e.,wcan be divided into three substrings), satisfying the following conditions:
|y| ≥ 1
|xy| ≤ pfor all
i ≥ 0, x y^i z ∈ L
...到目前为止一切顺利。
但是为了证明给定的语言是非常规的，考虑一种情况就足够了吗（从而使第三点无效）？ 例如：
L = {a b^n c^k d^m | k,n,m>0 AND m>n} <-- given language
w = {a b^n c d^m | n=1 AND m=2} = abcdd <-- arbitrary instance of the language
x = a
y = bc
z = dd
和i=2，x y^i z会变成abbccdd，因此n=2，这意味着m>n现在是false。
这足以作为证据吗？
OT: 你如何在 Whosebug 中写入 apex/superscript 个字符？
in order to prove that a given language is non-regular, is it sufficient to consider one case
是的，这是使用泵引理时的常见模式。证明应该是矛盾的，首先假设语言 是 规则。然后你会发现一个与抽取引理相矛盾的语言的示例字符串。泵引理说明了 每个 字符串（在某些条件下），因此找到一个反例就足以证明矛盾。
给出的语言是 L = {a b^n c^k d^m | k,n,m>0 AND m>n} - 这意味着在该语言的单词中 d 多于 b。
回答您的问题：
But in order to prove that a given language is non-regular, is it sufficient to consider one case (and thus going to void the third point)?
这个想法是正确的。您想对常规语言使用 Pumping Lemma，并且如果您可以证明将 Pumping Lemma 应用于给定语言的单词会产生不在该语言中的单词，那么您已经证明该语言不能是常规语言。
泵引理经常被使用并且在这个意义上很有用。
Is this enough as proof?
你给出的证明是正确的想法，但没有正确应用。您选择了
x = a
y = bc
z = dd
并且应用 Pumping Lemma 会导致 abcbcdd，这当然不是语言的一部分，但现在 pumping 长度开始发挥作用。
你有语言
L = {a b^n c^k d^m | k,n,m>0 AND m>n}
现在您要查找一个词并选择 p 和适当的子字符串，应用正则语言的抽取引理，并显示生成的词不在该语言中。然后您可以得出结论，该语言不规则。
您选择的子串不合适。有一个错误，我在对你的问题的评论中提到过。我会采用一般方法：
w = {a b^n c^k d^m | n,p,m > 0 and m > n and n < p }
x = a
y = b^n
z = c^k d^m
所以使用 Pumping Lemma 我们可以说：
|y| >= 1因为根据定义b^n with n > 0|xy| = |a b^n| <= p其中p是泵送长度- 因此我们可以假设
p = n + 1即|a b^n| xy至少包含ab，因此p >= 1|w| >= p，因为我们之前将p设置为n + 1，并且由于k > 0和m > n- 并且
x y^i z在L中，所有i >= 0
现在选择 n + 1 = m 处的单词，即单词中总是比 b 多 d 个。这个词在 L 中，看起来像 a b^n c^k d^m。现在我们应用 Pumping Lemma 并将单词抽取到 a b^n+1 c^k d^m。但这是一个矛盾，因为现在 pumped 单词中的 b 和 d 一样多，因此该单词不在语言 L。我们可以得出结论，L 不是正则的。