为常规语法泵送引理

---

定理

设 L 为常规语言。那么存在一个常量'c'，使得对于L中的每个字符串w -

|w| ≥c

我们可以将w分成三个字符串，w = xyz，这样 -

• |y| > 0
• |xy| ≤ c
• 对于所有 k ≥ 0，字符串 xy ^k z 也在 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 ^r b ⁿ，其中 p + q + r = n，p ≠ 0，q ≠ 0，r ≠ 0。因此 |y| ≠ 0。

• 令 k = 2。则 xy ² z = a ^p a ^2q a ^r b ⁿ。

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

• 因此，xy ² z = a ^n+q b ⁿ。由于 q ≠ 0，xy ^{2 z 不是 a n} b ⁿ的形式。

• 因此，xy ² z 不在L 中。因此L 不规则。