Theory of Computation Chapter 3, 4 - Regular Language

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

正規語言 (Regular Language), 又稱正則語言，是滿足下述相互等價的一組條件的一類形式語言：

• 可以被確定有限狀態自動機 (DFA) 辨識
• 可以被非確定有限狀態自動機 (NFA) 辨識
• 可以用正規表示式 (Regular Expression) 描述
• 可以用正規文法 (Regular Grammar) 生成

（以上摘自正規語言 - 維基百科）

Regular Expression

如何描述一個語言

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

正規表達式 (Regular Expression)

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

Connection Between REs and Regular Languages

正規表達式描述的語言

• 對於所有的原生正規表達式，他們所接受的語言定義為
  • $L(\mathrm{\varnothing })=\mathrm{\varnothing }$
  • $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^{\ast })=(L(r_1){)}^{\ast }$
  • $L((r_1))=L(r_1)$
  • 以上運算子之間的優先度，
    $()$ >
    ${}^{\ast }$ >
    $\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.

  ${}^{\ast }$ 運算子的 NFA

  • 證明「正規表達式可描述的語言
    $\subseteq$ 正規語言」
    • 如果針對每一個正規表達式所描述的語言，我們都能夠建立一個可以接受該語言的有限自動機的話，就能證明正規表達式所描述的語言包含於正規語言
    • 對於原生正規表達式，其描述的語言可以簡單的畫出 Fig. 1 中的 NFA
    • 對於正規表達式當中所有的運算子，他們的規則都可以用 Fig. 2-4 的 NFA 表達（
      $()$ 運算子不用 NFA 也可以得知）
    • 透過這些 NFA， 我們可以將正規表達式當中的每一個運算都畫出來，並且組合在一起，得到最後只有一個終止狀態的 NFA
    • 由於所有的正規表達式都可以做這樣的轉換（所有的正規表達式都有一個對應的 NFA），所以正規表達式可以描述的語言包含於正規語言
    • 同時我們也得知，在這些運算子之下，正規語言會形成一個閉包 (Closure)
      

  Figure 5. 這張圖的正規表達式為

  $r=r{1}^{\ast }r2(r4+r3r{1}^{\ast }r2{)}^{\ast }$

  • 證明「正規語言
    $\subseteq$ 正規表達式可描述的語言」
    • 泛化狀態轉移圖 (Generalized Transition Graphs, GTG)， 是一個狀態轉移圖，其每一個有向邊都是一條正規表達式
    • 每一個 NFA 都可以透過合併轉移函式和合併狀態的方式轉換成一個 GTG。 當一個 NFA 被化簡為只有起始狀態和終止狀態的 GTG 後，就可以簡單的得到與該 NFA 等價的正規表達式
    • 值得注意的是，當我們要將 NFA 轉換成 Complete GTG （所有的邊都填上的 GTG） 時
      • 由於 NFA 允許轉移函式的輸出為空集合，因此在轉換成 GTG 時需要補上一個
        $\mathrm{\varnothing }$ 的自環，而我們額外定義
        ${\mathrm{\varnothing }}^{\ast }=\lambda$
      • 由於 NFA 原本的轉移函式中，可能會有一個狀態無法走到另一個狀態，在無法連通的狀態之間，也需要補上
        $\mathrm{\varnothing }$ 的路徑，而我們額外定義
        $r+\mathrm{\varnothing }=r$，
        $r\cdot \mathrm{\varnothing }=\mathrm{\varnothing }$
    • 由於每一個 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^{\ast }: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\to aB$ 可以視為
      $\delta (A,a)=B$
    • 從起始符號開始，將所有的產生式規則都視為轉移函式畫為狀態機，直到連接終止符號為止
    • 得到一個等價於該文法的 NFA
  • 如果是左線性文法，則透過以下映射
    • 將每一個變數都視為狀態，起始符號視為終止狀態，終止符號視為起始狀態
    • 將每一條產生式規則都視為是一個反向的轉移函式，如
      $A\to 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=\mathrm{\varnothing }$）？
  • 畫出一個可以接受
    $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)=\mathrm{\varnothing }$ 。若是，則
    $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|\ge 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|\ge m$， 可以表示為
  $w=xyz$， 其中
  $|xy|\le m$ 且
  $|y|\ge 1$， 使得
  $x{y}^{i}z\in L,i=0,1,2,...$

  很重要！！ 上面要整段背起來！！

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