正則文法的泵引理

定理

設 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 不是正則的。