确定有穷自动机的定义#

确定有穷自动机（DFA）是一个五元组：

$A = (Q, \Sigma, \delta, q_0, F)$

其中：

• $Q$ 是一个有限的状态集合
• $\Sigma$ 是一个有限的输入符号集合（字母表）
• $\delta: Q \times \Sigma \to Q$ 是状态转移函数，定义了在给定状态和输入符号的情况下，自动机如何转移到下一个状态
• $q_0 \in Q$ 是初始状态
• $F \subseteq Q$ 是终结状态集或接受状态集合

条件#

1. 转移是确定且唯一的：对于每个状态 $q \in Q$ 和每个输入符号 $a \in \Sigma$，转移函数 $\delta(q, a)$ 定义了一个唯一的下一个状态
2. DFA在任何时候只能处于一个状态
3. DFA接受一个字符串，如果从初始状态出发，按照输入字符串的符号进行状态转移，最终停在一个接受状态上
4. DFA拒绝一个字符串，如果从初始状态出发，按照输入字符串的符号进行状态转移，最终停在一个非接受状态上
5. DFA不能有ε-转移，即不能在没有输入符号的情况下进行状态转移