离散数学/有限状态自动机

形式上，一个确定性有限自动机（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)$