形式化定义

到目前为止我们讨论的自动机都是确定性的，即从每个状态出发，对于输入符号的选择没有歧义。确定性有限自动机（DFA）也易于编程实现：我们只需为每个状态设置一个分支，在每个分支中根据当前输入符号选择对应的目标状态。在下一节中，我们将看到非确定性有限自动机（NFA）也有其用途。

一个确定性有限自动机（DFA）由以下部分组成：

• $Q$：一组状态，其中一个是初始状态（或起始状态），还有一个子集是终态（或接受状态）。
• $\Sigma$：有效输入符号的字母表。
• $\delta: Q \times \Sigma \rightarrow Q$：一个转移函数，给定当前状态和输入符号，决定自动机的下一个状态。

上述定义只是对我们已理解的 DFA 概念的形式化重述。转移函数 $\delta$ 表示自动机中的状态转移（边）。$Q$ 中构成终态的子集可以为空，这种情况出现在那些输出字符串而非“是/否”结果的机器中。对于 DFA 字母表中的每一个符号，每个状态必须有且仅有一条对应的输出转移边。

记住：对于 DFA 字母表中的每个符号，每个状态只能有一条对应的输出转移边。

接受以 $b$ 结尾字符串的 DFA

为了说明 DFA 形式化定义的应用，考虑下图所示的 DFA，它接受语言 $L$，该语言包含所有由字母表 $\Sigma = \{a, b\}$ 构成且以符号 $b$ 结尾的字符串。我们可以将此语言写作 $L = \{\text{所有以 } b \text{ 结尾的字符串}\}$。

每次读取到 $b$ 时，都有可能是输入字符串的最后一个字符，因此我们转移到接受状态 $q_1$；否则，我们转移到状态 $q_0$。因此，这个 DFA 的形式化定义如下：

• $Q = \{q_0, q_1\}$，其中 $q_0$ 是初始状态，$\{q_1\}$ 是终态集合
• $\Sigma = \{a, b\}$
• $\delta = \{((q_0,a),q_0), ((q_0,b),q_1), ((q_1,a),q_0), ((q_1,b),q_1)\}$

另一种表示 DFA 的方式是使用状态转移表。

$\text{ 语言 } L \text{ 的状态转移表}$

在状态转移表中，初始状态排在第一行，加号（+）标记每个终态。

由于表格是编程语言中常见的数据结构，因此它为在代码中实现 DFA 提供了另一种方法。

语言 $L$ 的模拟实现

下面的程序使用 Python 的字典类型来模拟上表中的状态转移。字典 transitions 将每个 <状态, 符号> 输入对映射到下一个状态。相比直接使用多个 if 和 else 语句判断状态，这种方法更加简洁。

1def ends_with_b(s):
2    transitions = {('q0','a'):'q0', ('q0','b'):'q1',
3                   ('q1','a'):'q0', ('q1','b'):'q1'}
4    state = 'q0'
5    for c in s:
6        state = transitions[(state,c)]
7    return 'accepted' if state == 'q1' else 'rejected'
8
9print(ends_with_b('aabab')) # 接受
10print(ends_with_b('aaba'))  # 拒绝

代码解释

以下是上述代码的逐行解析：

• 第 2–3 行：声明一个名为 transitions 的字典，用于存储语言 $L$ 对应的 DFA 所有转移函数。
• 第 4 行：将机器的初始状态设为 $q_0$。
• 第 5–6 行：使用 for 循环遍历输入字符串 s 中的每个字符 c。将当前 state 和字符 c 组合成元组作为字典 transitions 的键，获取对应的下一个状态并更新 state。
• 第 7 行：如果最终状态为 $q_1$，返回 'accepted'；否则返回 'rejected'。
• 第 9–10 行：打印函数对两个不同输入字符串的执行结果。

接受以 $ab$ 结尾字符串的 DFA

现在考虑如何构造一个 DFA 来接受语言 $M$，该语言包含所有由字母表 $\Sigma = \{a, b\}$ 构成且以子串 $ab$ 结尾的字符串。可将此语言写作： $M = \{ \text{所有以 } ab \text{ 结尾的字符串} \}$。

在这种情况下，通常可以从绘制一个仅接受目标子串的“局部自动机”开始。

如果我们在状态 $q_0$ 读取到 $b$，应保持在 $q_0$，因为我们需要一个 $a$ 出现在最终的 $b$ 之前。只有当我们在 $q_0$ 读取到 $a$ 时，才可能遇到了合法字符串倒数第二个字符。状态 $q_1$ 表示刚刚读取了一个 $a$，因此连续读取多个 $a$ 时我们仍停留在 $q_1$。如下图所示，$q_0$ 和 $q_1$ 上的自环体现了这一点。如果在状态 $q_2$ 读取到 $a$，它可能是最终 $b$ 前的那个 $a$，所以我们回到状态 $q_1$；如果在 $q_2$ 读取到 $b$，则需重新开始，转移到 $q_0$。

现在可以明确：状态 $q_0$ 表示尚未读取任何内容，或最近读取的是一个前面没有 $a$ 的 $b$。

接受包含 $aba$ 子串的 DFA

设计一个 DFA 来接受语言 $N$，该语言包含所有含有子串 $aba$ 的字符串，即 $N = \{ \text{所有包含 } aba \text{ 作为子串的字符串} \}$。首先构造一个仅接受字符串 $aba$ 的局部自动机，然后通过补全缺失的转移边来完成整个 DFA。

接受不包含 $aba$ 子串的 DFA

回顾前面的语言 $N = \{ \text{所有包含 } aba \text{ 作为子串的字符串} \}$。现在考虑如何构造一个 DFA 来接受语言 $N$ 的补集（即所有不包含子串 $aba$ 的字符串）。一旦进入状态 $q_3$，就说明已经出现了 $aba$，因此只要字符串从未到达该状态，它就属于原语言的补集。一般来说，补集语言中的字符串永远不会以原 DFA 的终态结束，或者说只会在非终态结束。因此，要构造一个识别语言补集的 DFA，只需将原 DFA 中每个状态的接受属性取反即可。下图中的自动机接受语言 $N$ 的补集。

一旦字符串进入状态 $q_3$，就无法再回到接受状态。这样的状态称为死状态或陷阱状态（jail state）。陷阱状态常见于某些语言的补集情形中——换句话说，当可接受字符串是由它们不具备的性质所定义时。

记住：要识别一个语言的补集，只需将接受该语言的 DFA 中每个状态的接受属性取反。

DFA 练习题

考虑语言 $K$，它包含所有以 $a$ 开头且以 $b$ 结尾的字符串。可将此语言写作 $K = \{ \text{所有以 } a \text{ 开头且以 } b \text{ 结尾的字符串} \}$。

下图是语言 $K$ 的一个不完整的有限自动机，部分转移边缺少标签。请为每条缺失的边填入正确的转移符号。