DFA

---

DFA（Deterministic Finite Automaton，确定有限状态自动机）是一个五元组，包括：

1. 状态集合（Q）：有限个状态的集合。

2. 输入字母表（Σ）：有限个输入符号的集合。

3. 状态转移函数（δ）：从一个状态经过一个输入符号到达另一个状态的函数。

4. 初始状态（q0）：一个初始状态，它是Q中的一个元素。

5. 终止状态集合（F）：一个终止状态集合，它是Q中的一个子集。

其中，状态转移函数δ的定义为：δ: Q × Σ → Q，即从一个状态和一个输入符号映射到另一个状态。

有穷自动机（DFA）是一种计算模型

---

有穷自动机（DFA）是一种计算模型，它接受一个输入字符串并根据预定义的规则进行状态转移，最终输出一个确定的结果。

举个例子，假设我们要构建一个DFA来识别二进制数字串是否能被3整除。该DFA的状态集合为{0,1,2}，输入字母表为{0,1}，起始状态为0，状态转移函数如下：

- 当前状态为0，输入0后转移到状态0，输入1后转移到状态1；
- 当前状态为1，输入0后转移到状态2，输入1后转移到状态0；
- 当前状态为2，输入0后转移到状态1，输入1后转移到状态2。

当输入一个二进制数字串时，从起始状态开始，根据输入的每个字符进行状态转移，最终到达某个状态。如果最终状态为0，则说明该数字串能被3整除；否则不能被3整除。

例如，输入二进制数字串10110，从状态0开始，依次转移到状态1、状态2、状态1、状态2、最终到达状态1，因此该数字串不能被3整除。