你如何在泵引理中划分字符串？
How do you divide the string in pumping lemma?
例如，让我们证明L = {0^n1^n | n ≥ 0} 是不规则的。
要证明一种语言是不规则的，请反驳以下任何一项：
(1) |紫外线| ≤ n
(2) |v| ≥ 1
(3) 对于所有 i ≥ 0: uviw ∈ L 使得 | uviw | >= n
让我们假设 L 是正则的，然后通过 Pumping Lemma 遵循上述给定的规则。
现在，让 x ∈ L 和 |x| ≥ 名词。因此，通过 Pumping Lemma，存在 u, v, w 使得 (1) – (3) 成立。
我们证明对于所有 u、v、w，(1) – (3) 都不成立。
如果 (1) 和 (2) 成立则 x = 0^n1^n = uvw with |uv| ≤ n 和 |v| ≥ 1.
//你是怎么划分语言的字符串的？如何w = 0^c1^n?
所以，u = 0^a，v = 0^b，w = 0^c1^n 其中：a + b ≤ n，b ≥ 1，c ≥ 0，a + b + c = n
谢谢
拉赫曼
您将 n 用于两件事：语言的定义以及抽取引理的常数。让我们使用 n_0 作为常量。在您的条件 (iii) 中，最后一条语句应该是 |uvw| \geq n_0，没有指数 i。
现在我们可以选择，例如a^{n_0}b^{n_0}这个词，它满足了这个长度要求。从条件 |uv|\leq n_0 中我们可以直接看出 u 和 v 只包含符号 a，满足抽取引理条件的每个因式分解。因此 uv^iw 中 i>1 的任何词的 a 比 b 多，因此不在该语言中，这与条件三相矛盾。
例如，让我们证明L = {0^n1^n | n ≥ 0} 是不规则的。
要证明一种语言是不规则的，请反驳以下任何一项： (1) |紫外线| ≤ n (2) |v| ≥ 1 (3) 对于所有 i ≥ 0: uviw ∈ L 使得 | uviw | >= n
让我们假设 L 是正则的，然后通过 Pumping Lemma 遵循上述给定的规则。 现在，让 x ∈ L 和 |x| ≥ 名词。因此，通过 Pumping Lemma，存在 u, v, w 使得 (1) – (3) 成立。
我们证明对于所有 u、v、w，(1) – (3) 都不成立。
如果 (1) 和 (2) 成立则 x = 0^n1^n = uvw with |uv| ≤ n 和 |v| ≥ 1.
//你是怎么划分语言的字符串的？如何w = 0^c1^n?
所以，u = 0^a，v = 0^b，w = 0^c1^n 其中：a + b ≤ n，b ≥ 1，c ≥ 0，a + b + c = n
谢谢 拉赫曼
您将 n 用于两件事：语言的定义以及抽取引理的常数。让我们使用 n_0 作为常量。在您的条件 (iii) 中，最后一条语句应该是 |uvw| \geq n_0，没有指数 i。
现在我们可以选择，例如a^{n_0}b^{n_0}这个词，它满足了这个长度要求。从条件 |uv|\leq n_0 中我们可以直接看出 u 和 v 只包含符号 a，满足抽取引理条件的每个因式分解。因此 uv^iw 中 i>1 的任何词的 a 比 b 多，因此不在该语言中，这与条件三相矛盾。