• Introduction to Deterministic Finite Automata (DFA) - YouTube
• Practice problems on finite automata - GeeksforGeeks

DFA 最基础也是最重要的能力：

1. 给定一个 DFA 和一个字符串，判断是否被接受。
2. 根据状态图判断它识别的 Language（语言），或者写出对应的 Regular Expression（正则表达式）

符号	英文	含义
(Q)	Set of States	所有状态（State）的集合，例如 {q0, q1, q2}
(\Sigma)	Alphabet	输入字母表（Alphabet），例如 {0,1}
(\delta)	Transition Function	状态转移函数（Transition Function），规定如何移动
(q_0)	Initial State	开始状态（Initial State）
(F)	Accepting State Set	接受状态集合（Accepting State Set），例如 {q0, q2}

Q      = 所有房间（States）
Σ      = 可以按的按钮（Input Symbols）
δ      = 房间之间的门（Transition Function）
q0     = 出生点（Initial State）
F      = 通关房间（Accepting States）

理论计算与DFA核心复习笔记

目标定位：快速攻克大阪大学（Osaka University）情报工学专业《计算理论》（Theory of Computation）入学考试中 DFA 相关的真题（包括状态图分析、字符串接受判定、语言归纳与正则表达式映射）。

一、 基础概念 (Foundational Concepts)

在深入自动机理论之前，我们需要理清以下三个层层递进、环环相扣的基础概念。它们是构建形式语言与自动机理论的“基石”。 计算理论-CH01-语言与字母表

1. 字母表 (Alphabet, $\Sigma$)

• 定义：一个非空、有限的字符集合。

• 数学符号：通常用大写希腊字母 $\Sigma$ 表示。

• 示例：

  • 二进制字母表：$\Sigma = \{0, 1\}$

  • 英文小写字母表：$\Sigma = \{a, b, c, \dots, z\}$

2. 字符串 (String, $w$)

• 定义：由某个字母表 $\Sigma$ 中的字符拼接而成的有穷序列。

• 空串 (Empty String, $\varepsilon$)：不包含任何字符的特殊字符串，长度为 $0$。

• 字符串的长度 (Length, $|w|$)：字符串中字符的个数。例如：若 $w = abba$，则 $|w| = 4$。

3. 语言 (Language, $L$)

• 定义：字母表 $\Sigma$ 上若干字符串的集合（可以是有限集，也可以是无限集）。也就是说，语言是所有可能字符串集合 $\Sigma^*$ 的子集（$L \subseteq \Sigma^*$）。

• 示例：

  • 若 $\Sigma = \{a, b\}$，则一个语言可以定义为 $L_1 = \{a, aa, aaa\}$（有限集）。

  • 也可以定义为 $L_2 = \{w \in \Sigma^* \mid w \text{ 包含偶数个 } a\}$（无限集）。

二、 确定性有限自动机 (DFA) 的直观理解

有了字母表、字符串和语言的概念，我们就可以引入自动机了。自动机的本质就是一个用来判断特定字符串是否属于某个语言的“识别机”。

1. 什么是 DFA？

DFA 全称为 Deterministic Finite Automaton（确定性有限自动机）。我们可以把它想象成一个简单的控制芯片或机器人：

• 它在任意时刻都处于某个特定的状态 (State) 之中。

• 当它依次读入字符串中的字符时，会按照一套确定的规则（状态转移）跳转到下一个状态。

• Deterministic（确定性） 意味着：在任何状态下，针对每一个输入字符，都有且仅有一条确定的转移边可以走，绝不会出现“无路可走”或“多条路可选”的歧义情况。

2. 判定核心：“只看终点，不看过程”

当自动机读完整个字符串后：

• 如果停在接受状态 (Accepting State / Final State)，则输出 Accept（接受），说明该字符串属于该语言。

• 如果停在普通状态 (Non-final State)，则输出 Reject（拒绝），说明该字符串不属于该语言。

• 注意：判定一个字符串是否被接受，只看输入完全结束时那一刻停留的状态。即使中间多次经过接受状态，只要最后停在普通状态，也是 Reject；反之，即便中间经过了无数次普通状态，只要终点是接受状态，就是 Accept。

三、 DFA 的形式化定义 (Formal Definition)

在学术考试与大阪大学的真题中，题目通常会给出自动机的数学形式化定义。我们必须准确掌握其五元组（5-tuple）模型。

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

符号	英文名称	含义说明	游戏地图比喻
$Q$	Set of States	所有的有限状态集合（如 $\{q_0, q_1, q_2\}$）	地图上所有的房间
$\Sigma$	Alphabet	输入的字母表（如 $\{0, 1\}$）	房间里可以按的按钮
$\delta$	Transition Function	状态转移函数，定义为 $\delta: Q \times \Sigma \to Q$	门上的走线规则（在 $A$ 房间按 $0$ 按钮会去到 $B$ 房间）
$q_0$	Initial State / Start State	初始状态，满足 $q_0 \in Q$	游戏的出生点（有且仅有一个）
$F$	Accepting State Set	接受状态集合，满足 $F \subseteq Q$	游戏的通关房间（可以是零个、一个或多个）

⚠️ 易错点修正（极重要）

手写笔记原话：“F 表示最后落到的状态是不是 Accept State 的那些字符串的集合。” > 纠正：这是完全错误的定义！ > $F$ 绝不是字符串的集合，而是状态 (State) 的集合（$F \subseteq Q$）。

• 例如，$F = \{q_0, q_2\}$ 意味着状态 $q_0$ 和 $q_2$ 是接受状态，它们在状态图中被画成双圈。

• 而“被接受的字符串的集合”被称为该 DFA 识别的语言 (Language Recognized by DFA)，记作 $L(M)$，这才是字符串的集合。请千万不要将形式化定义中的状态集合 $F$ 与语言 $L(M)$ 混淆！

四、 状态图 (State Diagram) 识图与状态分类

考试中，DFA 往往以直观的状态图呈现。掌握状态图的符号逻辑是快速做题的前提。

1. 状态的图形表示

  --> ( q0 )        (( q1 ))
   初始状态/单圈      接受状态/双圈
  (Non-final State)  (Accepting State)

• 初始状态 (Initial State)：有一根没有起点的单向箭头 $\rightarrow$ 指向的状态。

• 接受状态 (Accepting State)：画成双层同心圆（双圈）的状态。

• 普通状态 (Non-final State)：画成单层圆圈的状态。

2. 特殊状态：死状态 / 陷阱状态 (Dead State / Trap State)

• 特征：一旦进入该状态，无论后续输入字母表中的什么字符，转移结果都指向其自身（即无法逃离该状态）。

• 考试意义：如果死状态是非接受状态（Non-final State），它通常代表“出错无法恢复”。只要字符串在读取途中不小心掉进了这个“死胡同”，那么后续无论输入什么，最终结果都必定是 Reject。

⚠️ 概念辨析：DFA 状态与数字电路中的“自启动”

理解澄清：数字电路的状态转移图中有“自启动 (Self-starting)”的概念（指电路由于干扰进入非法状态后能自动返回有效状态）。 但在 DFA（有限自动机） 中：

1. 普通状态 (Non-final State) 完全可以是初始状态 (Initial State)。自动机从这里启动工作完全正常，并非“不能启动”。

2. DFA 的状态没有“非法编码”一说，所有状态都是协议的一部分。Non-final State 仅代表一种“到此为止，尚未满足接受条件”的普通运行位置。

五、 DFA 的模拟运行 (Simulation)

本节通过具体例题，详解判定字符串是否被自动机接受的“四步法”。

判定四步法：

1. 定位起点：找到带有无源箭头的初始状态。

2. 顺序移动：从左到右依次读取字符串中的每一个字符，沿对应的有向边转移。

3. 读毕即停：字符读取完毕时，必须立即停止。

4. 看圈定夺：检查最终停留的状态是否属于接受状态集合 $F$（即是否为双圈）。

📝 例题 1：空串的接受判定

【题目】 考虑以下 DFA：

       a
  --> (( q0 )) -----> ( q1 )

其中，$\Sigma = \{a\}$，$Q = \{q_0, q_1\}$，$F = \{q_0\}$。 若输入空串 $\varepsilon$，结果是 Accept 还是 Reject？为什么？

【分析与解答】

1. 初始状态为 $q_0$。

2. 输入为 $\varepsilon$，表示不输入任何字符，因此自动机不发生任何移动，依然停留在 $q_0$。

3. 停留在 $q_0$，由于 $q_0$ 是双圈（接受状态），因此结果为 Accept。

• 定理：一个 DFA 能否接受空串 $\varepsilon$，有且仅取决于其初始状态 $q_0$ 是否属于接受状态集合 $F$（即初始状态是不是双圈）。

📝 例题 2：标准转移运行与 011 的推导

【题目】 已知一个二进制 DFA 状态转移图如下：

        0 (自环)
       / \
       \ /     1
  --> (( q0 )) -----> ( q1 )
        ^             |
        |_____________|
               1

• $Q = \{q_0, q_1\}$，$\Sigma = \{0, 1\}$，初始状态为 $q_0$，$F = \{q_0\}$。

• 请判断字符串 011 的最终状态，并说明是 Accept 还是 Reject。

【分析与解答】 我们将每一步读入字符时的状态跳转过程记录如下：

读入步骤	当前读入字符	状态转移路径	当前停留状态	是否属于 $F$
初始状态	-	起点	$q_0$	是（Accepting）
步骤 1	0	$\delta(q_0, 0) \to q_0$	$q_0$	是（Accepting）
步骤 2	1	$\delta(q_0, 1) \to q_1$	$q_1$	否（Non-final）
步骤 3	1	$\delta(q_1, 1) \to q_0$	$q_0$	是（Accepting）

• 结论：字符串读完后最终停留在 $q_0$。因为 $q_0 \in F$，所以该字符串被 Accept。

📝 例题 3：运行轨迹演练

【题目】 使用例题 2 中的 DFA 状态图，分别判断以下字符串的结果：

1. 字符串 10

2. 字符串 1

【解答】

1. 对于字符串 10：

   • 开始于 $q_0$。

   • 读入 1：状态跳转为 $q_0 \xrightarrow{1} q_1$。

   • 读入 0：观察状态图，状态 $q_1$ 没有针对字符 0 的显式转移边。

   • 形式化补充说明：若图中未画出，按学术规范，未画出的边默认指向一个隐式的“死状态（Trap State）”。这里我们假设该 DFA 是完全定义的，若 $q_1$ 读 0 留在 $q_1$：

     • 跳转为 $q_1 \xrightarrow{0} q_1$。最终停在 $q_1$（普通状态），结果为 Reject。

2. 对于字符串 1：

   • 开始于 $q_0$。

   • 读入 1：跳转为 $q_0 \xrightarrow{1} q_1$。字符串读毕。

   • 最终停在 $q_1$（普通状态），结果为 Reject。

六、 语言归纳 (Language Induction)

大阪大学计算理论真题中最核心的难点，莫过于“看状态图描述其识别的语言”。为了避免盲目猜测，我们总结出一套系统化分析方法。

💡 语言归纳“四步分析法”

1. 定夺终点：明确哪些状态是 Accepting States（双圈），想一想“满足什么条件的字符串能让我们停在这里”。

2. 短串测试 (Short Strings Testing)：按长度从小到大（$0, 1, 2, 3 \dots$）列举并测试，记录它们是 Accept 还是 Reject。

3. 规律挖掘 (Pattern Recognition)：寻找被接受的字符串集与被拒绝的字符串集之间的内在共性特征。

4. 自然语言定义：用逻辑严密的自然语言写出其判定规则。

📝 例题 4：一维自环归纳

【题目】 分析以下自动机识别的语言：

       a (自环)
      / \
      \ /     b
 --> (( q0 )) ----> ( q1 )

其中，$\Sigma = \{a, b\}$，$F = \{q_0\}$。一旦进入 $q_1$，便无任何出边（隐式死状态）。

【分析与解答】 按“四步分析法”：

1. 唯一接受状态为 $q_0$。

2. 进行测试：

   • 长度 0：$\varepsilon \to$ Accept。

   • 长度 1：a $\to$ Accept；b $\to$ Reject（进入 $q_1$）。

   • 长度 2：aa $\to$ Accept；ab $\to$ Reject；ba $\to$ Reject。

3. 发现规律：只要字符中出现一次 b，自动机就会掉入非接受状态 $q_1$，再也无法返回 $q_0$。而仅包含 a 的字符串会一直自环留在 $q_0$。

4. 语言描述：该 DFA 识别的语言是“所有只包含 $a$ 的字符串（包含空串 $\varepsilon$）”。

📝 例题 5：陷阱状态的应用

【题目】 已知以下 DFA，请归纳其识别的语言，并详细解释为什么字符串 1011 会被拒绝。

        1 (自环)
       / \
       \ /     0       0, 1 (自环)
  --> (( q0 )) ----> ( q1 )

其中，$Q = \{q_0, q_1\}$，$\Sigma = \{0, 1\}$，初始状态为 $q_0$，$F = \{q_0\}$。

【分析与解答】

1. 直观归纳：

   • $q_0$ 是唯一的接受状态。

   • 在 $q_0$ 状态下，只要读到 1 就会自环留在 $q_0$。

   • 一旦读入 0，就会跳转到 $q_1$。在 $q_1$ 状态下，无论读入 0 还是 1，都会无限自环留在 $q_1$。

   • 因此，$q_1$ 是一个典型的死状态/陷阱状态 (Dead State)。

   • 结论：该 DFA 识别的语言是“所有不包含字符 0 的字符串（包含空串 $\varepsilon$）”。

2. 解释字符串 1011 被拒绝的运行轨迹：

   • $q_0 \xrightarrow{1} q_0$

   • $q_0 \xrightarrow{0} q_1$ （落入死状态）

   • $q_1 \xrightarrow{1} q_1$

   • $q_1 \xrightarrow{1} q_1$

   • 最终停在 $q_1$。由于 $q_1 \notin F$（是非接受状态），因此 1011 被 Reject。

📝 例题 6：基于“尾字符”决定的自动机

【题目】 分析以下自动机识别的语言：

       0 (自环)               1 (自环)
      / \                    / \
      \ /        1           \ /
 --> (( q0 )) ---------> ( q1 )
       ^                  |
       |__________________|
                0

其中，$\Sigma = \{0, 1\}$，接受状态为 $q_0$。

【分析与解答】

1. 观察状态跳转逻辑：

   • 无论当前在什么状态，只要读入字符 0，就会转移到 $q_0$。

   • 无论当前在什么状态，只要读入字符 1，就会转移到 $q_1$。

2. 这意味着自动机的最终停留状态有且仅由最后一个字符决定：

   • 若最后一个字符是 0 $\to$ 最终停在 $q_0$ $\to$ Accept。

   • 若最后一个字符是 1 $\to$ 最终停在 $q_1$ $\to$ Reject。

   • 特殊情况：对于空串 $\varepsilon$，停在初始状态 $q_0$ $\to$ Accept。

3. 语言描述：该 DFA 识别的语言是“所有以 0 结尾的字符串，以及空串 $\varepsilon$”（或者描述为“所有不以 1 结尾的字符串”）。

七、 正则表达式 (Regular Expression) 的映射关系

在大阪大学的真题中，往往要求你指出一个 DFA 对应的正则表达式 (Regular Expression, 简称 RE)。DFA 与正则表达式在描述语言的能力上是完全等价的。

以下是基础 RE 符号与语言的对照表：

正则表达式 (RE)	对应的语言集合 (Language)	含义说明
$a$	$\{a\}$	仅包含字符串 "a"
$ab$	$\{ab\}$	连接：先出现 $a$，紧接着出现 $b$
$a + b$ (或 $a \mid b$)	$\{a, b\}$	并集（选择）：要么是 $a$，要么是 $b$
$a^*$	$\{\varepsilon, a, aa, aaa, \dots\}$	克莱尼星号：任意个 $a$（包括零个）
$a^+$	$\{a, aa, aaa, \dots\}$	一个或多个 $a$（不包括空串）

💡 极速映射实例：

• 例题 4 归纳出的语言为“所有只包含 $a$ 的字符串”，对应的正则表达式为：$a^*$。

• 例题 5 归纳出的语言为“所有不包含 $0$、只由 $1$ 构成的字符串”，对应的正则表达式为：$1^*$。

八、 阪大真题思维与实战演练

为了检验对上述知识的掌握程度，请独立尝试完成以下这套模拟真题。

⚔️ 第一关：运行路径判定（快速心算）

【题目】 已知一个二进制 DFA $M_1$，其形式化定义为：

• $Q = \{q_0, q_1\}$

• $\Sigma = \{0, 1\}$

• 初始状态为 $q_0$

• $F = \{q_1\}$ （即只有 $q_1$ 是双圈接受状态）

• 状态转移函数 $\delta$ 的规则如下：

  • $\delta(q_0, 0) = q_0$

  • $\delta(q_0, 1) = q_1$

  • $\delta(q_1, 0) = q_0$

  • $\delta(q_1, 1) = q_1$

请判断以下三个字符串是 Accept 还是 Reject，并写出最终状态：

1. 10100

2. 11111

3. 空串 $\varepsilon$

⚔️ 第二关：语言归纳与 RE 转换

【题目】 针对第一关中的同一个 DFA $M_1$：

1. 请用一句严密的自然语言描述它所识别的语言。

2. 写出该语言对应的正则表达式（Regular Expression）。

⚔️ 第三关：概念纠错

【题目】 在大阪大学真题中，常有形式化定义的对错判断。请问：对于一个 DFA $M = (Q, \Sigma, \delta, q_0, F)$，如果已知它的接受状态集合 $F = \emptyset$（空集），这代表什么物理意义？它是否能够接受任何字符串？

🔑 实战演练答案与深度解析

第一关解析：

我们画出 $M_1$ 的状态转移图：

       0 (自环)               1 (自环)
      / \                    / \
      \ /        1           \ /
  ( q0 )   -------------> (( q1 ))
    ^                     |
    |_____________________|
               0

1. 对于字符串 10100：

   • 轨迹：$q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_0 \xrightarrow{0} q_0$。

   • 最终状态：$q_0$。由于 $q_0 \notin F$，结果为 Reject。

2. 对于字符串 11111：

   • 轨迹：从 $q_0$ 读第一个 1 进入 $q_1$，随后的四个 1 均自环留在 $q_1$。

   • 最终状态：$q_1$。由于 $q_1 \in F$，结果为 Accept。

3. 对于空串 $\varepsilon$：

   • 停留在初始状态 $q_0$。由于 $q_0 \notin F$，结果为 Reject。

第二关解析：

1. 语言描述： 仔细观察可以发现，每次读入 1 会锁定在接受状态 $q_1$，而读入 0 会被退回到普通状态 $q_0$。因此，决定最终是否接受，完全看最后一个读入的字符是否为 1。

   • 答：该 DFA 识别的语言是“所有以 1 结尾的字符串”。

2. 正则表达式： 以 1 结尾，前面可以是任意的 0 和 1 的组合（即 $(0+1)^*$）。

   • 答：*(0+1)1

第三关解析：

• 答：$F = \emptyset$ 意味着该 DFA 的接受状态集合为空（状态图中没有一个状态是双圈）。

• 根据“只看终点”原则，无论输入什么字符串，运行结束时停留的状态都必然属于 $Q \setminus F$（非接受状态）。

• 因此，该自动机无法接受任何字符串（即它识别的语言为空集 $\emptyset$）。