Finite Automaton

# Deterministic Finite Automaton 以一個 5-tuple 來定義一個有限自動機 Finite Automaton： $$ (Q,\sum,\delta,q_{0},F) $$ 其中： - $Q$ 狀態 states 的有限集合 - $\sum$ 有限的字母 alphabet - $\delta:Q\times \sum \rightarrow Q$ 在當前狀態，得到輸入後決定下一狀態的轉移函數 - $q_{0}\in Q$ 起始狀態 start state - $F\subseteq Q$ 允許狀態 accept states :::info - 起始狀態可以是允許狀態 ::: ## 運作方式給一個字串，然後從 $q_{0}$ 開始，使用 $\delta$ 根據當前狀態還有讀到的字母來決定下一狀態。例如給個字串 $0123$，則： $$ q_{0}\rightarrow q_{1}\rightarrow q_{2}\rightarrow q_{3}\rightarrow q_{4}\\ q_{1}=\delta(q_{0},0)\\ q_{2}=\delta(q_{1},1)\\ q_{3}=\delta(q_{2},2)\\ q_{4}=\delta(q_{3},3)\\ $$ # Nondeterministic Finite Automaton / NFA 跟 DFA 類似，只不過 alphabet 是 ${\sum}_{\Large\epsilon}$，可以注意到字母中多了 $\epsilon$，代表空字串，轉移函數變成： $$ \delta:Q\times {\sum}_{\Large\epsilon} \rightarrow \mathcal{P}(Q) $$ 其中 $\mathcal{P}(Q)$ 是由所有的狀態構成的可能組合的集合，又叫做 Power Set。會這樣的原因是，在 NFA 中給予某個輸入後，不是只有一個向外箭頭，而是可能有很多個，因此函數的輸出是一個集合。 ## 運作方式大致也跟 DFA 一樣，不過因為有可能有多條路可以走，所以會以畫出樹狀圖的方式運作，並且： - 如果當前狀態 $q_{0}$ 得到字母 $a$，所有可以抵達的 ${q_{1},q_{2}...}$ 都畫出來後，如果 ${q_{1},q_{2}...}$ 當中有人有空字串 $\epsilon$ 的向外箭頭，則會將該箭頭指向的下一個狀態加入 ${q_{1},q_{2}...}$ 裡面。 - 如果當前狀態得到字母 $a$ 沒有向外箭頭，代表這個分支「枯萎/死亡」 - 如果得到字母 $a$ 後的所有狀態中有重複的，每種狀態保留一個就好 - 因為只需要代表在該時刻，可以抵達的狀態有哪些 # 允許狀態如果讀完一個字串後，停留的狀態屬於允許狀態，代表該自動機「允許 accept」該字串。 # Language of Automaton 對於一個有限自動機 $M$，我們將 $M$ 允許的全部字串蒐集起來；這些字串的集合就是有限自動機「辨識出的語言 Recognized Language」 # Regular Language 如果語言 $A$ 有某個 DFA 辨識他，那麼 $A$ 就是個 Regular Language。因此我們可以知道對於一個 DFA $M$，他所對應的 Language 就是 Regular Language。 # NFA 和等價的 DFA 每一個 NFA 其實都可以建構出一個等價的 DFA，方法就是先弄出 $Q'=\mathcal{P}(Q)$，也就是說由 $Q$ 的所有狀態構成的 Power State。 >Power State 是所有 State 可以組合出的所有可能，如果有 3 個 State 就是 2^3^ 種然後對每個在 $Q'$ 中的狀態，由於他其實是個子狀態的集合，所以當他得到一個輸入的時候，每個子狀態會得到下一個狀態，他也是個子狀態的集合，所以我們把所有子狀態得到的狀態聯集起來；記得，如果走到的某個狀態有 $\epsilon$ 的向外箭頭，就要繼續走下去。起始狀態，就跟原本 NFA 的一樣，但是要記得起始狀態也可能有 $\epsilon$ 的向外箭頭，所以也要讓起始狀態變成一個狀態的集合。允許狀態就是包含原本 NFA 允許狀態的狀態。這樣一來，對於一個 NFA 辨識的語言 $A$，在上面的 DFA 架構中，因為最終都會走到允許狀態，所以這個新建構出的 DFA 同樣辨識出 $A$。 ## Corollary 因為一個 NFA 可以推導出價的 DFA，於是我們便可推得： $$ \text{Language is regular} \leftrightarrow \text{a NFA recognize it} $$ --- # Regular Operations 對 Regular Language 的操作，例如聯集，貓咪，跟星星。但是做了操作之後，有一個重點是要重新證明封閉性。 ## 聯集對於兩個正常語言 $A_{1}$ 跟 $A_{2}$，如果其對應的 NFA 為 $N_{1}$ 跟 $N_{2}$： - 在 $N_{1}$ 跟 $N_{2}$ 前加入一個共同的 $q_{0}$，並且指向各自 $q_{0}$ 時的輸入是 $\epsilon$ - 這樣一來組成的新的 $N=N_{1}\cup N_{2} \cup {q_0}$，依舊是個 NFA - 所以也就還是有個正常語言對應他 ## 貓咪/連結 Concatenation 跟上面很類似，不過換成 $N_{1}$ 的 $F$ 都要接空字串輸出到 $N_{2}$ 的起始狀態 $q_{2}$，並且要注意： - $\delta(q,a)=\delta_{1}(q,a)$ 如果 $q\in Q,q \notin F_{1}$ - $\delta(q,a)=\delta_{1}(q,a)$ 如果 $q \in F_{1}$ 且 $a\ne \epsilon$ - $\delta(q,a)=\delta_{1}(q,a)\cup \{q_{2}\}$ 如果 $q \in F_{1}$ 且 $a= \epsilon$ - $\delta(q,a)=\delta_{2}(q,a)$ :::warning 在 $q \in F_{1}$ 且 $a=\epsilon$，可以看到是 $\delta_{1}(q,a)\cup {q_{2}}$，原因是因為 $F_{1}$ 的某些點可能本身就自帶 $\epsilon$ 向外箭頭，要記得考慮原本就有的 $\delta_{1}(q,a)$。 ::: ## 星星 Star 把自己的字母複製好幾遍出來，記為 $A_{1}^{*}$。建構方法直覺蠻簡單的，就是把 $F_{1}$ 的所有狀態都拉一條空字串箭頭到 $q_{1}$。但是星星操作還有一個重點，它可以是空字串，所以需要稍微修改一下： - 如果直接把 $q_{1}$ 令作允許狀態 - 有可能其他不被 $A_{1}^{*}$ 認可的字串，繞了一圈又回到起始狀態因此我們用了一個巧妙的方法，建立一個新的起始狀態 $q_{2}$，他同時也是允許狀態，並且讓他以空字串指向原本的起始狀態 $q_{1}，這樣就可以避免上面的問題。 - $\delta(q,a)=\delta_{1}(q,a)$ 如果 $q\in Q,q \notin F_{1}$ - $\delta(q,a)=\delta_{1}(q,a)$ 如果 $q \in F_{1}$ 且 $a\ne \epsilon$ - $\delta(q,a)=\delta_{1}(q,a)\cup \{q_{1}\}$ 如果 $q \in F_{1}$ 且 $a= \epsilon$ - $\delta(q,a)=q_{1}$ 如果 $q=q_{2}$ 且 $a = \epsilon$ - $\delta(q,a)=\emptyset$ 如果 $q =q_{2}$ 且 $a\ne \epsilon$ :::warning 在 $q \in F_{1}$ 且 $a = \epsilon$當中，也會發生跟貓咪一樣的情況。 :::