自動機理論（DFA）

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

什麼是 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

有限狀態機 - 維基百科，自由的百科全書

確定有限狀態自動機 - 維基百科，自由的百科全書

運算隨想 :: 瞎猜的狀態機

dfa确定有限自动机定义_确定性有限自动机（DFA）-CSDN博客