##### 确定型有限自动机 - 确定型有限自动机 - **确定型有限自动机** $\text{DFA}$ 是一种[[有限自动机]], 它通过运行由字符串唯一确定的状态序列来接受或拒绝给定的符号串, 确定性是指计算运行的唯一性. 确定性有限自动机可定义为一个五元组 $A=(Q, \Sigma, \delta, q_0, F)$ 满足以下条件 - $Q$ 有限状态集合 - $\Sigma$ 有限输入字母表 - $\delta: Q \times \Sigma \to Q$ 状态转移函数 - $q_0 \in Q$ 初始状态 - $F \subseteq Q$ 接受状态集合 >[!example]- 确定型有限自动机 > ![[opentext_计算理论_1.png]] > - 状态图 > - 三个状态, 标记为 $q_1, q_2, q_3$ > - $q_1$ , 起始状态, 由外部箭头指向 > - $q_2$ , 接受状态, 用双圈表示 > - $q_3$ , 非接受状态 > - 输入字母表, $\{0, 1\}$ > - 转移箭头, 从一个状态到另一个状态的箭头, 标记为 $0$ 或 $1$, 表示根据输入符号的转移规则 > - 计算过程 > - 接收输入字符串, 逐个读取符号, 从左到右处理, 并根据转移规则改变状态. 最终状态决定输出, 接受如果最后状态是接受状态, 拒绝如果最后状态不是接受状态. 输入字符串 $1101$ 为例 > - 从 $q_1$ 开始 > - 读取 $1$, 从 $q_1$ 转移到 $q_2$ > - 读取 $1$, 从 $q_2$ 转移到 $q_2$ > - 读取 $0$, 从 $q_2$ 转移到 $q_3$ > - 读取 $1$, 从 $q_3$ 转移到 $q_2$ > - 结束时在 $q_2$ , 接受状态, 因此接受 > - 接受语言 > - $L = \{ w \mid w \text{至少包含一个1, 且最后一个1后面有偶数个0}\}$