自動機 ch.4

--- title: 自動機 ch.4 --- # Automata Theory and Formal Languages NTNU 自動機理論與正規語言 ##### [Back to Note Overview](https://hackmd.io/@NTNUCSIE112/NTNUNote) ##### [Back to Automata Theory and Formal Languages](https://hackmd.io/@NTNUCSIE112/AT110-1) {%hackmd @sophie8909/pink_theme %} ###### tags: `AutomataTheoryandFormalLanguages` `110-1` `選修` `CSIE` `NTNU`  ## Ch.04 Properties of Regular Languages ### 4.1 Closure Properties of Regular  #### Theorem 4.1 如果 $L_1, L_2$ 為正規語言，則 $L_1\cup L_2, L_1\cap L_2, L_1L_2, \overline {L_1}, {L_1}^*$ 也都是正規語言換句話說，正規語言的家族在聯集、交集、串聯、補集跟在星形閉合下是封閉的 #### Definition 4.1 - 假設 $\Sigma, \Gamma$ 為字母表，則函數 $h:\Sigma\rightarrow\Gamma^*$ 稱為同態（homomorphism） - 換句話說，同態是用字串替換掉單個字母的替換 - 函數 $h$ 的定義域以一種明顯的方式擴展到字串 - 如果 $w=a_1a_2...a_n$ 則 $h(w)=h(a_1)h(a_2)...h(a_n)$ - 如果 $L$ 為 $\Sigma$ 上的語言，則其同態像定義為 $h(L)=\{h(w):w\in L\}$ #### Theorem 4.2 - 正規語言的家族在轉置運算上是封閉的 - suppose that L is regular language - construct an nfa with a single final state for it - in #### Theorem 4.3 - 設 $h$ 是一個同態，如果 $L$ 是正規語言，那麼他的同態像 $h(L)$ 也是正規的 - 常規語言在任意同態下都是封閉的。 #### Definition 4.2 - 設 $L_1, L_2$ 為同個字母表上的語言 - $L_1, L_2$ 的右商定義為 - $L_1/L_2 = \{x:xy\in L_1 \text{ for some } y \in L_2\}$ - 先取 $L_1$ 中有屬於 $L_2$ 後綴的字串，每個這樣的字串在去掉該後綴後屬於 $L_1/L_2$ - e.g. $L_1=L(a^*baa*), L_2=L(ab^*)$，找出 $L_1/L_2$ :::spoiler 解法 1. 對每個 $q_i \in Q$，查看若 $\exists y\in L_2 \text{ s.t. } \delta^*(q_i, y)=q_f\in F$ - 這可以由 dfa $M_i=(Q, \Sigma, \delta, q_i, F)$<br>$M_i$ 為 $M$ 把初始狀態 $q_0$ 改成 $q_i$ - 接者可以判斷 $\exists y\in L(M_i)$ 且在 $L_2$ 2. 如果有 $q_i$ 到 $q_f$ 間存在一條path，將 $q_i$ 加入 $F$ - 對每個 $q_i \in Q$ 都做一次 3. 最後將結果的 dfa 在轉為 RE $a^*b+a^*baa^*\rightarrow a^*ba^*$ 4. $L_1/L_2=L(a^*ba^*)$ ::: #### Theorem 4.4 如果 $L_1, L_2$ 為正規語言，那麼 $L_1/L_2$ 也都會是正規語言，正規語言家族在右商的狀況下是封閉的  ### 4.2 Elementary Questions about Regular Languages #### 隸屬問題對於一個語言 $L$ 和字串 $w$，我們是否可以確定 $w$ 是 $L$ 的元素可以解決這種問題的演算法稱為 membership algorithm #### 標準表示常規語言以標準表示式輸出 i.f.f.它是由有限自動機、正規表達式或正規文法所描述 #### Theorem 4.5 給定任何正規語言 $L$ 在 $\Sigma$ 及任何 $w\in\Sigma^*$上的標準表示式，則存在一個可以確認 $w$ 是否在 $L$ 中的演算法。 #### Theorem 4.6 存在一種演算法，它可以判斷以標準形式給出的正規語言是空的、有限還是無限的 #### Theorem 4.7 對於兩正規語言 $L_1, L_2$ 的標準表示式，存在一個演算法判斷 $L_1=L_2$ 是否成立 ### 4.3 Identifying Non-regular Languages - 正規語言與具有有限記憶體的自動機有關，這對於正規語言的結構施加了一些限制 - 只有在處理任何字串時，所有階段必須記住的訊息受到嚴格限制時，語言才是正規的 - 但要如何用任何有意義的方式精確地顯示 #### 鴿籠原理如果將 n 個物體放進 m 個箱子，如果 n > m，至少一個盒子中會有不只一件物體 ##### Example 4.6 證明 $L=\{a^nb^n:n\geq0\}$ 為不正規的 :::spoiler 以下證明 by 反證法假設 $L$ 為正規的 $\rightarrow$ 存在一 dfa $M=(Q, \{a, b\}, \delta, q_0, F)$ 可以符合 $L$ 觀察 $\delta^*(q_0, a^i)$ for i=1, 2...，因為 M 中的狀態數是有限的，i 卻是無限的，by 鴿籠原理，一定會有兩狀況 $\delta^*(q_0, a^n) = q \text{ 以及 } \delta^*(q_0, a^n) = q, n\neq m$ 但因為 M 接受 $a^nb^n$ 所以我們有 $\delta^*(q, n^n) = q_f\in F$ 因此可以得出 $\delta^*(q_0, a^mb^n)=\delta^*(\delta^*(q_0, a_m), b^n)=\delta^*(q, b^n)=q_f$ 這與當初的假設只有 $n=m$ 時成立矛盾，反證得證 ::: #### 泵原理另一個形式的鴿籠原理再有 $n$ 個頂點的轉移圖中，任何長度 $\geq n$ 的 walk 必重複某個頂點，即包含一個 cycle #### Theorem 4.8 設 $L$ 是一個無限正規語言，那麼存在某正整數 $m$ 使得任意 $w\in L \text{ with } |w|\geq m$ 可以被分解為 $w=xyz\text{, with } |xy|\leq m \text{ and } |y|\geq1 \text{ s.t. } w_i=xy^iz$ 也在 L 中 for i=0, 1, 2... （長度超過狀態數的字串都可以表示為ｗ＝ｘｙｚ，而ｘｙiｚ都會被Ｍ接受） ![](https://i.imgur.com/BHtTAWl.png) #### 一些陷阱 - 試圖用 pumping lemma 證明一個語言是正規的 - 即使你可以證明 $L$ 中的任何字串都不能被抽出，也不能斷定 $L$ 是正規的 - 他只能拿來證明一種語言不是正規的 - 以不在 $L$ 中的字串開始 - e.g. 證明 $L=\{a^n:\text{ n is prime number}\}$ 不是正規的 - （False）從「給定 $m$ 設 $w=a^m...$」開始是不正確的，因為 $m$ 開頭不一定為質數 - （Correct）「給定 $m$ 設 $w=a^M \text{ where M is a prime number larger than m}$」 - 對於 xyz 的分解做一些假設 - 我們從定理中只知道 $y$ 不為空且 $|xy|\leq m$，其他多餘的假設會使這個定理無效 - e.g. $y=a^k$ with $k$ is odd 則 w=xz 為一個偶數長度的字串，因此不在 $L$ 中 *[quotient]: 商