《形式語言與自動機理論（第4版）》筆記（三）

文章目錄

@[toc]
前導
《形式語言與自動機理論（第4版）》筆記（一）
《形式語言與自動機理論（第4版）》筆記（二）

第四章：正則表達式
4.1|啟示
4.2|正則表達式的形式定義
正則表達式性質

4.3|正則表達式與 $F A$ 等價
正則表達式表示的語言是正則語言
$n = 0$ 時
$\varepsilon$
$\emptyset$
$\forall a \in \Sigma$ ， $r = a$

$n = k + 1$ 時
$r = r_{1} + r_{2}$
$r = r_{1} r_{2}$
$r = r_{1}^{*}$

例題
問題
解答

正則語言可以用正則表達式表示
構造與 $D F A$ 等價的正則表達式
圖上作業方法
預處理
循環操作

4.4|正則語言等價模型的總結

前導

《形式語言與自動機理論（第4版）》筆記（一）

《形式語言與自動機理論（第4版）》筆記（二）

第四章：正則表達式

4.1|啟示

4.2|正則表達式的形式定義

正則表達式性質

$\varepsilon)^{*}) = L(r^{*})$
$L((r^{*} s^{*})^{*}) = L((r + s)^{*})$

4.3|正則表達式與 $F A$ 等價

正則表達式表示的語言是正則語言

施歸納于正則表達式中所含運算符的個數 $n$ ，證明對于字母表 $\Sigma$ 上的任意正則表達式 $x$ ，存在 $\ M$ ，使得 $L (M) = L (x)$ ，并且 $M$ 恰有一個終止狀態，而且 $M$ 在終止狀態下不做任何移動

$n = 0$ 時

$\varepsilon$

$\emptyset$

$\forall a \in \Sigma$ ， $r = a$

$n = k + 1$ 時

$r = r_{1} + r_{2}$

此時 $r_{1}$ ， $r_{2}$ 種運算符的個數不會大于 $k$ ，由歸納假設，存在滿足定理要求的 $\varepsilon-NFA$ ， $M_{1} = (Q_{1} , \Sigma , \delta_{1} , q_{01} , \set{f_{1}})$ ， $M_{2} = (Q_{2} , \Sigma , \delta_{2} , q_{02} , \set{f_{2}})$ ，使得 $L(M_{1}) = L(r_{1})$ ， $L(M_{2}) = L(r_{2})$
不妨設 $Q_{1} \cup Q_{2} = \emptyset$ ，取 $q_{0}$ ， $\notin Q_{1} \cup Q_{2}$ ，令 $(Q_{1} \cup Q_{2} \cup \set(q_{0} , f) , \Sigma , \delta , q_{0} , \set{f})$ ，其中 $\delta$ 的定義為
- $\delta(q_{0} , \varepsilon) = \set{q_{01} , q_{02}}$
- 對 $\forall q \in Q_{1} - \set{f_{1}}$ ， $\in \Sigma \cup \set{\varepsilon}$ ， $\delta(q , a) = \delta_{1}(q , a)$ ，對 $\forall q \in Q_{2} - \set{f_{1}}$ ， $\in \Sigma \cup \set{\varepsilon}$ ， $\delta(q , a) = \delta_{2}(q , a)$
- $\delta(f_{1} , \varepsilon) = \set{f}$
- $\delta(f_{2} , \varepsilon) = \set{f}$

往證 $L(r_{1} + r_{2}) = L(M)$
- 由歸納假設， $L(r_{1}) = L(M_{1})$ ， $L(r_{2}) = L(M_{2})$ ，根據正則表達式的定義 $L(r_{1} + r_{2}) = L(r_{1}) \cup L(r_{2})$ ， $L(r_{1} + r_{2}) = L(M_{1}) \cup L(M_{2})$ ，因此，只需要證明 $L(M_{1}) \cup L(M_{2})$
- 先證 $L(M_{1}) \cup L(M_{2}) \subseteq L(M)$
  - 設 $\in L(M_{1}) \cup L(M_{2})$ ，從而有 $\in L(M_{1})$ ，或者 $\in L(M_{2})$
  - 當 $\in L(M_{1})$ 時，有 $\delta_{1}(q_{01} , x) = \set{f_{1}}$
  - 由 $M$ 的定義可得 $\begin{aligned} \delta(q_{0} , x) &= \delta(q_{0} , \varepsilon x \varepsilon) \\ &= \delta(\delta(q_{0} , \varepsilon) , x \varepsilon) \\ &= \delta(\set{q_{01} , q_{02}} , x \varepsilon) \\ &= \delta(q_{01} , x \varepsilon) \cup \delta(q_{02} , x \varepsilon) \\ &= \delta(\delta(q_{01} , x) , \varepsilon) \cup \delta(\delta(q_{02} , x) , \varepsilon) \\ &= \delta(\delta_{1}(q_{01} , x) , \varepsilon) \cup \delta(\delta_{2}(q_{02} , x) , \varepsilon) \\ &= \set{f} \cup \delta(\delta_{2}(q_{02} , x) , \varepsilon) \end{aligned}$
  - 即 $\in L(M)$
  - 同理可證，當 $\in L(M_{2})$ 時， $\in L(M)$
- 再證 $\subseteq L(M_{1}) \cup L(M_{2})$
  - 設 $\in L(M)$ ， $\in \delta(q_{0} , x)$
  - 按照 $M$ 的定義， $\begin{aligned} \delta(q_{0} , x) &= \delta(q_{0} , \varepsilon x \varepsilon) \\ &= \delta(\delta(q_{0} , \varepsilon) , x \varepsilon) \\ &= \delta(\set{q_{01} , q_{02}} , x \varepsilon) \\ &= \delta(q_{01} , x \varepsilon) \cup \delta(q_{02} , x \varepsilon) \\ &= \delta(\delta(q_{01} , x) , \varepsilon) \cup \delta(\delta(q_{02} , x) , \varepsilon) \\ &= \delta(\delta_{1}(q_{01} , x) , \varepsilon) \cup \delta(\delta_{2}(q_{02} , x) , \varepsilon) \end{aligned}$
  - $\in \delta(q_{0} , x)$ ，并且此時 $M$ 的最后一次移動必是根據 $\delta(f_{1} , \varepsilon) = \set{f}$ 或 $\delta(f_{2} , \varepsilon) = \set{f}$ 之一進行的移動
    - 如果是根據定義式 $\delta(f_{1} , \varepsilon) = \set{f}$ 進行的最后一次移動，此時必有 $\delta_{1}(q_{01} , x) = \set{f_{1}}$ ， $\in L(M_{1})$
    - 如果是根據定義式 $\delta(f_{2} , \varepsilon) = \set{f}$ 進行的最后一次移動，此時必有 $\delta_{2}(q_{02} , x) = \set{f_{2}}$ ， $\in L(M_{2})$
  - 無論是哪一種情況，都有 $\in L(M_{1}) \cup L(M_{2})$

$r = r_{1} r_{2}$

此時 $r_{1}$ 、 $r_{2}$ 中運算符的個數不會大于 $k$ ，由歸納假設，存在滿足定理要求的 $\varepsilon-NFA$ ， $M_{1} = (Q_{1} , \Sigma , \delta_{1} , q_{01} , \set{f_{1}})$ ， $M_{2} = (Q_{2} , \Sigma , \delta_{2} , q_{02} , \set{f_{2}})$ ，使得 $L(M_{1}) = L(r_{1})$ ， $L(M_{2}) = L(r_{2})$ ，而且 $Q_{1} \cap Q_{2} = \emptyset$
取 $(Q_{1} \cup Q_{2} , \Sigma , \delta , q_{01} , \set{f_{2}})$ ，其中 $\delta$ 的定義為
- 對 $\forall q \in Q_{1} - \set{f_{1}}$ ， $\in \Sigma \cup \set{\varepsilon}$ ， $\delta(q , a) = \delta_{1}(q , a)$
- 對 $\forall q \in Q_{2}$ ， $\in \Sigma \cup \set{\varepsilon}$ ， $\delta(q , a) = \delta_{2}(q , a)$
- $\delta(f_{1} , \varepsilon) = \set{q_{02}}$

往證 $L(r_{1} r_{2}) = L(M)$
- 由歸納假設， $L(r_{1}) = L(M_{1})$ ， $L(r_{2}) = L(M_{2})$ ，根據正則表達式的定義 $L(r_{1} r_{2}) = L(r_{1}) L(r_{2})$ ， $L(r_{1} r_{2}) = L(M_{1}) L(M_{2})$ ，因此，只需要證明 $L(M) = L(M_{1}) L(M_{2})$
- 先證 $L(M_{1}) L(M_{2}) \subseteq L(M)$
  - 設 $\in L(M_{1}) L(M_{2})$ ，從而有 $x_{1} \in L(M_{1})$ 并且 $x_{2} \in L(M_{2})$ ，使得 $x = x_{1} x_{2}$
  - $\delta(q_{01} , x_{1}) = \delta_{1}(q_{01} , x_{1}) = \set{f_{1}}$ ， $\delta(q_{02} , x_{2}) = \delta_{2}(q_{02} , x_{2}) = \set{f_{2}}$
  - $\begin{aligned} \delta(q_{01} , x) &= \delta(q_{01} , x_{1} x_{2}) \\ &= \delta(\delta(q_{01} , x_{1}) , x_{2}) \\ &= \delta(\delta_{1}(q_{01} , x_{1}) , x_{2}) \\ &= \delta(f_{1} , x_{2}) \\ &= \delta(f_{1} , \varepsilon x_{2}) \\ &= \delta(\delta(f_{1} , \varepsilon) , x_{2}) \\ &= \delta(q_{02} , x_{2}) \\ &= \delta_{2}(q_{02} , x_{2}) \\ &= \set{f_{2}} \end{aligned}$
  - 即 $\in L(M)$
- 再證 $\subseteq L(M_{1}) L(M_{2})$
  - 設 $\in L(M)$ ， $\delta(q_{01} , x) = \set{f_{2}}$
  - 必存在 $x$ 的前綴 $x_{1}$ 和后綴 $x_{2}$ ，使得 $x = x_{1} x_{2}$ ，并且 $x_{1}$ 將 $M$ 從狀態 $q_{01}$ 引導到狀態 $f_{1}$ ， $x_{2}$ 將 $M$ 從狀態 $q_{02}$ 引導到狀態 $f_{2}$ ，即 $\begin{aligned} \delta(q_{01} , x) &= \delta(q_{01} , x_{1} x_{2}) \\ &= \delta(f_{1} , x_{2}) \\ &= \delta(f_{1} , \varepsilon x_{2}) \\ &= \delta(q_{02} , x_{2}) \\ &= \set{f_{2}} \end{aligned}$
  - 其中， $\delta(q_{01} , x_{1}) = \set{f_{1}}$ ，說明 $\delta_{1}(q_{01} , x_{1}) = \set{f_{1}}$ ， $\delta(q_{02} , x_{2}) = \set{f_{2}}$ ，說明 $\delta_{2}(q_{02} , x_{2}) = \set{f_{2}}$ ，這表明 $x_{1} \in L(M_{1})$ ， $x_{2} \in L(M_{2})$
  - 從而 $x_{1} x_{2} \in L(M_{1}) L(M_{2})$

$r = r_{1}^{*}$

此時 $r_{1}$ 中運算符的個數不會大于 $k$ ，由歸納假設，存在滿足定理要求的 $\varepsilon-NFA$ ， $M_{1} = (Q_{1} , \Sigma , \delta_{1} , q_{01} , \set{f_{1}})$ ，使得 $L(M_{1}) = L(r_{1})$
取 $(Q_{1} \cup \set{q_{0} , f} , \Sigma , \delta , q_{0} , \set{f})$ ，其中 $q_{0}$ ， $\notin Q_{1}$ ， $\delta$ 的定義為
- 對 $\forall q \in Q_{1} - \set{f_{1}}$ ， $\in \Sigma$ ， $\delta(q , a) = \delta_{1}(q , a)$
- $\delta(f_{1} , \varepsilon) = \set{q_{01} , f}$
- $\delta(q_{0} , \varepsilon) = \set{q_{01} , f}$

往證 $L(r_{1}^{*}) = L(M)$
- 由歸納假設， $L(M_{1}) = L(r_{1})$ ，根據正則表達式的定義 $L(r) = (L(r_{1}))^{*}$ ，只需證明 $L(M) = (L(M_{1}))^{*}$
- 先證 $\subseteq (L(M_{1}))^{*}$
  - 設 $\in L(M)$ ，如果 $\varepsilon$ ，由克林閉包的定義，顯然 $\in (L(M_{1}))^{*}$
  - 如果 $\neq \varepsilon$ ，由 $M$ 的定義，必定存在 $x_{1}$ ， $x_{2}$ ， $\cdots$ ， $x_{n}$ ， $x_{1} x_{2} \cdots x_{n} (n \geq 1)$ 滿足 $\begin{aligned} \delta(q_{0} , x) &= \delta(q_{0} , x_{1} x_{2} \cdots x_{n}) \\ &= \delta(\delta(q_{0} , \varepsilon) , x_{1} x_{2} \cdots x_{n}) \\ &= \delta(q_{01} , x_{1} x_{2} \cdots x_{n}) \\ &= \delta(\delta_{1}(q_{01} , x_{1}) , x_{2} \cdots x_{n}) \\ &= \delta(f_{1} , x_{2} \cdots x_{n}) \\ &\cdots \\ &= \delta(f_{1} , x_{n}) \\ &= \delta(\delta(f_{1} , \varepsilon) , x_{n}) \\ &= \delta(q_{01} , x_{n}) \\ &= \delta(\delta_{1}(q_{01} , x_{n}) , \varepsilon) \\ &= \delta(f_{1} , \varepsilon) \\ &= \set{f} \end{aligned}$
  - 這表明 $x_{1} x_{2} \cdots x_{n} \in (L(M_{1}))^{*}$
- 再證 $(L(M_{1}))^{*} \subseteq L(M)$
  - 類似地，不難證明 $(L(M_{1}))^{*} \subseteq L(M)$

例題

問題

構造與正則表達式 $0 + 1)^{*} 0 + (00)^{*}$ 等價的 $F A$

解答

正則語言可以用正則表達式表示

構造與 $D F A$ 等價的正則表達式

設 $\ M = (\set{q_{1} , q_{2} , \cdots , q_{n}} , \Sigma , \delta , q_{1} , F)$
令 $R_{ij}^{k} = \set{x \mid \delta(q_{i} , x) = q_{j} , 而且對于 x 的任意前綴 y (y \neq x , y \neq \varepsilon) , 如果 \delta(q_{i} , y) = q_{l} , 則 l \leq k}$
為了便于計算，將 $R_{ij}^{k}$ 遞歸地定義為

$R_{ij}^{0} = \begin{cases} \set{a \mid \delta(q_{i} , a) = q_{j}} , & i \neq j \\ \set{a \mid \delta(q_{i} , a) = q_{j}} \cup \set{\varepsilon} , & i = j \end{cases}$

$R_{ij}^{k} = R_{ik}^{k - 1} (R_{kk}^{k - 1})^{*} R_{kj}^{k - 1} \cup R_{ij}^{k - 1}$

顯然， $\displaystyle\bigcup\limits_{q_{f} \in F}{R_{1f}^{n}}$

圖上作業方法

對 $\ M = (Q , \Sigma , \delta , q_{0} , F)$ 的狀態轉移圖，操作步驟如下

預處理

在狀態轉移圖中增加狀態 $X$ 和 $Y$ ，從狀態 $X$ 到 $M$ 的開始狀態 $q_{0}$ 引一條標記為 $\varepsilon$ 的弧，對 $\forall q \in F$ ，從狀態 $q$ 到狀態 $Y$ 分別引一條標記為 $\varepsilon$ 的弧
去掉所有的不可達狀態

循環操作

重復如下操作，直到該圖中不再包含除了 $X$ 和 $Y$ 的其他狀態，并且這兩個狀態之間最多只有一條弧
- 并弧：對圖中任意兩個狀態 $q$ ， $p$ ，如果圖中包含有從 $q$ 到 $p$ 的標記為 $r_{1}$ ， $r_{2}$ ， $\cdots$ ， $r_{g}$ 的并行弧，則用從 $q$ 到 $p$ 的、標記為 $r_{1} + r_{2} + \cdots + r_{g}$ 的弧取代這 $g$ 個并行弧，其中， $q$ 和 $p$ 可以是同一個狀態
- 去狀態 $1$ ：對圖中任意 $3$ 個狀態 $q$ ， $p$ ， $t$ ，如果從 $q$ 到 $p$ 有一條標記為 $r_{1}$ 的弧，從 $p$ 到 $t$ 有一條標記為 $r_{2}$ 的弧，并且不存在從狀態 $p$ 到狀態 $p$ 的弧，則將狀態 $p$ 和與之關聯的這兩條弧去掉，增加一條從 $q$ 到 $t$ 的標記為 $r_{1} r_{2}$ 的弧
- 去狀態 $2$ ：對圖中任意 $3$ 個狀態 $q$ ， $p$ ， $t$ ，如果從 $q$ 到 $p$ 有一條標記為 $r_{1}$ 的弧，從 $p$ 到 $t$ 有一條標記為 $r_{2}$ 的弧，并且存在一條從狀態 $p$ 到狀態 $p$ 標記為 $r_{3}$ 的弧，則將狀態 $p$ 和與之關聯的這 $3$ 條弧去掉，增加一條從 $q$ 到 $t$ 的標記為 $r_{1} r_{3}^{*} r_{2}$ 的弧
- 去狀態 $3$ ：如果圖中只有 $3$ 個狀態，而且不存在從狀態 $X$ 到 $Y$ 的路，則將除狀態 $X$ 和 $Y$ 之外的第三個狀態及其相關的弧全部刪除
從狀態 $X$ 到 $Y$ 的弧的標記為所求的正則表達式，如果該弧不存在，則所求的正則表達式為 $\emptyset$