離散數學/有限狀態自動機

形式上，一個確定性有限自動機（DFA）是一個 5 元組 $D=(Q,\Sigma ,\delta ,s,F)$ 其中

• Q 是所有狀態的集合。
  
• $\Sigma$ 是正在考慮的字母表。
  
• $\delta$ 是狀態轉換的集合，每個狀態包含字母表中每個元素的唯一一個轉換。
  
• $s$ 是唯一的起始狀態。
  
• F 是所有接受狀態的集合。
  

對於 DFA，$\delta$ 可以被視為一個從 $Q\times \Sigma \to Q$ 的函式。

示例：考慮 DFA ${A}=(\{p,q\},\{a,b\},\delta ,p,\{q\})$，其狀態轉換由下表給出

$\delta$	a	b
p	q	p
q	p	q

很容易驗證這個 DFA 接受輸入 "aaa"。

類似地，非確定性有限自動機的形式定義是一個 5 元組 $N=(Q,\Sigma ,\delta ,s,F)$ 其中

• Q 是所有狀態的集合。
  
• $\Sigma$ 是正在考慮的字母表。
  
• $\delta$ 是狀態轉換的集合，包含 $\epsilon$ 轉換，並且對於每個狀態，任何特定輸入可以有多個轉換。
  
• $s$ 是唯一的起始狀態。
  
• F 是所有接受狀態的集合。
  

對於 NFA，$\delta$ 可以被視為一個從 $Q\times (\Sigma \cup \{\epsilon \})\to P(Q)$ 的函式，其中 $P(Q)$ 是 $Q$ 的冪集。

注意，對於 NFA 和 DFA 而言，$s$ 不是狀態集合。相反，它是一個單獨的狀態，因為兩者都只能從一個狀態開始。但是，NFA 可以透過新增一個新的起始狀態並進行 ε 轉換到所有需要的起始狀態來實現類似的功能。

DFA 和 NFA 之間的區別在於，DFA 的 delta 轉換不允許包含 ε 跳躍（在無輸入的情況下進行轉換）、同一輸入的轉換的並集以及字母表中任何元素的無轉換。

對於任何非確定有限自動機 $N$，存在一個確定有限自動機 $D$，使得 $L(N)=L(D)$