---
# System prepended metadata

title: Finite Automaton
tags: [自動機與形式語言]

---

# 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$當中，也會發生跟貓咪一樣的情況。
:::