--- title: 自動機 ch.3 --- # 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.03 Regular languages and regular grammars ### 3.1 Regular Expressions <!-- slide 2 --> #### Formal definition of a regular expression (RE) - Let $\Sigma$ be a given alphabet. Then 1. $\emptyset$, $\lambda$ and $a \in \Sigma$ are all RE. These're called primitive（原始） RE 2. 如果 $r_1, r_2$ 為正規表達式，則 $r_1+r_2, r_1\cdot r_2, r_1^*, (r_1)$ 也都是正規表達式 3. 一個字串是一個正規表達式 i.f.f. 它可以由原始的正規表達式以有限個在規則 2 中的應用所推導出來 NOTE：很多課本使用對選擇使用符號$\cup、+或\vee$替代 $|$ #### Languages associated with REs - REs 可以用來描述一些簡單的語言 - 如果 $r$ 是一個 RE, 我們會用 $L(r)$ 代表與 $r$ 相關的語言 #### Definition of $L(r)$ - $L(r)$ denoted by any RE $r$ is defined by the following rules 1. $\emptyset$: the empty set 2. $\lambda$: {$\lambda$} 3. $\forall a \in \Sigma$, $a$: {a} ^^^^^^^^^^^^ 終止條件 ^^^^^^^^^^^^ 如果 $r_1, r_2$ 為正規表達式 4. $L(r_1+r_2)=L(r_1)\cup L(r_2)$ 5. $L(r_1\cdot r_2)=L(r_1)L(r_2)$ 6. $L((r_1))=L(r_1)$ 7. $L(r_1^*)=(L(r_1))^*$ ^^^^遞迴地將 $L(r)$ 簡化為更簡單的元件^^^^ #### 優先規則 + Ambiguity for the RE 正規表達式的模糊性 + e.g. $a\cdot b+c$ + $r_1=a\cdot b, r_2=c\Rightarrow L(a\cdot b+c)=\{ab, c\}$ + $r_1=a, r_2=b+c\Rightarrow L(a\cdot b+c)=\{ab, ac\}$ + 克服問題 + 全部都用括弧括起來（麻煩） + 優先順序 + Star-closure（$r_1^*$）> concatenation 串聯（$r_1\cdot r_2$）> union 聯集（$r_1+r_2$） + 串聯 $r_1\cdot r_2$ 可以寫成 $r_1r_2$ <!-- 10/12 Slide 11 end--> ### 3.2 Connections Betweem Regular Expressions and Regular Expressions and REgular Languages <!-- slide 13 --> + 每個正規語言都有一個正規表達式 + 每個正規表達式都有一個正規語言 #### Theorem 3.1 <!-- 15 --> 設 $r$ 為一個正規表達式，則存在一些 nfa 可以接受 $L(r)$，因此 $L(r)$ 為一個正規語言 透過這些方法將許多步驟串在一起，我們可以找到任意複雜正規表達式的自動機 <!-- --> #### REs for regular languages - 對於所有正規語言，必然存在一個對應的 RE - 因為任何正規語言都有一個相對應的 nfa 及一個轉移狀態圖，我們所需要做的就是找到一個符合 RE 能夠生成從初始狀態 $q_0$ 走到所有最終狀態的路徑的 label - Generalized transition graph (GTG): 一個所有邊都可以使用 REs 標示的轉移狀態圖 - 不然就只是一般的 transition graph - ![](https://i.imgur.com/HrvL1QO.png) - complete：任兩個狀態間都有一個邊 ![](https://i.imgur.com/Uyc3qGJ.png) #### Theorm 3.2 - 設 $L$ 為一個正規語言，則存在一個正規表達式 $r$ 使得 $L=L(r)$ - proof：如果 $L$ 為正規的，則存在一個對應的 nfa #### REs for describing simple patterns - The set of all acceptable Pascal integers is defined by the RE `sdd*` - s： the sign, with possible values from {$+, -, \lambda$} - d： digits 0 to 9 - REs 可以被用來描述 simple patterns Regular expression>nfa>dfa>pattern matching algorithm ![](https://i.imgur.com/C3ElUZS.png) ### 3.3 Regular Grammars <!-- slide 36 --> #### Describing regular languages - Deterministic finite accepters - Nondeterministic finite accepters - Regular expressions - Regular grammars #### Right- and left-liner grammars 左/右線性文法 如果一個文法 $G=(V, T, S, P)$ 的所有產生式都是... - $A\rightarrow xB, A\rightarrow x$ where $A, B \in V, x\in T^*$ 則稱為右線性文法 - $A\rightarrow Bx, A\rightarrow x$ where $A, B \in V, x\in T^*$ 則稱為左線性文法 - 一個正規文法指的就是左或是右線性文法 - 一個正規文法一定是線性的，但是不是所有的線性文法都是正規的 NOTE - 在正規文法中，任何產生式的右側最多出現一個變數 - 此外，該變數必須始終在任何產生式右側的最左或最右側 <!-- slide 43 --> #### **Right-linear grammars** generate **regular languages** 1. show a language generated by a right-linear grammars is always regular - construct an nfa 2. the se 3. #### Theorem 3.3 <!-- slide 44 --> 設 $G=(V, T, S, P)$ 為一個右線性文法，則 $L(G)$ 為一個正規語言 - Proof - assume - $V = \{V_0, V_1, cdots\}$ - S = V_0 - productions - $V_0 \to v_1V_i, V_1 \to v_2V_j,\cdots \text{ or } V_n\to v_l$ - If w is a string in L(G) .......(補) - For $V_i \to a_1a_2\cdots a_mV_j$ - 自動機會有 transitions 連接 $V_i$ 和 $V_j - transition function: $\delta^*(V_i,a_1a_2\cdots a_m) = V_j$ - For ...(補) #### Theorem 3.4 <!-- slide 49 --> 如果 $L$ 是字母集 $\Sigma$ 上的正規語言，則存在一個右線性文法 $G=(V, \Sigma, S, P)$ 使得 $L=L(G)$ - Proof - Let $M = (Q, \Sigma,\delta, q_0, F)$ be a dfa that accepts L - Assume $Q = \{q_0, q_1, \cdots, q_n\}$ and $\Sigma = \{a_1, a_2, \cdots, a_m\}$ - Construct the right-linear grammar ...(補) - For each transition XX of M - put in P the ..... #### Theorem 3.5 一個語言 $L$ 為正規的 i.f.f. 存在一個左線性文法 $G$ 使得 $L=L(G)$ <!-- slide 53 --> - 為 L(aab^*^a) 建構一個右線性的文法 - sol: - transition function for an nfa #### Theorem 3.6 一語言 $L$ 為正規的 i.f.f. 存在一個正規文法 $G$ 使得 $L=L(G)$ - proof - 將 Theorm 3.4 跟 Theorem 3.5 結合