正则文法的泵引理

定理

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

|w| ≥ c

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

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

泵引理的应用

泵引理用于证明某些语言不是正则语言。它不应该用于证明语言是正则语言。

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

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

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

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

• 因此，泵引理应该适用于 L。

• 使用泵引理得出矛盾 −

  • 选择 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ⁿ。

• a 的个数 = (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 不是正则的。