# Theory of Computation Chapter 3, 4 - Regular Language

（請搭配達叔的投影片一起服用）

**正規語言 (Regular Language)**, 又稱**正則語言**，是滿足下述相互等價的一組條件的一類形式語言：
* 可以被**確定有限狀態自動機 (DFA)** 辨識
* 可以被**非確定有限狀態自動機 (NFA)** 辨識
* 可以用**正規表示式 (Regular Expression)** 描述
* 可以用**正規文法 (Regular Grammar)** 生成

（以上摘自[正規語言 - 維基百科](https://zh.wikipedia.org/wiki/%E6%AD%A3%E5%88%99%E8%AF%AD%E8%A8%80)）

## Regular Expression

### 如何描述一個語言

* 如果是有限集的語言，可以用窮舉法，如 $L = \{a, aa, aba, aca\}$
* 無窮集的語言，則可以用描述法，如 $L = \{x \mid n_a(x) = n_b(x)\}$
* 由於語言是一個集合，因此將多個語言用集合運算子進行運算後的結果也是一個語言，如 $L = \{aa, ab\}^* \cup \{b\}\{bb\}^*$

### 正規表達式 (Regular Expression)

* 是一種基於集合運算子進行擴充的語言描述方法
* 基本定義如下，給定一個字母表 $\Sigma$
* $\emptyset$, $\lambda$, 和 $a \in \Sigma$ 皆為描述這個語言的**原生正規表達式 (primitive regular expressions)**
* 如果 $r_1$ 和 $r_2$ 皆為正規表達式，則以下算式也都會是正規表達式
* $r_1 + r_2$
* $r_1 \cdot r_2$ （$\cdot$ 可省略）
* $r_1^*$
* $(r_1)$
* 一串字串是一個正規表達式，若且唯若該字串可以由有限個原生表達式和上述的運算子組成
* 舉例
$r = (a + b \cdot c)^*$， 用來描述 $L = \{\{a\} \cup \{bc\}\}^*$
* 因此 $L(r) = \{\lambda , a, bc, aa, abc, bca, ...\}$
* 要注意的事
* 正規表達式並不是一種語言，而是一個描述語言的工具
* 對於一個語言 $L$， 我們不能說 $L = (a + b + c)^*$， 但可以說這個 $L$ 能夠用 $(a + b + c)^*$ 描述

## Connection Between REs and Regular Languages

### 正規表達式描述的語言

* 對於所有的原生正規表達式，他們所接受的語言定義為
* $L(\emptyset) = \emptyset$
* $L(\lambda) = \{\lambda\}$
* $L(a) = \{a\}$
* 對於正規表達式 $r_1$ 和 $r_2$， 他們之間的運算子規則定義為
* $L(r_1 + r_2) = L(r_1) \cup L(r_2)$
* $L(r_1 \cdot r_2) = L(r_1)L(r_2)$
* $L(r_1^*) = (L(r_1))^*$
* $L((r_1)) = L(r_1)$
* 以上運算子之間的優先度， $()$ > $^*$ > $\cdot$ > $+$
* 給定兩個正規表達式 $r_1$ 和 $r_2$， 如果 $L(r_1) = L(r_2)$， 則我們說 $r_1$ 和 $r_2$ 是等價的

### 克萊尼定理 (Kleene Theorem)

* 正規表達式可以描述的語言集合，就是正規語言
* **克萊尼定理 (Kleene Theorem)**： 由於正規表達式和有限自動機所能夠描述 / 接受的語言集合是一樣的，因此可以說**正規表達式等價於有限自動機**
* 對於每一個正規語言，都存在一條正規表達式可以描述他；對於每一個正規表達式，都存在其可以描述的一個正規語言
* 透過證明「正規表達式可描述的語言等同於正規語言」，可以證明克來尼定理
> Figure 1. 原生正規表達式可以很簡單的畫出對應的NFA
>
> Figure 2. $+$ 運算子的 NFA
>
> Figure 3. $\cdot$ 運算子的 NFA
>
> Figure 4. $^*$ 運算子的 NFA
* 證明「正規表達式可描述的語言 $\subseteq$ 正規語言」
* 如果針對每一個正規表達式所描述的語言，我們都能夠建立一個可以接受該語言的有限自動機的話，就能證明正規表達式所描述的語言包含於正規語言
* 對於原生正規表達式，其描述的語言可以簡單的畫出 Fig. 1 中的 NFA
* 對於正規表達式當中所有的運算子，他們的規則都可以用 Fig. 2-4 的 NFA 表達（ $()$ 運算子不用 NFA 也可以得知）
* 透過這些 NFA， 我們可以將正規表達式當中的每一個運算都畫出來，並且組合在一起，得到最後只有一個終止狀態的 NFA
* 由於所有的正規表達式都可以做這樣的轉換（所有的正規表達式都有一個對應的 NFA），所以正規表達式可以描述的語言包含於正規語言
* 同時我們也得知，在這些運算子之下，正規語言會形成一個[閉包 (Closure)](https://zh.wikipedia.org/zh-tw/%E9%97%AD%E5%8C%85_(%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6))
> Figure 5. 這張圖的正規表達式為 $r = r1^*r2(r4 + r3r1^*r2)^*$
* 證明「正規語言 $\subseteq$ 正規表達式可描述的語言」
* 泛化狀態轉移圖 (Generalized Transition Graphs, GTG)， 是一個狀態轉移圖，其每一個有向邊都是一條正規表達式
* 每一個 NFA 都可以透過合併轉移函式和合併狀態的方式轉換成一個 GTG。 當一個 NFA 被化簡為只有起始狀態和終止狀態的 GTG 後，就可以簡單的得到與該 NFA 等價的正規表達式
* 值得注意的是，當我們要將 NFA 轉換成 Complete GTG （所有的邊都填上的 GTG） 時
* 由於 NFA 允許轉移函式的輸出為空集合，因此在轉換成 GTG 時需要補上一個 $\emptyset$ 的自環，而我們額外定義 $\emptyset^* = \lambda$
* 由於 NFA 原本的轉移函式中，可能會有一個狀態無法走到另一個狀態，在無法連通的狀態之間，也需要補上 $\emptyset$ 的路徑，而我們額外定義 $r + \emptyset = r$， $r \cdot \emptyset = \emptyset$
* 由於每一個 NFA 都可以透過 GTG 轉換得到一條對應的正規表達式，因此正規語言包含於正規表達式可以接受的語言
* 由於兩個集合互相包含對方，證明兩個集合相等，所以正規語言等於正規表達式可描述的語言

## Regular Grammars

### 形式文法(Grammars)

* 可以表示為一個四元組 $(V, T, S, P)$
* $V$ 是**非終結符號 / 變數 (variables)** 的有限集
* $T$ 是**終止符號 (terminals)** 的有限集
* $S$ 是**起始符號 (start variable)**， $S \in V$
* $P$ 是**產生式規則 (production rules)** 的有限集
* 給定一個形式文法 $G$， 根據以上定義，其可以產生的語言為 $L(G) = \{w \in T^* : S \Rightarrow w \}$
* 如果 $w \in L(G)$， 則序列 $S \Rightarrow w_1 \Rightarrow w_2 \Rightarrow ... \Rightarrow w_n \Rightarrow w$ 為 $w$ 的**推導 (derivation)**
* 其中 $S, w_1, w_2, ... w_n$ （在代換的途中還有變數沒被換掉的狀態）稱為**句型 (sentential form)**
* 線性文法 (Linear Grammar) 為形式文法的子集，其所有的產生是規則的右手邊最多只包含一個變數
* **右線性文法 (Right-Linear Grammar)**， 為線性文法當中，所有規則右手邊中唯一的變數都在最右邊的文法
* **左線性文法 (Left-Linear Grammar)**， 為線性文法當中，所有規則右手邊中唯一的變數都在最左邊的文法
* 左線性文法和右線性文法都屬於**正規文法 (Regular Grammar)**

### 正規文法與正規語言

* 正規文法產生的語言集合，就是正規語言
* 證明「正規文法可產生的語言 $\subseteq$ 正規語言」
* 如果是右線性文法，可以透過以下映射將文法轉換成有限自動機
* 將每一個變數都視為狀態，起始符號視為起始狀態，終止符號視為終止狀態
* 將每一條產生式規則都視為是一個轉移函式，如 $A \rightarrow aB$ 可以視為 $\delta (A, a) = B$
* 從起始符號開始，將所有的產生式規則都視為轉移函式畫為狀態機，直到連接終止符號為止
* 得到一個等價於該文法的 NFA
* 如果是左線性文法，則透過以下映射
* 將每一個變數都視為狀態，起始符號視為終止狀態，終止符號視為起始狀態
* 將每一條產生式規則都視為是一個反向的轉移函式，如 $A \rightarrow Ba$ 可以視為 $\delta (B, a) = A$
* 從終止符號開始，將所有的產生式規則都視為轉移函式畫為狀態機，直到連起始符號為止
* 由於起始狀態只能有一個，所以在多個起始狀態前多加一個起始狀態，並且用空字串轉移連接到原本的多個起始狀態，得到一個等價於該文法的 NFA
* 由於所有的正規文法都可以透過以上映射得到等價的 NFA，所以正規文法產生的語言包含於正規語言
* 證明「正規語言 $\subseteq$ 正規文法可產生的語言」
* 由於有限狀態機當中的每個元素都可以對應正規文法中的某些元素（如上方證明所述），所以可以透過反向映射的方式，用跟上方相似的步驟，將有限狀態機以一個正規文法描述（敘述略）
* 由於所有的正規語言都對應到一個有限狀態機，而每一個有限狀態機都可以轉換為正規文法，所以正規語言包含於正規文法所產生的語言
* 兩個集合互相包含對方，證明兩個集合相等，所以正規語言等於正規文法可產生的語言

## Closure Properties of Regular Languages

略。

## Elementary Questions about Regular Languages

* 目前為止我們已經學過了幾種正規語言的標準表達方式 (Standard Representation)，包含：
* 確定有限狀態自動機 (DFA)
* 非確定有限狀態自動機 (NFA)
* 正規表示式 (Regular Expression)
* 正規文法 (Regular Grammar)
* 當我們說有一個正規語言 $L$， 這表示 $L$ 一定是以上述幾個方法之一來描述的

### Some Questions about Regular Language

* 給定一個正規語言 $L$ 和一個字串 $w$， 我們怎麼確認 $w \in L$ ？ (Membership Question)
* 畫出一個可以接受 $L$ 的 DFA， 然後看看 $w$ 能不能被該 DFA 接受。若能，則 $w$ 屬於 $L$， 反之則否
* 給定一個正規語言 $L$， 我們怎麼確認 $L$ 是空集合 （$L = \emptyset$）？
* 畫出一個可以接受 $L$ 的 DFA， 然後看看起始狀態是否有路徑可以走到終止狀態。若有，則 $L$ 非空集合，反之則是空集合
* 給定一個正規語言 $L$， 我們怎麼確認 $L$ 是有限集合 (finite set)？
* 畫出一個可以接受 $L$ 的 DFA， 然後看看從起始狀態走到終點狀態的路徑中有沒有環的存在。若有，則 $L$ 不是有限集合，反之則是有限集合
* 給定兩個正規語言 $L_1$ 和 $L_2$， 我們怎麼確認 $L_1 = L_2$ ？
* 確認是否 $(L_1 \cap L_2) \cup (L_1 \cap L_2) = \emptyset$ 。若是，則 $L_1 = L_2$， 反之則否

## Identifying Nonregular Languages

> Figure 6. 有限語言 $\subset$ 正規語言 $\subset$ 非正規語言

有些語言並不屬於正規語言的集合，我們該如何證明一個語言 $L$ 不是正規語言呢？我們或許可以證明沒有任何一個 DFA 可以接受這個語言，但是窮舉出所有的 DFA 並不是一件容易的事（是做不到的事），所以我們需要用到一個工具 —— **泵引理 (Pumping Lemma)**。

### Pigeonhole Principle

*參考離散數學。*

簡單來說，如果有 $m$ 隻鴿子要裝進 $n$ 個鴿籠，當 $m > n$ 時，必定會有某個籠子裡至少有兩隻鴿子。

### Pigeonhole Principle and DFAs

> Figure 7. 鴿籠定理與 DFA

對於任意一個有 $n$ 個狀態的 DFA $M$， 如果有一個字串 $w$， 其中 $|w| \geq m$， 則 $w$ 在 $M$ 當中所經過的路徑，必定有其中一個狀態 $q$ 被重複走過了至少兩次，如 Fig. 7 所示。

> Figure 8. 一個長度為 4 的 DFA
* 例如： 對於 Fig. 8 中的 DFA 來說， $a$, $aa$, $aab$ 等字串因為長度小於該 DFA 的狀態數量，所以不一定有重複走過的狀態。但是像 $aabb$, $bbaa$, $bababb$ 這些字串，其長度已經大於或等於該 DFA 的狀態數量了，所以在 DFA 消化他的過程當中，必定會有至少一個狀態被走過了兩次

### Pumping Lemma

* 定義： 給定一個無限正規語言 $L$， 必定存在一個整數 $m$ （代表可以接受 $L$ 的 DFA 的狀態數量），對於任意字串 $w \in L$ 且 $|w| \geq m$， 可以表示為 $w = xyz$， 其中 $|xy| \leq m$ 且 $|y| \geq 1$， 使得 $xy^iz \in L , i = 0, 1, 2,...$
:::danger
很重要！！ 上面要整段背起來！！
:::
* 應用： 可以搭配反證法來證明某語言**不是**正規語言。證明過程如下：
1. 假設給定的語言為正規語言，故滿足 pumping lemma （需要完整寫出上面這一段）
2. 舉出任意一個字串 $w$， 此字串必須要滿足 $w \in L$ 且 $|w| \geq m$， 所以通常會將 $m$ 用在該字串的參數當中
3. 將 $w$ 拆解成 $xyz$ 三段，其中 $|xy| \leq m$ 且 $|y| \geq 1$， 注意 $xy$ 的選擇務必滿足這些條件
4. 證明至少有一個 $xy^iz$ 不屬於 $L$
5. 由於 4. 違反了 pumping lemma， 跟「給定的語言是正規語言」的假設矛盾，故給定的語言並非正規語言
* Pumping lemma 常見的誤用
* 用 Pumping lemma 證明某語言是正規語言
* 就算一個語言符合 pumping lemma， 也不能保證他一定是正規語言。 符合 pumping lemma 是正規語言的充份條件，而不是必要條件
* 在 2. 時舉出了一個不在 $L$ 當中的字串
* 例： $L = \{a^n: \textrm{n is a prime number}\}$
* $w = a^m$ 並不是一個好的選項，因為 $m$ 不一定是質數
* $w = a^P$， 其中 $P$ 是一個比 $m$ 大的質數，才是正確的挑法
* 對於 $xyz$ 分解做出過度假設
* 例： $L = \{a^n: \textrm{n is a prime number}\}$
* 令 $y = ak$， 其中 $k$ 是一個奇數。這是一個不對的假設，因為這樣沒有考慮到 $k$ 是偶數時的狀況