Automata Theory 简明教程

Pumping Lemma For Regular Grammars

Theorem

设 L 是正则语言。那么存在常量 ‘c’ 使得对于 L 中的每个字符串 w −

|w| ≥ c

我们可以把 w 分成三个字符串 w = xyz ，使得 −

  1. |y| > 0

  2. |xy| ≤ c

  3. 对于所有的 k ≥ 0，字符串 xykz 也在 L 中。

Applications of Pumping Lemma

抽取引理用于证明某些语言不是正则的。它不应该被用来证明语言是正则的。

  1. 如果 L 是正则的，则它满足抽取引理。

  2. 如果 L 不满足抽空定理，它是非正则的。

Method to prove that a language L is not regular

  1. 首先，我们必须假设 L 是正则的。

  2. 因此，抽空定理应在 L 中成立。

  3. 使用抽空定理得到一个矛盾 − 选择 w 使得 |w| ≥ c 选择 y 使得 |y| ≥ 1 选择 x 使得 |xy| ≤ c 将剩余字符串分配给 z. 选择 k 使得结果字符串不在 L. 中

Hence L is not regular.

Problem

证明 L = {aibi | i ≥ 0} 不是正则的。

Solution −

  1. 首先，我们假设 L 是正则的，并且 n 是状态数。

  2. 令 w = anbn。因此 |w| = 2n ≥ n。

  3. 根据抽空定理，令 w = xyz，其中 |xy| ≤ n。

  4. 令 x = ap，y = aq 和 z = arbn，其中 p + q + r = n，p ≠ 0，q ≠ 0，r ≠ 0。因此 |y| ≠ 0。

  5. 令 k = 2。则 xy2z = apa2qarbn。

  6. as 的数量 = (p + 2q + r) = (p + q + r) + q = n + q

  7. 因此，xy2z = an+q bn。由于 q ≠ 0，xy2z 不是 anbn 的形式。

  8. 因此，xy2z 不在 L 中。因此 L 不是正则的。