跳至內容

泵引理

維基百科,自由的百科全書

可計算性理論中的形式語言理論中,泵引理(Pumping lemma)聲稱給定類的任何語言可以被「抽吸」並仍屬於這個類。一個語言可以被抽吸,如果在這個語言中任何足夠長的字符串可以分解成片段,其中某些可以任意重複來生成語言中更長的字符串。這些引理的證明典型的需要計數論證比如鴿籠原理

兩個最重要例子是正則語言的泵引理上下文無關語言的泵引理鄂登引理是另一種更強的上下文無關語言的泵引理。

這些引理可以用來確定特定語言在給定語言類中。但是它們不能被用來確定一個語言在給定類中,因為滿足引理是類成員關係的必要條件,但不是充分條件。

泵引理是1961年由 Y. Bar-HillelM. PerlesE. Shamir首次發表的[1]

正則語言的泵引理

定義

假設正則語言,則存在整數,對任意字符串(n為泵長度,可理解為正則語言等效的極小化DFA的狀態個數),可以將寫成的形式,使得以下說法成立:

正確性的證明

  • 因為L是正則語言,所以存在一個與之等價的確定有限狀態自動機
  • 假設n是這個確定有限狀態自動機中狀態的數量,
  • 假設
  • 在這個自動機讀入w的前n個字符後一定有一個狀態達到過兩次,
  • 也就是說對於其中一種w的分解方式w=xyz有
  • 因此對於所有的都有

應用

通過泵引理可以用反證法證明L不是正則語言。證明的時候需要注意以下幾點:

  1. 假設要證明的語言為正則語言
  2. 是未知的
  3. 可以在滿足的條件下自由選擇
  4. 也是未知的
  5. 找到一個,使得,也就是說和泵引理的第三條矛盾

一個證明L不是正則語言的例子

  • 證明不是正則語言
    • 假設是正則語言,令n為泵引理常數
    • 選擇,則
    • 於是存在使得滿足條件
    • 因為且,所以中不包含但最少有一個
    • 的時候,的數量比多,所以
    • 與泵引理的第三條矛盾,因此不是正則語言

普遍化的泵引理[2]

並不是所有滿足泵引理的語言都是正則語言。就是這樣的一個例子,它雖然滿足泵引理,但並不是正則語言。Jeffrey Jaffe發展出了一個普遍化的泵引理,使它可以證明一個語言是正則語言。它的描述如下:

  • 一個語言是正則語言,若且唯若存在一個自然數,使得任意字符串可以通過至少一種方式被寫成的形式時,以下說法成立:

一個可行的用於判斷一個語言是否為正則語言的方法,可以參見邁希爾-尼羅德定理。一般來說證明一個語言是正則的,可以通過對該語言構造一個有限狀態機正則表達式來實現。

上下文無關語言的泵引理

定義

L上下文無關語言,則存在一常數 n > 0 使得語言 L 中每個字串 w 的長度 |w| ≧ n,而當 w = uvxyz 時:

  1. |vxy| ≦ n
  2. |vy| ≧ 1,且
  3. 對所有的 k ≧ 0,字串 uvkxykz 屬於 L

應用

透過泵引理反證法證明 L 不是上下文無關語言

  • ,換句話說,L 就是包含 所有字串且 abc 三者數目相同的語言。
    • n泵引理常數, 屬於 Lw = uvxyz,而 |vxy| ≤ n,|vy| ≥ 1,則 vxy 不可能同時包含 ac
      1. vxy 不包含 a 時,vy 只可能包含 bc,則 uxz 包含 na 及不到 n 個的 bc,使得 uxz 不屬於 L
      2. vxy 不包含 c 時,uxz 會包含 nc 及不到 n 個的 ab,使得 uxz 不屬於 L
    • 因此,無論是上述何種狀況,L 都不會是上下文無關語言
    • n泵引理常數,w = uvxyz,而 |vxy| ≤ n,|vy| ≥ 1
      1. vxy 只包含 a,則 uxz 會包含不到 nab,不屬於 L
      2. vxy 只包含 b,則 uxz 會包含 na 及不到 b,不屬於 L
      3. vxy 裏有 a 也有 b
        1. vy 包含 ab 不在 裏;
        2. v 只包含 la,且 y 只包含 mb 會包含 n + lkab,由於兩者都是線性成長,不可能永遠滿足 的條件,不屬於 L
    • 因此,無論是上述何種狀況,L 都不會是上下文無關語言。
    • n泵引理常數, 屬於 Lw = uvxyz,而 |vxy| ≤ n,則 vxy 必然為 形式(此處有)。即 vxy無法同時包含前後兩組0,也無法同時包含前後兩組1。將uvxyz轉變成uxz必然導致前後兩組0或兩組1的數目產生差異。使得uxz不再滿足ww形式。亦即uxz不屬於L
    • 因此,L 都不會是上下文無關語言。

引用

  1. ^ Y. Bar-Hillel, M. Perles, E. Shamir, "On formal properties of simple phrase structure grammars", Zeitschrift für Phonetik, Sprachweissenshaft und Kommunikationsforschung 14 (1961) pp. 143-172.
  2. ^ Jeffery Jaffe: A necessary and sufficient pumping lemma for regular languages頁面存檔備份,存於互聯網檔案館