Automata and Theory of Computation Learning Notes: Long-term Accumulation#

1.1 形式定义与转移逻辑#

有限自动机通常由五元组 $M = (Q, \Sigma, \delta, q_0, F)$ 定义：

• $Q$：状态的有限集合 (Finite set of states)
• $\Sigma$：输入字母表 (Input alphabet)
• $\delta$：转移函数 (Transition function)
• $q_0 \in Q$：初始状态 (Start state)
• $F \subseteq Q$：接受状态集合 (Set of accept states)

1.2 正规表达式 (Regular Expressions, RE)#

正规表达式是描述正规语言的代数方法。

• 设计逻辑：约束条件的表达 在设计 RE 时，需重点考虑如何通过局部结构的限制来表达全局约束。
  • 案例：不含连续 00 的 01 串 一个非常“精彩”且简洁的等价形式是：$(1+01)^*(0+\epsilon)$。
    • 「护卫者」逻辑 (Bodyguard Logic)：在这个表达式中，每一个 0 的后面都紧跟着一个 1 作为它的“护卫”，从而杜绝了 00 出现的可能。末尾的 (0+\epsilon) 则允许字符串以一个孤立的 0 结尾。
    • 另一种形式：$1^*(011^*)^*(0+\epsilon)$。这种形式则强调了以 1 开头，后续跟随着“0 + 至少一个 1”的组合。
• Kleene 定理与状态消除法：
  • 任何 FA 都有等价的 RE。
  • 状态消除法：通过递归公式 $R_{ij}^{(k)} = R_{ij}^{(k-1)} \cup R_{ik}^{(k-1)}(R_{kk}^{(k-1)})^*R_{kj}^{(k-1)}$ 将自动机转换为 RE。这代表从 $i$ 到 $j$ 且中间状态编号不超过 $k$ 的路径集合。

1.3 证明方法：数学归纳法 (Mathematical Induction)#

在自动机理论中，常对字符串长度 $n = |w|$ 使用归纳法：

1. 基础步骤：验证 $n=0$（即 $w = \epsilon$）时命题成立。
2. 归纳假设：假设对于长度为 $k$ 的字符串 $w$ 命题成立。
3. 递推步骤：考虑字符串 $wa$（$|wa| = k+1$），利用转移函数 $\hat{\delta}(q, wa) = \delta(\hat{\delta}(q, w), a)$ 进行证明。

1.4 NFA 到 DFA 的转换：子集构造法 (Subset Construction)#

• 核心思想：将 NFA 的所有可能状态组合看作 DFA 的一个新状态。
• 状态爆炸：若 NFA 有 $N$ 个状态，转换后的 DFA 最多可能有 $2^N$ 个状态。

1.5 构造方法：Thompson 构造法 (RE to NFA)#

Thompson 构造法是一种将正规表达式映射为等效 NFA 的系统方法。其核心在于递归地将子表达式通过 $\epsilon$ 转移连接：

• 并集 (Union, $R+S$)：创建一个新的开始和接受状态，通过 $\epsilon$ 转移连接到 $R$ 和 $S$ 的 NFA，形成“并行”结构。
• 连接 (Concatenation, $RS$)：将 $R$ 的接受状态与 $S$ 的起始状态直接相连或通过 $\epsilon$ 转移相连，形成“串行”结构。
• 闭包 (Kleene Star, $R^*$)：
  1. 从 $R$ 的接受状态连回其起始状态（重复执行）。
  2. 增加一个新的起始状态和接受状态，通过 $\epsilon$ 转移直接相连（匹配空串 $\epsilon$）。

1.6 泵引理 (Pumping Lemma) —— 正规性的试金石#

• 核心直觉：鸽巢原理 (Pigeonhole Principle) 若一个 DFA 有 $n$ 个状态，而读取的字符串长度 $|w| \geq n$，则根据鸽巢原理，路径中必然存在重复的状态，即形成了一个“环”。
• 形式化条件：若 $L$ 是正规语言，则存在常数 $n$（泵长度），使得任何 $w \in L$ 且 $|w| \geq n$ 均可拆分为 $w = xyz$，满足：
  1. $|xy| \leq n$（环出现在前 $n$ 个状态内）
  2. $y \neq \epsilon$（环不能为空）
  3. $\forall k \geq 0, xy^k z \in L$（环可以被任意次“泵入”）

3.1 证明语言非正规性 (Using Pumping Lemma)#

题目 1：证明 $L = \{0^i 1^i \mid i \geq 0\}$ 不是正规语言。

• 反证法步骤：
  1. 假设 $L$ 是正规语言，其泵长度为 $n$。
  2. 选定字符串 $w = 0^n 1^n$。显然 $w \in L$ 且 $|w| = 2n \geq n$。
  3. 拆分 $w = xyz$。由条件 $|xy| \leq n$ 可知，$y$ 必然全由 0 组成。
  4. 令 $k=0$（抽去环）或 $k=2$（增加环）。此时 $xy^2z = 0^{n+|y|} 1^n$。
  5. 由于 $|y| > 0$，故 $n+|y| \neq n$，导致 $xy^k z \notin L$，产生矛盾。
  6. 结论：$L$ 不是正规语言。

题目 2：证明 $L = \{0^i 1^j \mid i > j\}$ 不是正规语言。

• 关键策略：Pumping Down ($k=0$)
  1. 取 $w = 0^{n+1} 1^n \in L$。
  2. 根据 $|xy| \leq n$，$y$ 仍在 $0$ 的区域内。
  3. 若抽出 $y$（即 $k=0$），得到 $xz = 0^{n+1-|y|} 1^n$。
  4. 由于 $|y| \geq 1$，则 $n+1-|y| \leq n$，即 $0$ 的数量不再大于 $1$。
  5. 矛盾：$xz \notin L$。

题目 3：证明 $L = \{a^3 b^n c^{n-3} \mid n \geq 3\}$ 不是正规语言。

• 多维约束分析：
  1. 取 $w = a^3 b^n c^{n-3}$。
  2. 由于 $|xy| \leq n$，$y$ 可能全由 $a$ 组成，或全是 $b$，或两者的混合。
  3. Case 1 ($y = a^m$)：Pump $y$ 会改变起始 $a$ 的固定数量（必须为 3）。
  4. Case 2 ($y = b^m$)：Pump $y$ 会打破 $n_c = n_b - 3$ 的数量平衡。
  5. Case 3 ($y$ 为混合, $y = a^r b^s$)：Pump $y$（例如 $k=2$）会导致 $a$ 与 $b$ 交错出现（形成诸如 $a^3 b \dots a^r b^s \dots$ 的模式），直接破坏了语言要求的“全 $a$ 在前，全 $b$ 在后，全 $c$ 在末尾”的固定字符顺序。
  6. 结论：无论 $y$ 落在哪里，通过 Pump ($k=0$ 或 $k \geq 2$) 均可推导出矛盾。

3.2 映射分类应用 (Set Theory)#

• 单射 (Injection)：客房服务。每个客人对应一个不同房间，但不一定住满。
• 满射 (Surjection)：所有房间都住满了人，但可能有房间住了多个人。
• 全单射 (Bijection)：完美的匹配，每个人都有独立房间且刚好住满。