# 前言

如果一個語言是由正常表達所描述，那麼我們可以知道該語言是正常的。

所以現在換想要知道哪些語言是不正常的。

方法其實就是透過一點邏輯。

## $P\rightarrow Q \equiv \sim Q \rightarrow \sim P$

如同標題所述，我們現在想要知道：

如果「 A 是正常語言」，則「A 會具有甚麼性質」。

因為當我們找到後，只要有一個 B 沒有該性質，那麼他就是不正常的。

但是也要記得，就算 B 是不正常的，他還是有可能會有該性質。

# Pumping Lemma

下面就是上面提到的性質：

對於一個正常語言 $A$，存在一個正整數 $p$，對於所有的字串 $s\in A$，只要 $|s|\ge p$，那麼 $s$ 一定可以分解成三個子字串 $s=xyz$，並且：

- $xy^{i}z \in A, i\ge 0$
- $|y|>0$
- $|xy|\le p$

:::info
如果 $A$ 裡面沒有字串長度大於等於 $p$，那...甚麼事也不會發生，頂多就是無法使用 Pumping Lemma。
:::

至於為甚麼會有這三個神奇性質，還有那個神奇的正整數 $p$，全都要從鴿籠原理講起...。

## 鴿籠原理

如果你有 10 隻鴿子跟 9 個籠子，如果你要隨意的放鴿子到籠子裡面，並且每個籠子很寬可以塞 10 隻鴿子，那麼我們知道，最少最少，一定會有一個籠子有兩隻鴿子。
>課本沒有講「最少有 at least」而是講「一定有 must」，害我誤解了好一段時間

這時候回到上面，我們直接通靈，令 $p$ 為總共狀態的數量：$p=|Q|$。

對所有的 $s\in A$，令字串長度 $|s|=n$，所以可知經過的狀態數量為 $n+1$。

只要當 $n\ge p$，可以知道 $n+1\ge p+1$；然而總共狀態最多就 $p$ 個，根據鴿籠原理，至少有一個(以上)狀態一定會重複。這裡我們令那個重複的狀態為 $q_{middle}$，而樣子就像下圖：


可以看到這個字串在遇到 $q_{middle}$ 後就有個環的結構，而環的位置可能在這 $n+1$ 個狀態中的任意兩個狀態：

- 從 $q_{start}$ 到 $q_{middle}$ 之間所讀取的字元，就是 $x$ 的部分
- $q_{middle}$ 中間繞一圈所讀取的字元，就是 $y$ 的部分
- 從 $q_{middle}$ 到 $q_{accept}$ 之間所讀取的字元，就是 $z$ 的部分

:::warning
當然，只要 $n > p$，其他地方一定會有一樣繞圈圈的結構，但這裡我們只專注一個這樣繞圈圈的結構就好。
:::

這樣一來對於那三個性質：

- $xy^{i}z \in A, i\ge 0$
- 因為 $y^{i}$ 就是一直在繞圈圈，確實是在 $A$ 裡面的字串
- $|y|>0$
- 因為 $q_{middle}$ 是會重複的狀態
- 所以最少的情況就是從 $q_{middle}$ 讀到一個字元，再走回 $q_{middle}$，然後離開
- 因此只少有一個字元
- $|xy|\le p$
- 當我們只看前 $p+1$ 個狀態，根據鴿籠原理，一定會至少發生一次環的結構
- 如果是只發生一次環的情形，那麼長度最長的可能就是從第一個狀態就進入環，然後中間經過了 $p-1$ 個狀態，再走回來
- 所以可以知道這個環的大小最大就是 $p+1$ 個狀態，因此 $|xy|$ 的長度最大就是 $p$，並且此時 $|x|=0$
- 所以如果在前 $p+1$ 個狀態就發生很多次環的話，就是小於的情形了

# 如何使用

基本上就是照著邏輯的推斷去弄。

## 法一，假設 A 是正常的

那麼根據 pumping lema ，他一定存在一個 p ，語言內的所有字串只要長度大於等於 p ，就一定會有上面那三個性質。

所以重點就是，你要如何挑出一個字串，他沒辦法滿足任一個性質。

當中的第三點 $|xy|\le p$ 實用性質很大，因為他限定了字串的 y 所位在的位置，要在前 p 個字母內，而這通常在第一點 $xy^{i}z \in A, i\ge 0$ 時很容易就無法滿足，所以就可以知道會造成矛盾。

## 法二，組合大師

由先前的三種正常操作，聯集、貓咪、星星，還有多一個，交集。

這四個操作之前有推導具有封閉性，所以你可以把要證明的語言 B，先跟某個正常的語言 A 湊出語言 C，如果 C 是已經證明過，或是很好證明他不正常的化，就可以透過封閉性來推導出 B 不正常，因為如果 B 跟 A 都正常的話，那 C 應該也要是正常的。