# 自動機理論（DFA）

[TOC]

歡迎你點進本篇文章～本篇主要針對計概上課內容做筆記，若你對文章感興趣的話，不妨按下愛心或追蹤我！感謝你的觀看～

## 什麼是 DFA

> 確定有限狀態自動機（Deterministic Finite Automata, DFA）是一種能夠實現狀態轉移的自動機（automaton），屬於計算理論中的基礎模型。
> Wikipedia

其中狀態（State）指的是機器在執行過程中的一個特定情況或條件，例如一個電燈開關他的狀態，有可能是開著的狀態，或是關著的狀態。

而所謂的轉移（transfer）就是狀態可能從原本是 ON 的狀態變成 OFF 狀態的過程，或是相反過來，OFF 變成 ON 這個狀態的過程。

### 狀態（State）

狀態可以分成三種：

- 起始狀態（Start State）：機器開始時的初始狀態，通常用符號 $q_0$ 或 $s$ 去表示。
- 接受狀態（Accept State）：也稱最終狀態，就是在當機器讀完所有輸入後停在該狀態時，就表示接受該輸入字串。
- 一般狀態（States）：其他的中間狀態，負責處理輸入過程的各種情況。

起始狀態的圖長以下這樣，會先有一個箭頭指向起始狀態，而這個箭頭之前是沒有任何東西的：


接受狀態的圖長以下這樣，以兩個圓圈表示 Accept State：


而一般狀態基本上就是一個圓圈：


### 運作方式

在 DFA 中，會從起始狀態開始，然後一個字元接著一個字元去讀入完整的字串，然後根據轉移函式逐步轉移到下一個狀態。讀完整個字串後，如果機器停在接受狀態，就接受（Accept）該字串；否則拒絕（Reject）該字串。

### DFA 的定義（Definition）

DFA 是一個 5 元組（tuple）： $M = (Q, \Sigma, \delta, q_0, F)$

- $Q$ 是有限狀態集合。
- $\Sigma$ 是一個字母表，為所有可能輸入符號的有限集合，DFA 會處理 $\Sigma$ 上面的字串。
- $\delta : Q \times \Sigma \rightarrow Q$ ， $\delta$ 是一個轉移函式（transition function），定義在某個狀態下讀取某個輸入符號後會轉移到哪個狀態。
- $q_0 \in Q$ 為起始狀態，機器開始運作的初始狀態。
- $F \subseteq Q$ 為接受狀態（Accept State）集合，最終狀態的集合，若機器停在這些狀態則接受該輸入字串。

### 轉移函式（Transition Function）

轉移函式可接受兩個輸入：

1. 當前狀態。
2. 一個輸入字元。

轉移函式是機器決定在某個狀態下讀取某個字元後，應該轉移到哪個狀態的結果。

運作原理：當自動機處於狀態 $q$ 並讀入字元 $a$ 時，轉移函式 $\delta(q, a)$ 會跟機器說等下要進入哪種狀態。在 DFA 裡面，這結果會是唯一的，因為 Deterministic 就是決定性的。

轉移函式有很多種表示方式，可以是：

- 狀態轉移表
- 狀態轉移圖
- 轉移矩陣

狀態轉移表就是像真值表那樣的表示法，如：

| | a | b |
| -------- | -------- | -------- |
| q1 | q1 | q2 |
| q2 | q3 | q2 |
| q3 | q2 | q2 |

狀態轉移圖就是用箭頭連接每一個狀態，然後在箭頭上面寫上輸入的字元，如表中的 a 跟 b。

若給定 $M = (\{q_1, q_2, q_3\}, \{a, b\}, \delta, q1, \{q_2\})$

而 $\delta$ 就是上面那張表的話，畫圖起來就會像是下面這樣子：


當輸入字串 `abb`，該字串會被接受，因為 b 最後停留在 $q_2$ 這個 accept state。流程是這樣跑的：

1. 先輸入 a 字元，由起始狀態 $q_1$ 出發，因為遇到 a，所以會原地打轉，一樣停在狀態 $q_1$
2. 再輸入 b 字元，由上一個狀態 $q_1$ 轉移到 $q_2$ 。
3. 再次輸入 b 字元，由上個狀態 $q_2$ 轉移到 $q_2$ ，由於最後停留的是在 accept state，因此這個字串會被接受。

但輸入字串 `aba` 會被拒絕，因為最後的狀態 $q_3$ 不是 accept state。

## Language of Machine

機器的語言 $L(M)$ 是指機器 $M$ 所接受的所有字串集合。若說「機器 $M$ 識別語言 $A$ 」時，意思就是機器 $M$ 能夠接受語言 $A$ 中的所有字串，並拒絕不在 $A$ 裡面的所有字串。

用數學表示就是如果 $A$ 是所有被機器 $M$ 接受的字串集合，則 $A = L(M)$ 。

當機器 $M$ 的輸入字母集是 $\Sigma$ 的時候，機器的語言 $L(M)$ 必為 $\Sigma^*$ 的子集合。

而這的 $\Sigma^*$ 代表的是所有可以由字母集 $\Sigma$ 組成的字串集合（含空字串）。

### 正規語言（Regular Language）

如果存在某個確定有限狀態自動機（DFA）能夠識別語言 $L$ ，那麼我們稱 $L$ 為正規語言。正規語言具有封閉性，在聯集、交集、補集、串接和 Kleene 星號運算下都保持正規性。

## 相關範例

### 辨別二進位字串是否有奇數個 1

Consider the following DFA $M_1$ with alphabet $\Sigma = \{0, 1\}$ :


then

- `010110` is accepted, but `0101` is rejected.
- $L(M_1)$ is the language of strings over $\Sigma$ in which the total number of 1's is odd.

### 辨別二進位字串是否有偶數個 1

Given DFA $M = (Q, \Sigma, \delta, q_0, F)$, then :

- $Q = \{q_0, q_1\}$
- alphabet $\Sigma = \{0, 1\}$
- $F = \{q_0\}$
- $\delta$ : $Q \times Sigma \rightarrow Q$ is described as

| | 0 | 1 |
| -------- | -------- | -------- |
| $q_0$ | $q_0$ | $q_1$ |
| $q_1$ | $q_1$ | $q_0$ |


上面這兩題的運作方式很好懂，只要將不影響到結果本身的因素的狀態保持不變即可，也就是讀到 0 的時候，狀態不變，一旦讀到 1 就將狀態改變。

## 總結

確定有限狀態自動機（DFA）是一種基礎計算模型，用來描述系統如何依序讀取輸入，並在狀態間進行決定性的轉移。想像成「電燈開關」的行為模式：電燈的狀態是 **開** 或 **關**，而按下開關就是狀態轉移。

### 1. 狀態（State）

DFA 具備三類狀態：

* 起始狀態（Start State）：機器開始的位置。
* 接受狀態（Accept State）：若在讀完字串後停在此狀態，就接受該字串。
* 一般狀態（States）：處理過程中的中間狀態。

圖示：起始狀態有外來的箭頭、接受狀態是兩個圓圈、一般狀態是一個圓圈。

### 2. 運作方式

DFA 從起始狀態出發，依序讀入字串的每個字元。

每讀到一個字元，就依轉移函式移動到下一個狀態。

讀完後：

* 停在接受狀態 → 接受
* 停在其他狀態 → 拒絕

### 3. DFA 的正式定義

DFA 是一個五元組： $M = (Q, \Sigma, \delta, q_0, F)$

* $Q$：有限的狀態集合
* $Σ$：字母表（所有可能的輸入符號）
* $δ$：轉移函式（$Q \times Σ \to Q$）
* $q_0$：起始狀態
* $F$：接受狀態集合

### 4. 轉移函式（Transition Function）

轉移函式輸入：

1. 當前狀態
2. 下一個輸入字元

回傳：

* 下一個應該轉移到的狀態（且唯一，因為是 deterministic）

常見表示方式：

* 轉移表
* 狀態圖
* 轉移矩陣

### 語言（Language of Machine）

DFA 所接受的所有字串形成語言： $L(M) = {\text{所有使 } M \text{停在接受狀態的字串}}$

若輸入字母表是 $Σ$ ，則 DFA 語言必定是 $Σ*$ 的子集合。

### 正規語言（Regular Language）

若語言可以被某個 DFA 識別，則稱該語言為正規語言。
正規語言在：

* 聯集
* 交集
* 補集
* 串接
* Kleene star（反覆運算）

下皆保持封閉性。

## 參考資料

[Formal Language - Ch1 決定性有限自動機 Deterministic Finite automata, DFA | Mr. Opengate](https://www.mropengate.com/2015/03/formal-language-ch11-finite-automata.html)

[有限狀態機 - 維基百科，自由的百科全書](https://zh.wikipedia.org/zh-tw/%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA)

[確定有限狀態自動機 - 維基百科，自由的百科全書](https://zh.wikipedia.org/zh-tw/%E7%A1%AE%E5%AE%9A%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E8%87%AA%E5%8A%A8%E6%9C%BA)

[運算隨想 :: 瞎猜的狀態機](https://openhome.cc/zh-tw/computation/automata/nfa/)

[dfa确定有限自动机定义_确定性有限自动机（DFA）-CSDN博客](https://blog.csdn.net/cumubi7453/article/details/107794893)