--- title: 自動機 ch.2 --- # 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.02 Finite Automata ### 2.1 Deterministic Finite Accepters (DFA) <!-- slide 4 --> #### Definition of DFA - DFA is defined by the quintuple $M =(Q, \Sigma, \delta, q_0, F)$ - $Q$: a finite set of **internal states** - $\Sigma$: a finite set of symbols called the **input alphabet** - $\delta$: $Q\times\Sigma\to Q$: a total function called the **transition function** - $q_0 \in Q$: the **initial state** - $F \subseteq Q$: a set of **final state** #### DFA 的運作 1. 最開始處於初始狀態 $q_0$ ，讀取指標位於輸入字串最左邊的符號 2. 每次移動時，讀取指標都會向右移動一個位置，每次移動消耗一個符號 3. 轉換由轉換函數 $\delta$ 控制 4. 當到了字串尾時，如果自動機處於最終狀態之一，則接受該字串，反之拒絕 #### Transition Graph 轉變圖 ![](https://i.imgur.com/gU19VkB.png) #### 轉變圖（$G_M$）vs dfa（$M$） + A dfa $M=(Q, \Sigma, \delta, q_0, F)$ + $G_M$ 有剛好 |Q| 個頂點，每個頂點都有不同的 $q_i\in Q$ + 每個轉移規則 $\delta(q_i, a)=q_j$ 在圖上標記為 a 的邊$(qi, qj)$ + 初始頂點：與 $q_0$ 有關聯的頂點 + 最終頂點：$q_f\in F$ #### Definition of $L(M)$ <!-- slide 11 --> - The language accepted by a dfs $M = (Q, \Sigma, \lambda, q_0, F)$ is the set of all strings on $\Sigma$ accepted by $M$. - $L(M) = \{w\in \Sigma^*:\lambda^*(q_0, w)\in F\}$ - All $\lambda$'s must be total functions - Unaccepted: - $\overline{L(M)} = \{w\in \Sigma^*:\lambda^*(q_0, w)\not\in F\}$ #### 擴展轉移函數 + $\delta^*:Q\times\Sigma^*\rightarrow Q$ 其中 $\Sigma^*$ 為一個字串 + 定義 + $\delta^*(q, \lambda)=q$ + $\delta^*(q, wa)=\delta(\delta^*(q, w), a)\forall q\in Q, w\in \Sigma^*, a\in \Sigma$ + 舉例： $\delta(q_0, a)=q_1, \delta(q_1, b )=q_2$ 則 $\delta^*(q_0, ab )=q_2$ #### Regular Language 正規語言 - A language L is called regular iff there exists some deterministic finite accepter M such that L = L(M) - 找到 DFA 即可確認任何語言是否為正規語言 ### 2.2 Nondeterministic Finite Accepters 非確定有限狀態自動機 <!-- Slide 21 --> + 非確定性代表自動機可以選擇移動 + 我們允許在每種狀況下可以採取的一系列行動 #### NFA 的定義 + NFA 被五元組 $M=(Q, \Sigma, \delta, q_0, F)$ 所定義 + $Q, \Sigma, q_0, F$ 的定義都與 DFA 相同 + $\delta:Q\times(\Sigma\cup\{\lambda\})\rightarrow2^Q$ ![](https://i.imgur.com/YGsgFmE.png) #### 三個不同 + nfa 中，$\delta$ 的範圍在冪集合中 + e.g. $\delta(q_1, a)=\{q_0, q_2\}$ + nfa 中，允許 $\lambda$ 作為 $\delta$ 的第二個參數，意謂著 nfa 可以在不消耗輸入符號的狀況進行轉移 + nfa 中，集合 $\delta(q_i, a)$ 可能為空，意謂著 nfa 沒有為這個特殊情形定義轉移 #### 被 nfa 所接受的東西 + 存在一些轉移的順序，可以使機器在字串結束時處於最終狀態的輸入，則會被 nfa 接受 + 不確定性可以被視為涉及直覺的洞察力，使其在每個狀態都可以選擇最佳轉移 #### 擴展轉移函數 對於 nfa ，擴展轉移函數在 $\delta^*(q_i, w)$ 包含 $q_j$ 被定義 i.f.f. 在 $G_M$ 中存在一條從 $q_i$ 到 $q_j$ 的路徑，標籤為 w ，適用於 $\forall q_i, q_j\in Q, w\in \Sigma^*$ #### L(M) 的定義 + 被 nfa $M=(Q, \Sigma, \delta, q_0, F)$ 所接受的語言為在 $\Sigma$ 上被 $M$ 所接受字串的集合 + $L(M)=\{w\in\Sigma^*:\delta^*(q_0, w)\cap F\neq\emptyset\}$ + 換句話說，該語言包含所有在轉移圖中可以從初始節點走到最終節點被標註為 w 的路徑的字串 w ### 2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters #### 有限接收器的等價定義 兩有限接收器 $M_1, M_2$ 在 $L(M_1)=L(M_2)$ （換句話說，如果他們都接收相同的語言）時，稱兩有限接收器等價 #### dfa 跟 nfa + 兩者的級別都一樣強大 + 對於每個被某些 nfa 接受的語言都可以找到一個同樣可以接受該語言的 dfa #### Theorem 2.2 設一語言 L 可以被 nfa $M_N=(Q_N, \Sigma, \delta_N, q_0, F_N)$ 所接受，則必存在一個 dfa $M_D=(Q_D, \Sigma, \delta_D, \{q_0\}, F_D)$ 使得 $L(M_N)=L(M_D)$ #### 把 nfa 轉成 dfa #### 正規語言 + 所有可以被 nfa 所接受的語言都是正規的 + 可以從 Theorem2.2 中得出 ### 統整筆記 #### DFA vs NFA <!-- 可以開新charater了 我晚上再把它整理完 --> <!-- ch3已開 -->