正則語言的泵引理是什麼？

有兩個泵引理 (PL)，分別定義用於正則語言和上下文無關語言。

正則語言的泵引理

  • 它提供了一種從給定字串中“泵出”（生成）許多子串的方法。
  • 換句話說，它提供了一種將給定的長輸入字串分解成幾個子串的方法。
  • 它給出了證明一組字串不是正則的必要條件。

定理

對於任何正則語言 L，存在一個整數 P，使得對於 L 中的所有 w

|w|>=P

我們可以將 w 分解成三個字串，w=xyz，使得。

(1)|xy| < P

(2)|y| > 1

(3)對於所有 k>= 0：字串 xykz 也在 L 中

泵引理的應用

泵引理用於證明某些語言不是正則的。

它不應用於證明語言是正則的。

  • 如果 L 是正則的，則它滿足泵引理。
  • 如果 L 不滿足泵引理，則它不是正則的。

**使用 PL 證明語言不是正則的步驟**如下：

  • 步驟 1 - 我們必須假設 L 是正則的
  • 步驟 2 - 因此，泵引理應該適用於 L。
  • 步驟 3 - 它必須有一個泵長度（例如 P）。
  • 步驟 4 - 所有長度大於 P 的字串都可以泵出 |w|>=p。
  • 步驟 5 - 現在在 L 中找到一個字串 'w'，使得 |w|>=P
  • 步驟 6 - 將 w 分解成 xyz。
  • 步驟 7 - 證明對於某些 i，xyiz ∉ L。
  • 步驟 8 - 然後考慮 w 可以分解成 xyz 的所有方式。
  • 步驟 9 - 證明這些方式中沒有一個可以同時滿足所有 3 個泵條件。
  • 步驟 10 - w 不能被泵出 = 矛盾。

更新於：2021年6月11日

54K+ 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告