- 給定任何一種形式語言，則該種語言可以被「抽吸」後仍屬於這個種類。
- 這些引理的證明需要計數論證，如鴿籠原理。
- 這些引理可以用來確定特定語言不在給定的語言類別中，但是它們不能被用來確定一個語言在給定的類別中，因為滿足引理是必要條件而非充分條件。
抽吸(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$的形式時，以下說法成立：
- $\left| xy \right| \le n$
- $\left| y \right| \ge 1$
- $\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$不是正則語言。證明的時候需要注意以下幾點：
通過泵引理可以用反證法證明$L$不是正則語言。證明的時候需要注意以下幾點：
- 假設要證明的語言為正則語言
- $n$是未知的
- $w$可以在滿足$w \in L$和$\left| w \right| \ge n$的條件下自由選擇
- $x,y,z$也是未知的
- 找到一個$k$，$使得xy^kz \notin L$，也就是說和泵引理的第三條矛盾
發表文章
沒有留言:
張貼留言