2015年4月28日 星期二

Formal Language - Ch4 泵引理 Pumping Lemma

 

泵引理(Pumping Lemma)簡介
  • 給定任何一種形式語言,則該種語言可以被「抽吸」後仍屬於這個種類。
  • 這些引理的證明需要計數論證,如鴿籠原理
  • 這些引理可以用來確定特定語言不在給定的語言類別中,但是它們不能被用來確定一個語言在給定的類別中,因為滿足引理是必要條件而非充分條件。


抽吸(Pump)
如果在這個語言中任何足夠長的字符串可以分解成片段,其中某些可以任意重複來生成語言中更長的字符串,則稱一個語言可以被抽吸(pump)。


鴿籠原理 (Pigeonhole principle)
若有n個籠子和n+1隻鴿子,所有的鴿子都被關在鴿籠裡,那麼至少有一個籠子有至少2隻鴿子。
雖然鴿籠原理看起來很容易理解,但有時使用鴿籠原理會得到一些不直觀的結論,鴿籠原理經常在計算機領域得到真正的應用,如本章介紹的pumping lemma,或其他議題如:
  • hash表的重複問題(collison)是不可避免的,因為Key的數目總是比Index的數目多,不管是多麼高明的算法都不可能解決這個問題。
  • 任何無損壓縮算法,在把一個文件變小的同時,一定有其他文件增大來輔助,否則某些信息必然會丟失。



泵引理定義
假設$L \subseteq \Sigma^*$是正則語言,存在字符串$w \in L$且$\left| w \right| \ge n$(n為泵長度,可理解為正則語言等效的有限自動機DFA狀態個數),如果可以將$w$寫成$w = xyz$的形式時,以下說法成立:
  1. $\left| xy \right| \le n$
  2. $\left| y \right| \ge 1$
  3. $\forall k \ge 0:xy^kz \in L$

[用心去感覺] 泵引理的正確性來自鴿籠原理
  • 因為這個有限自動機中狀態的數量比輸入的字串長度小,$\left| w \right| \ge n$。
  • 所以在這個自動機讀入$w$的前$n$個字符後一定有一個狀態達到過兩次,$\delta^* \left( s,x \right)=\delta^* \left( s,xy \right)$。
  • 根據這個結論再推廣,$\delta^*(s,xyz) \in L \leftrightarrow \delta^*(s,xy^kz) \in L$

反證法證明 Nonregular Language
通過泵引理可以用反證法證明$L$不是正則語言。證明的時候需要注意以下幾點:
  1. 假設要證明的語言為正則語言
  2. $n$是未知的
  3. $w$可以在滿足$w \in L$和$\left| w \right| \ge n$的條件下自由選擇
  4. $x,y,z$也是未知的
  5. 找到一個$k$,$使得xy^kz \notin L$,也就是說和泵引理的第三條矛盾
下面是一個簡單的例子 :





Reference

交大陳穎平教授正規語言講義

wiki - 泵引理
http://zh.wikipedia.org/wiki/%E6%B3%B5%E5%BC%95%E7%90%86





技術提供:Blogger.