正则文法的泵引理

定理

设 L 为正则语言。则存在一个常数 'c'，使得对于 L 中的每个字符串 w −

|w| ≥ c

我们可以将 w 拆分为三个字符串，w = xyz，使得 −

• |y| > 0
• |xy| ≤ c
• 对于所有 k ≥ 0，字符串 xy^kz 也在 L 中。

泵引理的应用

泵引理用于证明某些语言不是规则的。它永远不应该被用来证明一种语言是正则的。

• 如果 L 是正则的，它就满足 Pumping 引理。

• 如果 L 不满足 Pumping 引理，它就是非正则的。

证明语言 L 不是正则的方法

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

• 因此，Pumping 引理应该对 L 成立。

• 使用 Pumping 引理得到矛盾 −

  • 选择 w 使得 |w| ≥ c

  • 选择 y 使得 |y| ≥ 1

  • 选择 x 使得 |xy| ≤ c

  • 将剩余的字符串分配给 z。

  • 选择 k 使得结果字符串不在 L 中。

因此 L 不是正则的。

问题

证明 L = {aⁱbⁱ | i ≥ 0 不是正则的。

解决方案 −

• 首先，我们假设 L 是正则的，n 是状态数。

• 设 w = aⁿbⁿ。因此 |w| = 2n ≥ n。

• 通过引理，设 w = xyz，其中 |xy| ≤ n。

• 设 x = a^p，y = a^q，z = a^rbⁿ，其中 p + q + r = n，p ≠ 0，q ≠ 0，r ≠ 0。因此 |y| ≠ 0。

• 设 k = 2。则 xy²z = a^pa^2qa^rbⁿ。

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

• 因此，xy²z = a^n+q bⁿ。由于 q ≠ 0，xy²z 不属于 aⁿbⁿ 形式。

• 因此，xy²z 不属于 L。因此 L 不是正则的。