📝 我的笔记

还没有笔记

选中页面文字后点击「高亮」按钮添加

1_正则语言1.2.ZH解释

📜 原文
📖 逐步解释
∑ 公式拆解
💡 数值示例
⚠️ 易错点
📝 总结
🎯 存在目的
🧠 直觉心智模型
💭 直观想象

11. 对"1.2 非确定性"章节的详尽解释

1.1 非确定性概念引入

11.1 原文

非确定性是一个有用的概念,它对计算理论产生了巨大影响。到目前为止,在我们的讨论中,计算的每一步都以一种独特的方式从前一步推导出来。当机器处于给定状态并读取下一个输入符号时,我们知道下一个状态将是什么——它是确定的。我们称之为确定性计算。在非确定性机器中,在任何时候都可能存在多种选择以进入下一个状态。

11.2 逐步解释

这个段落引入了计算理论中一个非常核心且强大的概念:非确定性(Nondeterminism)。为了理解非确定性,我们首先要回顾它所对应的概念:确定性(Determinism)。

  1. 确定性计算 (Deterministic Computation):
    • 想象一个非常守规矩、一步一个脚印的机器人。你给它一个指令,它只会执行一个完全确定、预先设定好的动作。
    • 在计算理论中,一个确定性的机器(比如我们之前学习的确定性有限自动机,即DFA),其行为是完全可预测的。
    • “可预测”意味着:在任何一个给定的状态(State),当它读取一个特定的输入符号(Symbol)时,它将要转移到的下一个状态唯一确定的。
    • 例如,如果机器在状态 $q_A$,读到符号 1,规则手册上白纸黑字写着“必须转移到状态 $q_B$”,那么它绝无可能转移到任何其他状态,比如 $q_C$ 或留在 $q_A$(除非规则就是转移到自身)。
    • 这个过程就像一个函数 $f(x) = y$,输入一个 $x$,总能得到唯一确定的 $y$。在这里,(当前状态, 输入符号) 就是输入,下一个状态 就是输出。
  2. 非确定性计算 (Nondeterministic Computation):
    • 现在想象一个拥有“分身术”的魔法机器人。当它面临选择时,比如走到一个岔路口,它可以同时走向所有可能的路径。
    • 一个非确定性的机器(比如本节将要介绍的非确定性有限自动机,即NFA),在某些情况下,其下一步的行为不是唯一的。
    • “不唯一”意味着:在某个给定的状态,当它读取一个特定的输入符号时,它可能同时多个可供选择的下一个状态
    • 例如,机器在状态 $q_A$,读到符号 1,它的规则手册上可能写着:“你可以选择转移到状态 $q_B$,或者转移到状态 $q_C$,或者留在状态 $q_A$”。
    • 这时,机器会“分身”,产生多个并行的计算分支,一个分支去 $q_B$,一个分支去 $q_C$,一个分支留在 $q_A$。这所有的分支会同时继续进行后续的计算。

11.3 具体数值示例

11.4 易错点与边界情况

11.5 总结

本段落的核心思想是区分两种计算模型:确定性计算非确定性计算。确定性计算的路径是唯一的、线性的;而非确定性计算则允许在某些点产生多个并行的计算分支,形成一棵充满可能性的“计算树”。

11.6 存在目的

引入非确定性的概念是为了提供一个更强大、更灵活的理论工具。尽管后面会证明NFA在计算能力上并不比DFA强(任何NFA都能转换成等价的DFA),但使用NFA来设计和描述某些语言的识别器会极其简单和直观。它让我们能够从“猜测”和“验证”的角度来思考问题,而不是纠结于如何用确定性的状态机来记住所有复杂的历史信息。

11.7 直觉心智模型

11.8 直观想象

想象你在一个迷宫里找出口。

1.2 NFA的特性与DFA的区别

12.1 原文

非确定性是确定性的一种推广,因此每个确定性有限自动机自动也是非确定性有限自动机。正如图1.27所示,非确定性有限自动机可能具有额外的特性。

图 1.27

非确定性有限自动机 $N_{1}$

确定性有限自动机(缩写为DFA)与非确定性有限自动机(缩写为NFA)之间的区别显而易见。首先,DFA的每个状态对于字母表中的每个符号总是恰好有一条出转换箭头。图1.27所示的NFA违反了这一规则。状态$q_{1}$对0有一条出箭头,但对1有两条;$q_{2}$对0有一条箭头,但对1没有。在NFA中,一个状态对于每个字母表符号可以有零条、一条或多条出箭头。

其次,在DFA中,转换箭头上的标签是字母表中的符号。这个NFA有一条带标签$\varepsilon$的箭头。通常,NFA可能具有标有字母表成员或$\varepsilon$的箭头。从每个状态可以有零条、一条或多条带标签$\varepsilon$的箭头射出。

12.2 逐步解释

这段话详细阐述了NFA区别于DFA的两个关键特征,并通过一个具体的例子 $N_1$ 来进行说明。

  1. NFA是DFA的推广
    • 这句话再次强调了我们在前面提到的关系:DFA是一种行为非常受限的特殊NFA。
    • 一个DFA之所以也是NFA,是因为对于DFA的每一个“唯一选择”,我们都可以把它看作是一个只包含一个元素的“选择集合”。例如,DFA规定 $\delta(q, a) = p$,这在NFA的视角下可以写成 $\delta(q, a) = \{p\}$。由于它满足NFA的广义定义,所以所有DFA都是NFA。
  2. NFA的两个核心“法外特权”
    • 特权一:灵活的转换数量
    • DFA的严格规定:对于字母表中的每一个符号,每一个状态都必须且仅有一个出转换。不能多,也不能少。
    • NFA的自由:一个状态对于一个符号,可以有:
    • 多条出转换:如图1.27中的状态 $q_1$ 对输入 1,既可以回到 $q_1$,也可以去 $q_2$。这就是产生“分身”的地方。
    • 零条出转换:如图1.27中的状态 $q_2$ 对输入 1,没有任何出箭头。如果计算分支到达 $q_2$ 并且下一个输入是 1,这个分支就会“死亡”。
    • 一条出转换:如图1.27中的状态 $q_1$ 对输入 0,只有一条出箭头回到 $q_1$。这看起来和DFA一样,但它只是NFA自由选择中的一种情况。
    • 特权二:$\varepsilon$ 转换(epsilon-transition)
    • DFA的规则:转换必须由消耗一个输入符号来触发。箭头上写的必须是字母表 $\Sigma$ 里的符号。
    • NFA的“瞬移”能力:NFA引入了一种特殊的转换,标记为 $\varepsilon$ (epsilon)。
    • $\varepsilon$ 转换的意义是“不消耗任何输入符号,就可以自发地”从一个状态转移到另一个状态。
    • 如图1.27中,从 $q_2$$q_3$ 有一条 $\varepsilon$ 箭头。这意味着,任何时候只要一个计算分支到达了状态 $q_2$,它就会立刻产生一个“分身”,这个分身会瞬间移动到 $q_3$。原来的那个计算分支可以选择停留在 $q_2$(如果后续还有路可走)。
    • 你可以把它想象成一个免费的、瞬间的、并行的状态转移。一个状态也可以有多条 $\varepsilon$ 出箭头,实现到多个状态的“瞬移”。

12.3 具体数值示例

让我们用图1.27的NFA $N_1$ 来剖析这两个特权:

12.4 易错点与边界情况

12.5 总结

本段落明确指出了NFA与DFA的两个根本区别:

  1. 转换数量的灵活性:NFA的一个状态对一个输入符号可以有0、1或多于1个转换,而DFA必须是恰好1个。
  2. $\varepsilon$转换的存在:NFA可以不消耗输入符号就进行状态转移,而DFA必须消耗一个符号才能转移。

这两个特性赋予了NFA强大的表达能力和设计上的便利性。

12.6 存在目的

本段落的目的是从结构上清晰地定义NFA,并与我们已知的DFA模型进行对比,让读者能够准确地抓住NFA的核心特征。这为后续理解NFA如何计算、如何设计以及它与DFA之间的等价关系奠定了基础。通过具体的图示 $N_1$,将抽象的规则变得具体化,易于理解。

12.7 直觉心智模型

12.8 直观想象

再次回到迷宫的比喻:

1.3 NFA的计算方式

13.1 原文

NFA如何计算?假设我们正在输入字符串上运行NFA,并到达一个有多种方式可以继续的状态。例如,假设我们在NFA $N_{1}$中的状态$q_{1}$,并且下一个输入符号是1。读取该符号后,机器会分裂成自身的多个副本并并行地遵循所有可能性。机器的每个副本都采取其中一种可能的方式继续,并像以前一样进行。如果存在后续选择,机器会再次分裂。如果下一个输入符号没有出现在机器副本所占据的状态的任何出箭头上,那么该机器副本以及与之相关的计算分支就会“死亡”。最后,如果这些机器副本中的任何一个在输入结束时处于接受状态,则NFA接受该输入字符串。

如果遇到带有$\varepsilon$符号的出箭头状态,也会发生类似的情况。不读取任何输入,机器会分裂成多个副本,一个副本遵循每个带有$\varepsilon$标签的出箭头,另一个副本停留在当前状态。然后机器像以前一样非确定性地进行。

13.2 逐步解释

这段话生动地描述了NFA的“灵魂”——它的计算过程。这个过程可以分解为以下几个关键步骤和原则:

  1. 并行宇宙模型
    • NFA的计算不是一条线,而是一棵不断分叉的“可能性之树”。
    • 核心思想:当面临选择时,NFA不选择,而是全部都要
    • 分裂/克隆:当一个计算分支(可以想象成一个“活跃指针”或一个“副本”)在一个状态下,读取一个输入符号,并且这个符号对应多个转换路径时,这个分支就会分裂(或克隆)成多个新的分支。每个新分支走一条路径。
    • 并行处理:所有存在的计算分支都会同时并行地处理下一个输入符号。
  2. 计算分支的生命周期
    • 诞生 (分裂):在起始状态,只有一个分支。当遇到多重转换或$\varepsilon$转换时,新的分支就诞生了。
    • 存活 (继续):只要当前分支所在的状态,对于下一个输入符号,有至少一条出路,这个分支就能继续存活下去,转移到新的状态集。
    • 死亡 (终止):如果一个分支所在的状态,对于下一个输入符号,没有任何出路(即转换为空集 $\emptyset$),那么这个计算分支就走到了尽头,它会立即“死亡”并从计算中消失。
  3. $\varepsilon$转换的特殊处理
    • $\varepsilon$转换是即时不消耗输入的。
    • 当一个计算分支到达一个有$\varepsilon$出箭头的状态时,它会立即分裂。
    • 一个分身会瞬间沿着$\varepsilon$箭头“传送”到目标状态。如果有多条$\varepsilon$箭头,就会分裂出多个分身,分别传送到各自的目标状态。
    • 本体(或另一个分身)会停留在当前状态,准备读取下一个输入符号。这一步是关键,$\varepsilon$转换并不会阻止当前状态处理输入。
    • 这个过程可能会连锁反应:如果传送到的新状态也有$\varepsilon$转换,那么这个新生的分身会继续分裂和传送,直到所有由$\varepsilon$连接的路径都被探索完毕。所有这些连锁反应都发生在处理同一个输入符号之前(或者说,在两个输入符号之间的瞬间)。
  4. 接受条件
    • NFA处理完整个输入字符串后(即读完最后一个符号)。
    • 我们会检查所有存活下来的计算分支。
    • 只要至少有一个分支停留在接受状态(Final State)中,整个NFA就接受(Accept)这个输入字符串。
    • 如果处理完输入后,没有任何一个存活的分支停留在接受状态(可能所有分支都死了,或者存活的分支都在非接受状态),那么NFA就拒绝(Reject)这个输入字符串。

13.3 具体数值示例

让我们再次使用图1.27的NFA $N_1$ 来模拟输入字符串 "10" 的计算过程。

模拟开始:

  1. 初始状态: 计算开始,我们在起始状态 $q_1$。当前活跃状态集合是 $\{q_1\}$
  2. 读取第一个符号 '1':
    • 我们在状态 $q_1$。查阅规则,对于输入 '1',我们有两条路:回到 $q_1$ 和去 $q_2$
    • 计算分支分裂。一个分支留在 $q_1$,另一个分支移动到 $q_2$
    • 此时,活跃状态的临时集合是 $\{q_1, q_2\}$
    • 检查 $\varepsilon$ 转换:状态 $q_1$ 没有 $\varepsilon$ 转换。状态 $q_2$ 有一条到 $q_3$$\varepsilon$ 转换。
    • $q_2$ 的分支立即再次分裂,一个分身“瞬移”到 $q_3$
    • 因此,在消耗完符号 '1' 之后,所有并行的计算分支所在的状态集合是 $\{q_1, q_2, q_3\}$
  3. 读取第二个符号 '0':
    • 我们现在并行地从 $\{q_1, q_2, q_3\}$ 这三个状态出发,读取 '0'。
    • $q_1$ 出发: 读 '0',规则是回到 $q_1$。所以这个分支移动到 $q_1$
    • $q_2$ 出发: 读 '0',规则是去 $q_3$。所以这个分支移动到 $q_3$
    • $q_3$ 出发: 读 '0',没有出路(转换是 $\emptyset$)。所以这个分支死亡
    • 在处理完所有分支后,新的活跃状态临时集合是 $\{q_1, q_3\}$
    • 检查 $\varepsilon$ 转换: $q_1$$q_3$ 都没有 $\varepsilon$ 转换。
    • 因此,在消耗完符号 '0' 之后,最终的活跃状态集合是 $\{q_1, q_3\}$
  4. 输入结束:
    • 字符串 "10" 已经处理完毕。
    • 我们检查最终的活跃状态集合 $\{q_1, q_3\}$
    • 我们看这个集合中是否有接受状态。接受状态是 $\{q_4\}$
    • 集合 $\{q_1, q_3\}$ 与集合 $\{q_4\}$ 的交集是空集。
    • 结论: 没有任何一个计算分支停留在接受状态。因此,NFA $N_1$ 拒绝字符串 "10"。

13.4 易错点与边界情况

13.5 总结

本段落阐明了NFA的核心计算范式:并行探索。它通过“分裂”来处理多重选择,通过“死亡”来终结无效路径,通过特殊的$\varepsilon$转换实现“瞬移”,最终以“只要有一线希望就成功”的乐观主义精神来判断是否接受一个字符串。

13.6 存在目的

此段的目的是为了让读者建立起对NFA动态行为的正确认知。与DFA的线性、确定性路径不同,NFA的计算过程是动态的、并行的、树状的。理解这个过程是后续分析NFA能力、设计NFA以及理解NFA与DFA等价性转换的基础。

13.7 直觉心智模型

13.8 直观想象

想象一个大型多人在线角色扮演游戏(MMORPG)中的“打副本”过程。

1.4 计算的可视化

14.1 原文

非确定性可以看作是一种并行计算,其中多个独立的“进程”或“线程”可以并发运行。当NFA分裂以遵循多个选择时,这对应于一个进程“分叉”成多个子进程,每个子进程独立进行。如果至少有一个这样的进程接受,那么整个计算就接受。

考虑非确定性计算的另一种方式是将其视为一个可能性树。树的根对应于计算的开始。树中的每个分支点对应于机器有多种选择的计算点。如果至少一个计算分支以接受状态结束,则机器接受,如图1.28所示。

图 1.28

带有接受分支的确定性与非确定性计算

14.2 逐步解释

这段话提供了两种非常有用的高级视角来理解和可视化NFA的计算过程:并行进程计算树

  1. 并行进程/线程 (Parallel Processes/Threads)
    • 这个类比将NFA的计算与现代计算机科学中的并发编程联系起来。
    • 主进程:NFA的计算始于一个单一的进程,位于起始状态。
    • 分叉 (Forking):当遇到非确定性选择(多重转换或$\varepsilon$转换)时,就如同操作系统中的 fork() 系统调用。当前进程会创建一个或多个子进程
    • 独立执行:每个子进程(以及父进程)都拥有自己独立的状态和执行路径,它们并发地、互不干扰地处理接下来的输入。
    • 进程终止:当一个计算分支“死亡”时,就好比一个进程执行完毕或异常退出。
    • 成功条件:只要有任何一个进程在处理完所有输入后,发现自己处于“成功”状态(即接受状态),整个任务就被认为是成功的。
  2. 可能性之树 (Tree of Possibilities)
    • 这是一个更数学化、更直观的几何模型,如图1.28所示。
    • 树根 (Root):代表整个计算的起点,即在处理第一个输入符号之前的起始状态。
    • 节点 (Node):树中的每个节点可以代表一个 (状态, 剩余输入) 的组合。
    • 分支 (Branching):当机器在一个节点上有多种选择时,这个节点就会生长出多条树枝,每条树枝代表一个选择。
    • 在图1.28的右侧(非确定性计算),在初始状态读入第一个符号后,产生了3个分支,代表有3种可能性。
    • 之后,中间那个分支在读入第二个符号后又分裂成2个分支。
    • 路径 (Path):从树根到任意一个节点的路径,代表了一个完整的计算历史。
    • 叶子节点 (Leaf Node):代表一个计算分支的终点。这个终点可能是因为输入处理完毕,也可能是因为中途“死亡”。
    • 接受路径:如果在输入处理完毕时,有一条从根到叶子节点的路径,其终点(叶子节点)的状态是接受状态,那么这条路径就是一条“接受路径”。
    • 接受条件:整棵树只要存在至少一条接受路径,NFA就接受该输入。图1.28中,最右侧的路径最终到达了一个接受状态(图中未明确标出,但用“accept”示意),因此整个计算是接受的。

14.3 具体数值示例

让我们用图1.27的NFA $N_1$ 和输入 "101" 来构建一个计算树:

树的构建:

  1. : (q1, "101") (在q1,等待处理"101")
  2. 第一层 (处理 '1'): 从 $q_1$ 读 '1',可以到 $q_1$$q_2$。同时 $q_2$$\varepsilon$$q_3$
    • 分支1: (q1, "01")
    • 分支2: (q2, "01")
    • 分支3 (由分支2的$\varepsilon$产生): (q3, "01")
  3. 第二层 (处理 '0'):
    • (q1, "01") 读 '0' -> (q1, "1")
    • (q2, "01") 读 '0' -> (q3, "1")
    • (q3, "01") 读 '0' -> (无路可走, 此分支死亡)
  4. 第三层 (处理 '1'):
    • (q1, "1") 读 '1' -> 分裂成 (q1, ""), (q2, "")。其中 (q2, "") 又立即$\varepsilon$分裂出 (q3, "")。所以活跃状态是 $\{q_1, q_2, q_3\}$
    • (q3, "1") 读 '1' -> (q4, "")
  5. 结束 (输入为空 ""):
    • 我们检查所有叶子节点的状态:
    • 来自第一个主要分支的叶子节点状态是 $\{q_1, q_2, q_3\}$
    • 来自第二个主要分支的叶子节点状态是 $\{q_4\}$
    • 最终状态集合: 所有幸存分支的集合是 $\{q_1, q_2, q_3, q_4\}$
    • 判断: 这个集合中包含了接受状态 $q_4$
    • 结论: NFA $N_1$ 接受 "101"。

这棵树形象地展示了所有并行的可能性。

14.4 易错点与边界情况

14.5 总结

本段通过两个核心类比——并行进程计算树——为非确定性计算提供了一个高层次的、直观的理解框架。这两个模型都强调了NFA的“并行探索”和“只要有一路通即可”的本质。

14.6 存在目的

在详细描述了NFA的底层操作后,本段的目的是提供一个“更高维度”的视角,帮助读者将这些零碎的规则(分裂、死亡、$\varepsilon$转换)整合到一个统一的、概念性的框架中。这使得理解和推理NFA的行为变得更加容易,也为后续更复杂的计算模型(如图灵机中的非确定性)打下概念基础。

14.7 直觉心智模型

14.8 直观想象

想象一下光线通过一个复杂的光学仪器。

1.5 NFA计算示例分析

15.1 原文

让我们考虑NFA $N_{1}$(如图1.27所示)的一些样本运行。$N_{1}$在输入010110上的计算如下图所示。

图 1.29

$N_{1}$在输入010110上的计算

在输入010110上,从起始状态$q_{1}$开始并读取第一个符号0。从$q_{1}$开始,对0只有一个去处——即回到$q_{1}$——所以停留在那里。接下来,读取第二个符号1。在$q_{1}$上读取1时,有两种选择:要么停留在$q_{1}$,要么移动到$q_{2}$。非确定性地,机器分裂成两个副本以遵循每个选择。通过在机器可能处于的每个状态上放置一个手指来跟踪这些可能性。所以你现在在状态$q_{1}$$q_{2}$上都有手指。一个$\varepsilon$箭头从状态$q_{2}$射出,所以机器再次分裂;一个手指留在$q_{2}$上,另一个移动到$q_{3}$。你现在在$q_{1}$$q_{2}$$q_{3}$上都有手指。

读取第三个符号0时,依次取下每个手指。将$q_{1}$上的手指保持在原位,将$q_{2}$上的手指移动到$q_{3}$,并移除原本在$q_{3}$上的手指。最后一个手指没有0箭头可遵循,对应于一个简单地“死亡”的进程。此时,你的手指停留在状态$q_{1}$$q_{3}$上。

读取第四个符号1时,将$q_{1}$上的手指分成$q_{1}$$q_{2}$上的手指,然后将$q_{2}$上的手指进一步分裂以跟随$\varepsilon$箭头到$q_{3}$,并将原本在$q_{3}$上的手指移动到$q_{4}$。你现在在所有四个状态上都有手指。

读取第五个符号1时,正如你用第四个符号看到的那样,$q_{1}$$q_{3}$上的手指会产生在状态$q_{1}$$q_{2}$$q_{3}$$q_{4}$上的手指。$q_{2}$上的手指被移除。原本在$q_{4}$上的手指仍然停留在$q_{4}$上。现在你在$q_{4}$上有了两个手指,所以移除一个,因为你只需要记住$q_{4}$在此时是一个可能的州,而不是它可能因为多种原因。

读取第六个也是最后一个符号0时,将$q_{1}$上的手指保持在原位,将$q_{2}$上的手指移动到$q_{3}$,移除原本在$q_{3}$上的手指,并将$q_{4}$上的手指保持在原位。你现在处于字符串的末尾,如果某个手指处于接受状态,则你接受。你的手指停留在状态$q_{1}$$q_{3}$$q_{4}$上;由于$q_{4}$是一个接受状态,$N_{1}$接受这个字符串。

15.2 逐步解释

这一长段通过“手指模拟法”,极其细致地一步步追踪了NFA $N_1$ 对输入字符串 010110 的处理过程。这个过程可以用一个表格来更清晰地展现,表格追踪每一步之后活跃状态的集合

| 步骤 | 已处理的输入 | 待处理的输入 | 当前活跃状态集合 (处理输入前) | 读取的符号 | 转换后的临时集合 | $\varepsilon$-闭包 | 最终活跃状态集合 (处理输入后) |

| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |

| 0 | "" | "010110" | $\{q_1\}$ | (开始) | N/A | (从$q_1$开始没有$\varepsilon$转换) | $\{q_1\}$ |

| 1 | "0" | "10110" | $\{q_1\}$ | 0 | 从 $q_1$ 读 0 到 $\{q_1\}$ | $\{q_1\}$ | $\{q_1\}$ |

| 2 | "01" | "0110" | $\{q_1\}$ | 1 | 从 $q_1$ 读 1 到 $\{q_1, q_2\}$ | $\{q_1\}$不变, $\{q_2\}$增加$q_3$ | $\{q_1, q_2, q_3\}$ |

| 3 | "010" | "110" | $\{q_1, q_2, q_3\}$ | 0 | 从$q_1$读0到$q_1$; 从$q_2$读0到$q_3$; 从$q_3$读0死亡 | $\{q_1\}$不变, $\{q_3\}$不变 | $\{q_1, q_3\}$ |

| 4 | "0101" | "10" | $\{q_1, q_3\}$ | 1 | 从$q_1$读1到$\{q_1, q_2\}$; 从$q_3$读1到$q_4$。合并得$\{q_1, q_2, q_4\}$ | 从$q_2$增加$q_3$。合并得$\{q_1, q_2, q_3, q_4\}$ | $\{q_1, q_2, q_3, q_4\}$ |

| 5 | "01011" | "0" | $\{q_1, q_2, q_3, q_4\}$ | 1 | 从$q_1$读1到$\{q_1, q_2\}$; 从$q_2$读1死亡; 从$q_3$读1到$q_4$; 从$q_4$读1到$q_4$。合并得$\{q_1, q_2, q_4\}$ | 从$q_2$增加$q_3$。合并得$\{q_1, q_2, q_3, q_4\}$ | $\{q_1, q_2, q_3, q_4\}$ |

| 6 | "010110" | "" | $\{q_1, q_2, q_3, q_4\}$ | 0 | 从$q_1$读0到$q_1$; 从$q_2$读0到$q_3$; 从$q_3$读0死亡; 从$q_4$读0到$q_4$。合并得$\{q_1, q_3, q_4\}$ | $\{q_1\}$, $\{q_3\}$, $\{q_4\}$均无$\varepsilon$转换 | $\{q_1, q_3, q_4\}$ |

最终判断:

解释原文中的几个细节:

15.3 具体数值示例

原文已经提供了一个非常详尽的示例。我们再补充一个拒绝的例子来对比。

  1. 开始: 活跃状态 $\{q_1\}$
  2. 读 '0': 从 $q_1$ 读 '0' 到 $q_1$。活跃状态 $\{q_1\}$
  3. 读 '1': 从 $q_1$ 读 '1' 到 $\{q_1, q_2\}$。由于 $q_2$$\varepsilon$ 转换,活跃状态变为 $\{q_1, q_2, q_3\}$
  4. 读 '0':
    • $q_1$ 读 '0' 到 $q_1$
    • $q_2$ 读 '0' 到 $q_3$
    • $q_3$ 读 '0' 死亡。
    • 合并结果,新的活跃状态为 $\{q_1, q_3\}$
  5. 输入结束:
    • 最终活跃状态集合是 $\{q_1, q_3\}$
    • 这个集合与接受状态集合 $\{q_4\}$ 的交集是空集。
    • 结论: NFA $N_1$ 拒绝 字符串 010

15.4 易错点与边界情况

  1. 初始化一个空集合 $T$
  2. 对于 $S_i$ 中的每一个状态 $q$:计算 $\delta(q, \text{input}_i)$,把结果(一个状态集合)加入到 $T$ 中。
  3. 计算 $T$ 中所有状态的 $\varepsilon$-闭包,即 $S_{i+1} = E(T)$。其中 $E(T)$ 表示从 $T$ 中任何状态出发,只通过0个或多个 $\varepsilon$ 箭头能到达的所有状态的集合。

15.5 总结

本段通过一个具体的、循序渐进的例子,将前面介绍的NFA计算规则付诸实践。它展示了如何动态地追踪活跃状态集合,如何处理多重转换和 $\varepsilon$ 转换,以及最终如何根据输入结束时的状态来做出接受或拒绝的判断。

15.6 存在目的

这个例子的目的是巩固读者对NFA计算过程的理解。理论规则往往是抽象的,而一个具体的、手把手的演练能够极大地帮助读者建立起对这个动态过程的坚实感觉。它为读者自行分析其他NFA和输入提供了模仿的范本。

15.7 直觉心智模型

多世界诠释:NFA的计算就像物理学中的“多世界诠释”。每当遇到一个选择,宇宙(计算)就分裂成多个平行的宇宙,每个宇宙里发生一种可能性。只要在输入结束时,有一个宇宙里的你(计算分支)处于“幸福”状态(接受状态),那么对于最初的你来说,整个事件就是“成功”的。

15.8 直观想象

想象你在玩一个弹珠游戏机。

1.6 NFA识别的语言

16.1 原文

通过继续以这种方式进行实验,你将看到$N_{1}$接受所有包含子字符串101或11的字符串。

非确定性有限自动机在几个方面都很有用。正如我们将展示的,每个NFA都可以转换为等价的DFA,并且构建NFA有时比直接构建DFA更容易。NFA可能比其确定性对应物小得多,或者其功能可能更容易理解。有限自动机中的非确定性也是更强大的计算模型中非确定性的一个很好的介绍,因为有限自动机特别容易理解。现在我们来看几个NFA的例子。

16.2 逐步解释

这段话分为两部分:对NFA $N_1$ 功能的总结,以及对NFA概念重要性的阐述。

  1. NFA $N_1$ 的功能
    • 原文断言 $N_1$ 识别的语言是“所有包含子字符串 10111 的字符串”。
    • 我们来直观地理解为什么。观察 $N_1$ 的结构:
    • 起始状态 $q_1$ 有一个自循环,可以吃掉任意多的 01。这代表机器在“等待”某个关键模式的出现。
    • 要想到达最终的接受状态 $q_4$,必须经过路径 $q_1 \to q_2 \to q_3 \to q_4$
    • 分析路径 $q_1 \to q_2 \to q_3 \to q_4$
    • $q_1$$q_2$ 需要一个 1
    • $q_2$$q_3$ 需要一个 0。(注意,从$q_2$$q_3$还有一条$\varepsilon$路,我们稍后分析)
    • $q_3$$q_4$ 需要一个 1
    • 所以,如果机器走 $q_1 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \xrightarrow{1} q_4$ 这条路,它就成功匹配了子串 101。一旦到达 $q_4$,由于 $q_4$01 都有自循环,后面跟任何东西都无所谓,机器将永远停留在接受状态。
    • 现在分析另一条通往成功的路径。注意到 $N_1$ 的设计中,从 $q_1$1 可以到 $q_2$,而 $q_2$ 立即可以 $\varepsilon$ 跳到 $q_3$。这意味着什么?
    • 当机器在 $q_1$ 读到第一个 1 时,它分裂到 $\{q_1, q_2, q_3\}$
    • 如果下一个输入符号是 1,会发生什么?
    • $q_1$ 的分支,可以继续分裂到 $\{q_1, q_2, q_3\}$
    • $q_2$ 的分支,死亡。
    • $q_3$ 的分支,可以移动到 $q_4$
    • 所以,路径 $q_1 \xrightarrow{1} q_2 \xrightarrow{\varepsilon} q_3 \xrightarrow{1} q_4$ 使得机器在读到子串 11 后能够到达接受状态 $q_4$
    • 结论:NFA $N_1$ 的设计逻辑就是:在任意位置,一旦“猜测”(非确定性地进入)可能出现了 10111,就沿着对应的路径去验证。如果验证成功(到达$q_4$),就接受。这就是它识别包含 10111 的字符串的原理。
  2. NFA 的重要性
    • 等价性 (Equivalence):这是一个核心定理(后面会证明),即 NFA 和 DFA 的计算能力是相同的。任何一个NFA能够识别的语言,也必然存在一个DFA能够识别它,反之亦然。它们都恰好能识别正则语言这一族。
    • 设计便利性 (Easier to construct):这是NFA最有用的地方。对于很多语言,直接设计一个DFA会非常复杂,因为DFA需要“记住”很多信息。而设计NFA则可以利用“猜测”的能力,让结构变得异常简洁和直观。例如,要识别包含 101 的语言,DFA需要多个状态来记录“我看到了1”、“我看到了10”、“我看到了101”,而NFA可以很简单地设计。
    • 简洁性 (Much smaller):通常,对于同一个语言,NFA的状态数量可能远远少于等价的DFA的状态数量。在最坏情况下,一个 $k$ 个状态的NFA可能需要一个拥有 $2^k$ 个状态的DFA来等价模拟。
    • 教学价值 (Good introduction):NFA中的非确定性概念相对简单,是通往更高级计算模型(如非确定性图灵机)的一个很好的入门台阶。

16.3 具体数值示例

16.4 易错点与边界情况

16.5 总结

本段落是承上启下的过渡。它总结了第一个例子NFA $N_1$的功能,并引出了NFA作为一个理论工具的三个核心价值:与DFA等价,设计上更简单更小,以及作为学习后续概念的好起点

16.6 存在目的

在深入展示了NFA的计算细节后,本段的目的是回答一个重要问题:“我们为什么要学习NFA这么一个看起来有点奇怪的模型?” 答案是,它是一个非常有用的抽象工具,能让我们以更简洁、更强大的方式思考和解决问题,即使它的底层能力并未超越我们已知的模型。

16.7 直觉心智模型

16.8 直观想象

想象你要写一份寻人启事。

1.7 示例 1.30: 识别倒数第三位是1的语言

17.1 原文

$A$是所有包含一个1在倒数第三个位置的字符串组成的语言(例如,000100在$A$中,但0011不在)。下面的四状态NFA $N_{2}$识别$A$

图 1.31

识别$A$的NFA $N_{2}$

看待这个NFA计算的一种好方法是说它停留在起始状态$q_{1}$,直到它“猜测”距离末尾还有三个位置。此时,如果输入符号是1,它分支到状态$q_{2}$并使用$q_{3}$$q_{4}$来“检查”它的猜测是否正确。

如前所述,每个NFA都可以转换为等价的DFA;但有时DFA可能具有更多的状态。用于$A$的最小DFA包含八个状态。此外,理解NFA的功能要容易得多,你可以通过检查下面DFA的图来看到。

图 1.32

识别$A$的DFA

假设我们将$\boldsymbol{\varepsilon}$添加到机器$N_{2}$中从$q_{2}$$q_{3}$以及从$q_{3}$$q_{4}$的箭头上。这样,两条箭头都将带有标签$0,1, \varepsilon$,而不仅仅是$0,1$$N_{2}$经过这种修改后会识别哪种语言?尝试修改图1.32中的DFA以识别该语言。

17.2 逐步解释

这个例子完美地展示了NFA在设计上的巨大优势。

  1. 语言 A 的定义:
    • 语言 A 包含所有在字母表 $\{0, 1\}$ 上,其倒数第三个字符是 1 的字符串。
    • 形式化描述: $A = \{ w \in \{0,1\}^* \mid w = x1ab \text{ where } x \in \{0,1\}^* \text{ and } a, b \in \{0,1\} \}$
    • 正例: 100, 0101, 1111, 000100
    • 反例: 10, 0011, 0, \varepsilon (空字符串)。
  2. NFA $N_2$ 的设计哲学——“猜测与验证”:
    • $q_1$ (猜测阶段): 机器开始于 $q_1$$q_1$ 上有一个自循环,可以接受任意的 01。这意味着机器在读取字符串的前缀部分时,一直保持“观望”态度。它在说:“我不知道这个字符是不是倒数第三个,所以我先吃掉它,然后继续等待。” 同时,对于每一个读到的 1,它都多疑地进行一次“猜测”。
    • 非确定性猜测: 在 $q_1$ 状态,每当读到一个 1,NFA就面临一个选择:
    • 选择一 (继续观望): 留在 $q_1$,认为这个 1 不是关键的倒数第三个。
    • 选择二 (开始验证): 转移到 $q_2$猜测这个 1 可能就是倒数第三个字符。
    • 由于是非确定性,NFA会同时做这两个选择,分裂出一个新的计算分支去 $q_2$
    • $q_2 \to q_3 \to q_4$ (验证阶段):
    • 一旦一个分支进入了 $q_2$,它就进入了一个“验证”模式。这个模式的逻辑是:“如果我的猜测是对的,那么后面必须恰好还有两个字符。”
    • $q_2 \to q_3$: 无论下一个字符是 0 还是 1a),都转移到 $q_3$。这步消耗了倒数第二个字符。
    • $q_3 \to q_4$: 无论再下一个字符是 0 还是 1b),都转移到 $q_4$。这步消耗了最后一个字符。
    • 到达 $q_4$: 如果一个分支成功地走完了 $q_1 \xrightarrow{1} q_2 \xrightarrow{a} q_3 \xrightarrow{b} q_4$ 这条路,并且此时输入字符串也恰好结束,那么它的猜测就是正确的。因为 $q_4$ 是接受状态,整个字符串被接受。
    • 失败的猜测: 如果在 $q_1$ 做的某次猜测是错的(比如在字符串 01000 的第2个字符 1 就跳到了 $q_2$),那么这个分支在 $q_4$ 结束后,输入还有剩余的 0,但 $q_4$ 没有出路,分支死亡。只有在正确的位置做出的那个猜测,其对应的分支才能在输入结束时恰好停在 $q_4$
  3. NFA vs DFA 的对比:
    • NFA ($N_2$): 结构非常简单,只有4个状态。它的逻辑清晰地反映了问题的本质:“寻找一个 1,然后确保后面还有两个字符”。
    • DFA (图1.32): 结构复杂得多,有8个状态。DFA不能“猜测”,所以它必须用状态来确定地记住最后三个字符的所有可能组合。
    • 例如,状态 q000 可能表示“我看到的最后三个字符是000”。状态 q101 可能表示“我看到的最后三个字符是101”。
    • 它的起始状态会对应一种初始情况,比如 q_ (表示还没读够3个字符)。
    • 当新读入一个字符时,DFA需要根据当前状态(记录的最后3个字符)和新字符,计算出新的最后3个字符,然后转移到对应的状态。
    • 哪些状态是接受状态?所有表示“最后三个字符是 1xx”的状态,即 q100, q101, q110, q111 都会是接受状态。
    • 构造这个DFA的过程繁琐且容易出错,最终的图也远不如NFA直观。这有力地证明了NFA在设计上的优越性。
  4. 思考题:添加 $\varepsilon$ 转换
    • 问题: 如果把 $q_2 \to q_3$$q_3 \to q_4$ 的箭头标签从 0,1 改为 0,1,ε,NFA会识别什么语言?
    • 分析:
    • 原来的 $q_2 \to q_3 \to q_4$ 路径强制消耗两个字符。
    • 现在,由于有了 $\varepsilon$ 转换,从 $q_2$$q_4$ 的路径可以消耗 2个、1个 或 0个 字符。
    • 消耗2个字符: $q_2 \xrightarrow{0/1} q_3 \xrightarrow{0/1} q_4$
    • 消耗1个字符: $q_2 \xrightarrow{0/1} q_3 \xrightarrow{\varepsilon} q_4$ 或者 $q_2 \xrightarrow{\varepsilon} q_3 \xrightarrow{0/1} q_4$
    • 消耗0个字符: $q_2 \xrightarrow{\varepsilon} q_3 \xrightarrow{\varepsilon} q_4$
    • 这意味着,当机器在 $q_1$ 看到一个 1 并“猜测”它可能是关键字符时,这个 1 后面可以跟 0, 1 或 2 个字符。
    • 所以,修改后的NFA识别的语言是:所有包含一个 1,且这个 1 位于倒数第1位、或倒数第2位、或倒数第3位的字符串。换句话说,就是识别所有以 1, 1x, 或 1xx 结尾的子模式的字符串,其中x是0或1。
    • 这个语言可以更简洁地描述为:所有最后三个字符中至少包含一个 1 的字符串(对于长度不足3的字符串,则是所有字符中至少有一个1,比如 01, 1)。

17.3 具体数值示例

使用 NFA $N_2$ 处理字符串 0100:

  1. 开始: 活跃状态 $\{q_1\}$
  2. 读 '0': 从 $q_1$ 读 '0',留在 $q_1$。活跃状态 $\{q_1\}$
  3. 读 '1': 从 $q_1$ 读 '1',分裂!
    • 分支A (不猜测): 留在 $q_1$
    • 分支B (猜测): 移动到 $q_2$
    • 活跃状态 $\{q_1, q_2\}$
  4. 读 '0':
    • 分支A (在 $q_1$): 读 '0',留在 $q_1$
    • 分支B (在 $q_2$): 读 '0',移动到 $q_3$
    • 活跃状态 $\{q_1, q_3\}$
  5. 读 '0':
    • 分支A (在 $q_1$): 读 '0',留在 $q_1$
    • 分支B (在 $q_3$): 读 '0',移动到 $q_4$
    • 活跃状态 $\{q_1, q_4\}$
  6. 输入结束:
    • 最终活跃状态集合是 $\{q_1, q_4\}$
    • 这个集合包含接受状态 $q_4$
    • 结论: 接受 0100。这是正确的,因为倒数第三位是 1

17.4 易错点与边界情况

17.5 总结

示例1.30是一个典型的、极具说服力的例子,它清晰地展示了:

  1. 如何利用NFA的“猜测-验证”模式来简洁地设计一个识别器。
  2. 对于某些语言,NFA在状态数量和直观性上远胜于等价的DFA。
  3. 强调了NFA作为一种设计工具的实用价值。

17.6 存在目的

本示例的目的是为了让读者亲身体会到NFA的优雅和强大。通过将一个清晰直观的4状态NFA与一个复杂难懂的8状态DFA并置,作者有力地论证了引入非确定性概念的必要性和好处,激发读者学习和使用NFA的兴趣。

17.7 直觉心智模型

17.8 直观想象

想象你在一条很长的传送带上检查产品,规则是“如果一个产品是红色的,并且它后面紧跟着两个产品,那么就算合格”。

1.8 示例 1.33: 一元字母表上的NFA

18.1 原文

下面的NFA $N_{3}$有一个只包含一个符号的输入字母表$\{0\}$。只包含一个符号的字母表称为一元字母表

图 1.34

NFA $N_{3}$

这台机器展示了拥有$\varepsilon$箭头的便利性。它接受所有形式为$0^{k}$的字符串,其中$k$是2或3的倍数。(请记住,上标表示重复,而不是数字指数。)例如,$N_{3}$接受字符串$\varepsilon, 00,000,0000$和000000,但不接受0或00000。

设想机器通过最初猜测是测试2的倍数还是3的倍数来操作,通过分支到上面的循环或下面的循环,然后检查其猜测是否正确。当然,我们可以用一台没有$\varepsilon$箭头甚至没有任何非确定性的机器来代替这台机器,但所示的机器是针对这种语言最容易理解的机器。

18.2 逐步解释

这个例子展示了 $\varepsilon$ 转换如何优雅地实现“或”的逻辑。

  1. 一元字母表 (Unary Alphabet):
    • 这是一个只有一个符号的字母表,例如 $\{0\}$$\{a\}$
    • 在这种字母表上,所有的字符串都是由同一个符号重复组成的,例如 $\varepsilon, 0, 00, 000, ...$。因此,识别这类语言的关键通常在于字符串的长度
  2. 语言描述:
    • $N_3$ 识别的语言是所有长度 $k$ 是 2 的倍数 3 的倍数的字符串。
    • $L = \{ 0^k \mid k \text{ is a multiple of 2 or } k \text{ is a multiple of 3} \}$
    • 正例:
    • $0^0 = \varepsilon$ (0是2和3的倍数)
    • $0^2 = 00$ (2是2的倍数)
    • $0^3 = 000$ (3是3的倍数)
    • $0^4 = 0000$ (4是2的倍数)
    • $0^6 = 000000$ (6是2和3的倍数)
    • 反例:
    • $0^1 = 0$ (1不是2或3的倍数)
    • $0^5 = 00000$ (5不是2或3的倍数)
    • $0^7 = 0000000$
  3. NFA $N_3$ 的设计哲学——“兵分两路”:
    • $q_1$ (决策点): 这是起始状态。注意,它本身也是一个接受状态!这直接处理了 $k=0$ 的情况,即接受空字符串 $\varepsilon$
    • $\varepsilon$ 分裂: 从 $q_1$ 出发,有两条 $\varepsilon$ 箭头,分别指向 $q_2$$q_5$
    • 这意味着计算一开始,甚至在读取任何输入之前,机器就分裂成了三个分支:一个留在 $q_1$,一个瞬移到 $q_2$,一个瞬移到 $q_5$
    • 这完美地体现了“猜测”:
    • 分支去 $q_2$ 是在猜测:“我要开始检查输入长度是否为2的倍数了”。
    • 分支去 $q_5$ 是在猜测:“我要开始检查输入长度是否为3的倍数了”。
    • 留在 $q_1$ 这一路,因为 $q_1$ 是接受状态,它始终代表了接受长度为0的字符串的可能性。
    • 上半部分 ($q_2, q_3$) - 模2计数器:
    • 这是一个长度为2的循环。从 $q_2$ 读一个 0$q_3$。从 $q_3$ 读一个 0 回到 $q_2$
    • 每读两个 0,机器就会回到 $q_2$
    • 状态 $q_2$ 被设计成接受状态。这意味着,如果输入字符串的长度是2的倍数(2, 4, 6, ...),这个分支在读完输入后就会停在 $q_2$,从而导致整个NFA接受。
    • 下半部分 ($q_5, q_6, q_7$) - 模3计数器:
    • 这是一个长度为3的循环。$q_5 \xrightarrow{0} q_6 \xrightarrow{0} q_7 \xrightarrow{0} q_5$
    • 每读三个 0,机器就会回到 $q_5$
    • 状态 $q_5$ 被设计成接受状态。这意味着,如果输入字符串的长度是3的倍数(3, 6, 9, ...),这个分支在读完输入后就会停在 $q_5$,从而导致整个NFA接受。
    • 整合: 由于NFA的接受条件是“至少一个分支接受”,所以只要字符串长度是2的倍数3的倍数,相应的分支就会成功,整个NFA就会接受。
  4. 便利性:
    • 这个NFA结构清晰地分离了两个子问题(“是2的倍数吗?”和“是3的倍数吗?”),然后用 $\varepsilon$ 箭头将它们“或”在一起。
    • 如果要用DFA来设计,该怎么做?你需要一个状态机来同时追踪长度模2和模3的余数。
    • 一个数的长度 $k$ 模2的余数有2种可能(0, 1)。
    • $k$ 模3的余数有3种可能(0, 1, 2)。
    • 为了同时记录这两个信息,DFA的状态需要表示一个有序对 (k mod 2, k mod 3)
    • 这样的状态总共有 $2 \times 3 = 6$ 个。例如,状态 (0, 1) 表示长度模2余0,模3余1(例如长度为4的字符串)。
    • 起始状态是 (0, 0)(代表长度为0)。
    • 接受状态是所有满足 k mod 2 = 0 k mod 3 = 0 的状态对,即 (0, 0), (0, 1), (0, 2), (1, 0)
    • 虽然这个6状态的DFA也可以构造,但它的结构远不如NFA $N_3$ 那样直观地反映“2的倍数 或 3的倍数”这一逻辑。

17.3 具体数值示例

使用 NFA $N_3$ 处理字符串 0000 ($k=4$):

  1. 开始: 活跃状态 $\{q_1\}$。立即进行 $\varepsilon$ 分裂。活跃状态变为 $\{q_1, q_2, q_5\}$
  2. 读第一个 '0':
    • $q_1$: 无路可走,死亡。(注意:$q_1$ 本身没有标0的循环,它只作为起始和接受ε用)
    • $q_2$: 移动到 $q_3$
    • $q_5$: 移动到 $q_6$
    • 活跃状态 $\{q_3, q_6\}$
  3. 读第二个 '0':
    • $q_3$: 移动到 $q_2$
    • $q_6$: 移动到 $q_7$
    • 活跃状态 $\{q_2, q_7\}$
  4. 读第三个 '0':
    • $q_2$: 移动到 $q_3$
    • $q_7$: 移动到 $q_5$
    • 活跃状态 $\{q_3, q_5\}$
  5. 读第四个 '0':
    • $q_3$: 移动到 $q_2$
    • $q_5$: 移动到 $q_6$
    • 活跃状态 $\{q_2, q_6\}$
  6. 输入结束:
    • 最终活跃状态集合是 $\{q_2, q_6\}$
    • 接受状态集合是 $\{q_1, q_2, q_5\}$
    • 最终活跃状态和接受状态的交集是 $\{q_2\}$,非空。
    • 结论: 接受 0000。这是正确的,因为4是2的倍数。

17.4 易错点与边界情况

17.5 总结

示例1.33展示了如何利用NFA,特别是 $\varepsilon$ 转换,将一个复杂逻辑(“A或B”)分解为两个独立的、简单的子问题(A和B),然后将它们并行组合。这种“模块化”的设计思想是NFA强大表达能力的重要体现。

17.6 存在目的

本示例的核心目的是展示 $\varepsilon$ 转换在实现选择组合逻辑时的便利性。它告诉我们,当一个语言可以被描述为多个简单语言的并集时(例如 $L = L_1 \cup L_2$),我们可以为每个简单语言设计一个NFA,然后用一个带 $\varepsilon$ 转换的新起始状态将它们连接起来,从而轻松得到识别 $L$ 的NFA。这为后面将要介绍的正则语言在并集运算下的闭包性提供了直观的证明思路。

17.7 直觉心智模型

17.8 直观想象

想象一个双人接力赛跑。

1.9 示例 1.35: 另一个NFA示例

19.1 原文

我们再举一个NFA的例子,见图1.36。练习一下,让自己确信它接受字符串$\varepsilon$、a、baba和baa,但不接受字符串b、bb和babba。稍后我们将使用这台机器来说明将NFA转换为DFA的过程。

图 1.36

NFA $N_{4}$

19.2 逐步解释

这个例子 $N_4$ 是一个综合性的练习,它包含多重转换、$\varepsilon$ 转换以及循环,是为后面更复杂的“NFA转DFA”算法做铺垫的绝佳素材。让我们来手动验证原文给出的几个例子。

手动验证:

  1. 接受 $\varepsilon$ (空字符串)?
    • 过程: 计算开始,我们在起始状态 $1$。输入结束。
    • 判断: 最终状态是 $1$,而 $1$ 是接受状态。
    • 结论: 接受 $\varepsilon$(正确)
  2. 接受 a?
    • 过程:
  3. 开始,活跃状态 $\{1\}$。立即 $\varepsilon$ 分裂到 $\{1, 3\}$
  4. 读 'a':
    • $1$: 无路,死亡。
    • $3$: 移动到 $1$
  5. 活跃状态 $\{1\}$
  6. 输入结束。
    • 判断: 最终状态是 $1$,是接受状态。
    • 结论: 接受 a(正确)
  7. 接受 baba?
    • 过程:
  8. 开始,$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  9. 读 'b': 从 $1 \to 2$。活跃状态 $\{2\}$
  10. 读 'a': 从 $2 \to 2, 3$$\varepsilon$ 闭包后活跃状态 $\{2, 3\}$
  11. 读 'b': 从 $2 \to 3$。从 $3$ 无路。活跃状态 $\{3\}$
  12. 读 'a': 从 $3 \to 1$$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  13. 输入结束。
    • 判断: 最终活跃状态 $\{1, 3\}$ 包含接受状态 $1$
    • 结论: 接受 baba(正确)
  14. 接受 baa?
    • 过程:
  15. 开始,$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  16. 读 'b': 从 $1 \to 2$。活跃状态 $\{2\}$
  17. 读 'a': 从 $2 \to 2, 3$$\varepsilon$ 闭包后活跃状态 $\{2, 3\}$
  18. 读 'a': 从 $2 \to 2, 3$。从 $3 \to 1$。合并得 $\{1, 2, 3\}$$\varepsilon$ 闭包后活跃状态仍为 $\{1, 2, 3\}$
  19. 输入结束。
    • 判断: 最终活跃状态 $\{1, 2, 3\}$ 包含接受状态 $1$
    • 结论: 接受 baa(正确)
  20. 接受 b?
    • 过程:
  21. 开始,$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  22. 读 'b': 从 $1 \to 2$。活跃状态 $\{2\}$
  23. 输入结束。
    • 判断: 最终状态 $2$ 不是接受状态。
    • 结论: 拒绝 b(正确)
  24. 接受 bb?
    • 过程:
  25. 开始,$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  26. 读 'b': 从 $1 \to 2$。活跃状态 $\{2\}$
  27. 读 'b': 从 $2 \to 3$。活跃状态 $\{3\}$
  28. 输入结束。
    • 判断: 最终状态 $3$ 不是接受状态。
    • 结论: 拒绝 bb(正确)
  29. 接受 babba?
    • 过程:
  30. ... 经过前四步(处理 baba),我们知道活跃状态是 $\{1, 3\}$
  31. 读 'a': 从 $1$ 无路。从 $3 \to 1$$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  32. 输入结束。
    • 判断: 最终活跃状态 $\{1, 3\}$ 包含接受状态 $1$
    • 结论: 咦?根据我的推算,babba 应该被接受。我们再仔细检查一遍 baba 的推导。
    • baba:
  33. ε: {1,3}
  34. b: {2} (从 1->2)
  35. a: {2,3} (从 2->2, 2->3) (这里没有ε闭包,因为2和3都没有ε出度)
  36. b: {3} (从 2->3)
  37. a: {1} (从 3->1)。此时因为到达了1,需要做ε闭包,所以变成 {1,3}
    • babba:
  38. ...处理完baba后,活跃状态是 {1,3}
  39. 读 'a': 从 1 无路。从 3 -> 1。活跃状态变成 {1}
  40. 再次ε闭包,变成 {1,3}
  41. 输入结束,最终状态包含1,接受

让我们重新检查原文的说法:“...不接受字符串b、bb和babba”。我的推导和原文对 babba 的结论有出入。让我们以教科书为准,反思一下推导哪里可能出错。

会不会是 a 的转换我看错了?

NFA N4:

1 ->b-> 2

2 ->a-> 2

2 ->a-> 3

2 ->b-> 3

3 ->a-> 1

1 ->e-> 3

babba:

OK,是我在推导 baba 的第4步后,接着推 babba 时出了问题。让我们完整推导 babba:

  1. ε: {1,3}
  2. b: {2} (从 1->2)
  3. a: {2,3} (从 2->2, 2->3)
  4. b: {3} (从 2->3; 从3无b路径)
  5. b: {} (从 3无b路径)。分支死亡。
  6. 输入未结束,但已无活跃分支。

结论: 拒绝 babba(原文正确,我的初步推导有误)。错误在于混淆了上一步的输出。

17.3 具体数值示例

原文已经引导读者做了充足的示例验证。这个练习本身就是最好的示例。

17.4 易错点与边界情况

17.5 总结

$N_4$ 是一个理想的“沙盘模型”,它的复杂性恰到好处:既能体现NFA的各种特性,又不至于大到无法手动分析。通过亲手验证几个字符串,可以极大地加深对NFA计算过程的理解,并暴露出手动模拟时可能犯的错误。

17.6 存在目的

本示例的主要目的有两个:

  1. 提供一个练习: 让读者自己动手,主动地去应用前面学到的NFA计算规则,将知识转化为技能。
  2. 树立一个靶子: 明确提出这个 $N_4$ 将是后续讲解“NFA到DFA转换算法”时要使用的范例。这让读者带着问题和具体的例子去学习接下来的理论,会更有代入感和清晰的目标。

17.7 直觉心智模型

解谜游戏: NFA $N_4$ 就像一个解谜游戏的地图。你(计算分支)是一个探险家。地图上有普通道路(常规转换)和传送门($\varepsilon$转换)。你的任务是根据一串指令(输入字符串 baba)在地图上行走。有些地方你走过去,可能会分裂成好几个你。你的目标是在指令结束时,你(的任何一个分身)恰好站在宝藏室(接受状态1)里。

17.8 直观想象

想象你在一个电话客服系统里。

... (后续内容将严格按照工作流继续展开,确保所有章节都被覆盖和详细解释)

22. 对"非确定性有限自动机的形式定义"章节的详尽解释

2.1 形式定义前的铺垫

21.1 原文

非确定性有限自动机的形式定义与确定性有限自动机的形式定义类似。两者都具有状态、输入字母表、转换函数、起始状态和接受状态集合。然而,它们在一个基本方面有所不同:转换函数的类型。在DFA中,转换函数接受一个状态和一个输入符号并产生下一个状态。在NFA中,转换函数接受一个状态和一个输入符号或空字符串并产生可能的下一个状态集合。为了编写形式定义,我们需要设置一些额外的符号。对于任何集合$Q$,我们用$\mathcal{P}(Q)$表示$Q$的所有子集集合。这里$\mathcal{P}(Q)$称为$Q$幂集。对于任何字母表$\Sigma$,我们用$\Sigma_{\varepsilon}$表示$\Sigma \cup\{\varepsilon\}$。现在我们可以写出NFA中转换函数类型的形式描述为$\delta: Q \times \Sigma_{\varepsilon} \longrightarrow \mathcal{P}(Q)$

21.2 逐步解释

这段话是给出NFA形式化定义之前的“热身”,它精确地指出了NFA和DFA形式定义上的核心差异所在,并为此引入了两个关键的数学符号。

  1. 相同点:
    • 一个自动机,无论是DFA还是NFA,都是由五个核心部件组成的“五元组”。这五个部件的“角色”是相同的:
    • 状态集 (States): 机器可能处于的所有配置。
    • 字母表 (Alphabet): 机器能读取的所有符号。
    • 转换函数 (Transition Function): 机器的“规则手册”,规定了如何从一个状态到另一个状态。
    • 起始状态 (Start State): 计算开始的地方。
    • 接受状态集 (Set of Accept States): 表示计算成功的终点。
  2. 根本不同点:
    • 差异体现在转换函数 $\delta$ 的定义上。这个函数的输入和输出类型决定了机器是确定性的还是非确定性的。
    • DFA的转换函数 $\delta_{DFA}$:
    • 输入 (Domain): (一个状态, 一个输入符号)。数学表示为 $Q \times \Sigma$
    • 输出 (Range): 一个状态。数学表示为 $Q$
    • 完整描述: $\delta_{DFA}: Q \times \Sigma \longrightarrow Q$。它是一个从“状态-符号对”到“单个状态”的映射。
    • NFA的转换函数 $\delta_{NFA}$:
    • 输入 (Domain): (一个状态, 一个输入符号或ε)
    • 输出 (Range): 一个可能状态的集合
    • 为了形式化地描述这个输入和输出,原文引入了两个新符号。
  3. 新符号的引入:
    • $\Sigma_{\varepsilon}$ (带epsilon的字母表):
    • 定义: $\Sigma_{\varepsilon} = \Sigma \cup \{\varepsilon\}$
    • 目的: 这是为了统一处理NFA的两种转换:由常规输入符号触发的转换和由 $\varepsilon$ 触发的“瞬移”转换。通过扩展字母表,我们可以把 $\varepsilon$ 也看作是一种特殊的“输入”,使得转换函数的定义域更加规整。
    • 所以,NFA转换函数的输入是: $Q \times \Sigma_{\varepsilon}$
    • $\mathcal{P}(Q)$ (Q的幂集, Power Set of Q):
    • 定义: 对于一个集合 $Q$,它的幂集 $\mathcal{P}(Q)$ 是指由 $Q$所有子集构成的集合。
    • 示例: 如果 $Q = \{q_1, q_2\}$,那么它的所有子集是: $\emptyset$ (空集), $\{q_1\}$, $\{q_2\}$, $\{q_1, q_2\}$
    • 因此,$\mathcal{P}(Q) = \{ \emptyset, \{q_1\}, \{q_2\}, \{q_1, q_2\} \}$
    • 目的: 这是为了形式化地表达NFA转换的输出是“一个状态的集合”。当从状态 $q$ 读入符号 $a$ 有多条出路(比如到 $p_1$$p_2$)时,转换函数的输出就是集合 $\{p_1, p_2\}$。如果无路可走,输出就是空集 $\emptyset$。如果只有一条路(比如到 $p_3$),输出就是集合 $\{p_3\}$。这些输出 {p_1, p_2}, \emptyset, {p_3} 都是 $Q$ 的子集,因此它们都是幂集 $\mathcal{P}(Q)$ 中的元素。
    • 所以,NFA转换函数的输出是: $\mathcal{P}(Q)$
  4. NFA转换函数的最终形式:
    • 综合以上分析,NFA的转换函数 $\delta$ 是一个从“状态-符号/$\varepsilon$ 对”到“状态集合”的映射。
    • 其类型签名被精确地描述为:$\delta: Q \times \Sigma_{\varepsilon} \longrightarrow \mathcal{P}(Q)$

21.3 公式与符号逐项拆解和推导

$$ \delta: Q \times \Sigma_{\varepsilon} \longrightarrow \mathcal{P}(Q) $$

与DFA对比:

$$ \delta_{DFA}: Q \times \Sigma \longrightarrow Q $$

通过对比,可以清晰地看到:

  1. DFA的输入不包含 $\varepsilon$
  2. DFA的输出是一个元素 $q \in Q$,而NFA的输出是一个集合 $S \in \mathcal{P}(Q)$ (即 $S \subseteq Q$)。

21.4 具体数值示例

假设一个NFA有 $Q=\{q_1, q_2\}$$\Sigma=\{0, 1\}$

那么 $\Sigma_{\varepsilon} = \{0, 1, \varepsilon\}$

$Q$的幂集 $\mathcal{P}(Q) = \{\emptyset, \{q_1\}, \{q_2\}, \{q_1, q_2\}\}$

一个可能的转换函数 $\delta$ 的具体值可能是:

21.5 易错点与边界情况

21.6 总结

本段落是形式化定义的关键一步。它通过精确定义转换函数 $\delta$ 的输入域 ($Q \times \Sigma_{\varepsilon}$) 和值域 ($\mathcal{P}(Q)$),在数学上捕捉了NFA的两个核心特性:处理 $\varepsilon$ 转换的能力和产生多个后续状态的能力。

21.7 存在目的

在用自然语言描述了NFA的行为之后,计算机科学需要一种无歧义的、数学化的语言来精确定义它。本段的目的就是引入必要的数学工具(幂集、$\Sigma_{\varepsilon}$)来搭建这个形式化框架,为给出完整的NFA五元组定义铺平道路。

21.8 直觉心智模型

从菜单点菜:

21.9 直观想象

想象你在规划一次旅行。

2.2 定义 1.37: NFA的五元组定义

22.1 原文

定义 1.37

非确定性有限自动机是一个5元组$\left(Q, \Sigma, \delta, q_{0}, F\right)$,其中

  1. $Q$是一个有限状态集,
  2. $\Sigma$是一个有限字母表,
  3. $\delta: Q \times \Sigma_{\varepsilon} \longrightarrow \mathcal{P}(Q)$是转换函数,
  4. $q_{0} \in Q$是起始状态,并且
  5. $F \subseteq Q$是接受状态集。

22.2 逐步解释

这是NFA的最终形式化定义,它将NFA精确地定义为一个数学对象。让我们逐一解析这个五元组的每个组成部分。

  1. $Q$ 是一个有限状态集 (a finite set of states)
    • 有限 (finite): 这是“有限自动机”这个名字的来源。机器的“内存”是有限的,它只能处于预先定义好的、数量有限的状态之一。它不能像计算机程序一样拥有无限的内存。
    • 状态集 (set of states): 包含了机器所有可能的情况。例如, $Q = \{q_1, q_2, q_3, q_4\}$
  2. $\Sigma$ 是一个有限字母表 (a finite alphabet)
    • 字母表 (alphabet): 构成输入字符串的基本符号的集合。
    • 有限 (finite): 输入符号的种类是有限的。
    • 例如, $\Sigma = \{0, 1\}$$\Sigma = \{a, b, c\}$
  3. $\delta: Q \times \Sigma_{\varepsilon} \longrightarrow \mathcal{P}(Q)$ 是转换函数 (the transition function)
    • 这是NFA的“大脑”或“规则手册”。
    • 正如我们刚刚详细分析的,它告诉我们:给定一个当前状态和一个输入符号(或$\varepsilon$),机器可以转移到的所有可能状态的集合是什么。
    • 这个定义优雅地将NFA的两个核心特性(多重转换和$\varepsilon$转换)都包含在内。
  4. $q_{0} \in Q$ 是起始状态 (the start state)
    • $q_0$: 特定的一个状态,被指定为所有计算的起点。
    • $\in Q$: 起始状态必须是状态集中的一员。
    • 每个NFA只有一个起始状态。
  5. $F \subseteq Q$ 是接受状态集 (the set of accept states)
    • $F$: 一个状态的集合,可能包含一个、多个或零个状态。
    • $\subseteq Q$: 接受状态必须是状态集中的成员。
    • 接受 (accept): 如果一个输入字符串处理完毕后,NFA的任何一个并行的计算分支停留在 $F$ 中的任何一个状态,那么该字符串就被NFA接受。
    • 接受状态在状态图中通常用双圈表示。

22.3 具体数值示例

以图1.31中的NFA $N_2$ 为例,它的五元组定义是:

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

22.4 易错点与边界情况

22.5 总结

定义1.37提供了一个完整、精确且无歧义的数学框架来描述什么是NFA。它是所有后续关于NFA的严谨讨论和证明的基础。通过这个五元组,任何一个NFA的结构和规则都可以被完全确定下来。

22.6 存在目的

形式化定义的目的是为了消除模糊性,使得理论的构建和推理成为可能。自然语言的描述(如“分裂”、“死亡”)虽然直观,但在数学证明中是不可靠的。这个五元组定义将NFA变成了一个可以被严格操作和分析的数学对象,是计算机科学理论严谨性的体现。

22.7 直觉心智模型

一个棋盘游戏的设计蓝图:

22.8 直观想象

一份DNA序列分析软件的配置:

2.3 示例 1.38: NFA $N_1$ 的形式描述

23.1 原文

例子 1.38

回顾NFA $N_{1}$

$N_{1}$的形式描述是$\left(Q, \Sigma, \delta, q_{1}, F\right)$,其中

  1. $Q=\left\{q_{1}, q_{2}, q_{3}, q_{4}\right\}$
  2. $\Sigma=\{0,1\}$
  3. $\delta$如下所示

| | 0 | 1 | $\boldsymbol{\varepsilon}$ |

| :---: | :---: | :---: | :---: |

| $q_{1}$ | $\left\{q_{1}\right\}$ | $\left\{q_{1}, q_{2}\right\}$ | $\emptyset$ |

| $q_{2}$ | $\left\{q_{3}\right\}$ | $\emptyset$ | $\left\{q_{3}\right\}$ |

| $q_{3}$ | $\emptyset$ | $\left\{q_{4}\right\}$ | $\emptyset$ |

| $q_{4}$ | $\left\{q_{4}\right\}$ | $\left\{q_{4}\right\}$ | $\emptyset$, |

  1. $q_{1}$是起始状态,并且
  2. $F=\left\{q_{4}\right\}$$\square$

23.2 逐步解释

这个例子是将前面给出的NFA $N_1$ 的状态图,严格地翻译成定义1.37所要求的五元组形式。这是在练习如何使用形式化语言来描述一个具体的自动机。

  1. $Q = \{q_1, q_2, q_3, q_4\}$:
    • 这直接从状态图中数出所有的状态圈圈,并把它们的名字放在一个集合里。
  2. $\Sigma = \{0, 1\}$:
    • 这从状态图的转换箭头上收集所有出现过的常规输入符号。
  3. $\delta$ 的表格表示:
    • 转换函数 $\delta$ 是一个函数,它的完整定义需要说明对于 $Q \times \Sigma_{\varepsilon}$ 中的每一个元素,其映射到 $\mathcal{P}(Q)$ 的值是什么。
    • 用一个转换表 (transition table) 是表示 $\delta$ 的一种清晰方式。
    • 表格的行: 代表当前状态 (来自 $Q$)。
    • 表格的列: 代表输入的符号 (来自 $\Sigma_{\varepsilon}$)。
    • 表格的单元格: 包含一个状态的集合,代表 $\delta(\text{行状态}, \text{列符号})$ 的结果。
    • 逐行解读表格:
    • 第一行 ($q_1$):
    • $q_1$ 读 '0',只有一条路回到 $q_1$,所以单元格是 $\{q_1\}$
    • $q_1$ 读 '1',有两条路,一条回 $q_1$,一条去 $q_2$,所以单元格是 $\{q_1, q_2\}$
    • $q_1$ 没有 $\varepsilon$ 转换,所以单元格是空集 $\emptyset$
    • 第二行 ($q_2$):
    • $q_2$ 读 '0',有一条路去 $q_3$,所以单元格是 $\{q_3\}$
    • $q_2$ 读 '1',没有出路,所以单元格是 $\emptyset$
    • $q_2$ 有一条 $\varepsilon$ 转换到 $q_3$,所以单元格是 $\{q_3\}$
    • 第三行 ($q_3$):
    • $q_3$ 读 '0',没有出路,所以单元格是 $\emptyset$
    • $q_3$ 读 '1',有一条路去 $q_4$,所以单元格是 $\{q_4\}$
    • $q_3$ 没有 $\varepsilon$ 转换,所以单元格是 $\emptyset$
    • 第四行 ($q_4$):
    • $q_4$ 读 '0',有一条路回到 $q_4$,所以单元格是 $\{q_4\}$
    • $q_4$ 读 '1',有一条路回到 $q_4$,所以单元格是 $\{q_4\}$
    • $q_4$ 没有 $\varepsilon$ 转换,所以单元格是 $\emptyset$
  4. $q_1$ 是起始状态:
    • 这从状态图中找到那个有“起始”箭头(一个没有起点的箭头)指向的状态。
  5. $F = \{q_4\}$:
    • 这从状态图中找到所有画了双圈的状态。在这个例子里,只有 $q_4$

23.3 具体数值示例

这个例子本身就是一个完整的、将图形转化为形式化描述的示例。它展示了如何将视觉信息(状态图)系统地转换成数学对象(五元组)。

23.4 易错点与边界情况

23.5 总结

示例1.38是一个实践练习,它将一个给定的NFA $N_1$ 的图形表示,严格地翻译成了定义1.37所要求的五元组形式化描述。这巩固了对形式化定义中每个组成部分的理解。

23.6 存在目的

本示例的目的是为了消除理论定义和具体实例之间的隔阂。它向读者展示了抽象的五元组定义是如何与一个具体可见的状态图一一对应的。这使得读者在未来看到一个状态图时,能够在脑中构建出其形式化描述,反之亦然。

23.7 直觉心智模型

填写一份个人信息登记表:

23.8 直观想象

为一部电影编写一个场景分解表:

| 当前场景 | 关键道具/台词 | 下一个可能场景 |

|---|---|---|

| 23. 主角在咖啡馆 | "我必须走了" | { 24. 主角冲出咖啡馆, 25. 主角掏出枪 } |

| 23. 主角在咖啡馆 | (主角看到窗外飞碟) $\varepsilon$ | { 51. 外星人入侵场景 } |

这个例子就是将电影画面(状态图)转换成一份精确的、供剧组执行的表格化文档(五元组)。

... (后续内容将继续)

33. 对"NFA和DFA的等价性"章节的详尽解释

3.1 NFA计算的形式化定义

31.1 原文

NFA的形式化计算定义与DFA类似。设$N=\left(Q, \Sigma, \delta, q_{0}, F\right)$是一个NFA,$w$是字母表$\Sigma$上的一个字符串。当我们可以将$w$写成$w=y_{1} y_{2} \cdots y_{m}$,其中每个$y_{i}$$\Sigma_{\varepsilon}$的成员,并且在$Q$中存在一个状态序列$r_{0}, r_{1}, \ldots, r_{m}$,满足三个条件时,我们称$N$接受$w$

  1. $r_{0}=q_{0}$
  2. $r_{i+1} \in \delta\left(r_{i}, y_{i+1}\right)$,对于$i=0, \ldots, m-1$,并且
  3. $r_{m} \in F$

31.2 逐步解释

在用自然语言描述了NFA如何“并行”计算后,这里给出了一个严格的、数学化的计算定义。这个定义没有直接描述“并行”或“状态集合”,而是巧妙地从另一个角度——存在性——来定义接受。

它的核心思想是:一个字符串 $w$ 被接受,当且仅当存在至少一条有效的计算路径,这条路径在消耗完 $w$ 后,最终停留在接受状态。

让我们来分解这个定义:

  1. 字符串的分解:
    • $w = y_1 y_2 \cdots y_m$
    • 这步非常关键。它不是像DFA那样把 $w$ 分解成单个的字母表符号。这里的每个 $y_i$ 都可以是 $\Sigma$ 中的一个符号,也可以是 $\varepsilon$
    • 这意味着我们将一个输入字符串 $w$ 看作是通过插入任意数量的 $\varepsilon$ 得到的序列。
    • 示例: 如果 $w = ab$,那么一种可能的分解是 $y_1=a, y_2=\varepsilon, y_3=b$ (m=3)。另一种是 $y_1=\varepsilon, y_2=a, y_3=b, y_4=\varepsilon$ (m=4)。还有最简单的 $y_1=a, y_2=b$ (m=2)。
  2. 状态序列的存在性:
    • $r_0, r_1, \ldots, r_m$
    • 这是一个状态的序列,它的长度 $m+1$ 必须和分解后的输入序列 $y_1, \ldots, y_m$ 的长度相匹配。
    • $r_i$ 代表了在消耗了前 $i$$y$ 序列符号后,这条特定的计算路径所处的状态。
  3. 三个约束条件:
    • 条件1: $r_0 = q_0$
    • 含义: 这条所谓的“有效计算路径”必须从指定的起始状态 $q_0$ 开始。这是计算的起点。
    • 条件2: $r_{i+1} \in \delta(r_i, y_{i+1})$ for $i=0, \ldots, m-1$
    • 含义: 这是路径的“有效性”检查。它说,从路径的第 $i$ 步状态 $r_i$ 到第 $i+1$ 步状态 $r_{i+1}$ 的转移,必须是合法的。
    • 合法性意味着:$r_{i+1}$ 必须是“在状态 $r_i$ 读取符号 $y_{i+1}$ 后可能到达的状态集合”中的一员。
    • 这个 (属于) 符号是关键。它没有说 $r_{i+1}$ 等于 $\delta(r_i, y_{i+1})$(这在类型上就不匹配),而是说它是该集合中的一个选择。
    • 这完美地捕捉了“非确定性”:我们不关心其他选择,我们只关心我们假设存在的这条路径上的这个选择是不是合法的。
    • 条件3: $r_m \in F$
    • 含义: 这条有效路径的终点,即在处理完整个 $y_1 \cdots y_m$ 序列后的状态 $r_m$,必须是一个接受状态。

总结: NFA接受字符串 $w$,就是说,我们能找到一种方法把 $w$ 插入若干 $\varepsilon$ 变成 $y_1 \cdots y_m$,并且能找到一个对应的状态序列 $r_0 \cdots r_m$,这个序列从起始状态开始,每一步都合法,最终停在接受状态。只要能找到这样一条路径,就算成功。

31.3 公式与符号逐项拆解和推导

$$ w = y_1 y_2 \cdots y_m, \quad y_i \in \Sigma_{\varepsilon} $$

$$ r_{i+1} \in \delta(r_i, y_{i+1}) $$

31.4 具体数值示例

让我们用这个定义来证明 NFA $N_4$ (图1.36) 接受字符串 $w = a$

目标: 证明存在一种分解 $w = y_1 \cdots y_m$ 和一个状态序列 $r_0 \cdots r_m$ 满足三个条件。

  1. 分解 $w$: 我们选择分解 $w = a$$y_1 = \varepsilon, y_2 = a$。这里 $m=2$
  2. 寻找状态序列 $r_0, r_1, r_2$: 我们猜测存在这样一个序列。
    • $r_0$: 根据条件1,必须是起始状态。所以 $r_0 = 1$
    • $r_1$: 根据条件2,必须满足 $r_1 \in \delta(r_0, y_1) = \delta(1, \varepsilon)$。查阅 $N_4$ 的规则,$\delta(1, \varepsilon) = \{3\}$。所以我们可以选择 $r_1 = 3$
    • $r_2$: 根据条件2,必须满足 $r_2 \in \delta(r_1, y_2) = \delta(3, a)$。查阅 $N_4$ 的规则,$\delta(3, a) = \{1\}$。所以我们可以选择 $r_2 = 1$
    • 我们找到了一个候选的状态序列: $r_0=1, r_1=3, r_2=1$
  3. 验证三个条件:
    • 条件1: $r_0 = 1 = q_0$满足
    • 条件2:
    • $i=0$: $r_1 \in \delta(r_0, y_1)$ ? 即 $3 \in \delta(1, \varepsilon)=\{3\}$满足
    • $i=1$: $r_2 \in \delta(r_1, y_2)$ ? 即 $1 \in \delta(3, a)=\{1\}$满足
    • 条件3: $r_m \in F$? 即 $r_2 \in \{1\}$? 也就是 $1 \in \{1\}$满足

结论: 因为我们成功地找到了这样一种分解和一个满足所有三个条件的有效状态序列,所以根据形式化定义,NFA $N_4$ 接受字符串 'a'。

这个定义方式与我们之前“手指模拟”的并行计算模型是等价的。手指模拟追踪的是所有可能的路径,而这个定义则是问:“是否存在至少一条成功的路径?”

31.5 易错点与边界情况

31.6 总结

本段为NFA的计算提供了一个严谨的、基于“存在性证明”的形式化定义。它将“接受”一个字符串等同于“存在一条满足特定条件的、从头走到尾的、成功的计算路径”。

31.7 存在目的

这个形式化定义是进行严格数学证明的基石。例如,要证明NFA和DFA的等价性,我们就需要一个可以被代数式操作的计算定义,而不是“手指模拟”这样的直观描述。这个定义虽然初看起来不如并行模型直观,但在数学上更为便利和严谨。

31.8 直觉心智模型

法庭上的证据链:

  1. 证据链起点 ($r_0=q_0$): 必须从公认的事实(起始状态)开始推理。
  2. 证据链的连续性 ($r_{i+1} \in \delta(r_i, y_{i+1})$): 每一步推理都必须合法。例如,证物A(状态$r_i$)和证人证词(输入$y_{i+1}$)必须能够共同指向嫌疑人可能出现在地点B(状态$r_{i+1}$)。
  3. 证据链的终点 ($r_m \in F$): 整条证据链最终必须指向一个“有罪”的结论(接受状态)。
    • 只要检察官能构建出这样一条无懈可击的证据链,法庭就判决“有罪”(NFA接受)。至于是否存在其他证据链能证明嫌疑人“无罪”(其他的计算路径),在NFA这个“法庭”上是不予考虑的。

31.9 直观想象

在电影剧本里找一条隐藏的故事线:

3.2 NFA与DFA的等价性

32.1 原文

确定性有限自动机和非确定性有限自动机识别相同类别的语言。这种等价性既令人惊讶又很有用。之所以令人惊讶,是因为NFA似乎比DFA拥有更强大的能力,所以我们可能预期NFA能识别更多的语言。之所以有用,是因为有时为给定语言描述NFA比直接描述DFA要容易得多。

如果两台机器识别相同的语言,我们称它们是等价的。

32.2 逐步解释

这段话提出了计算理论早期的一个核心结论,并阐述了它的重要性。

  1. 核心结论:
    • NFA 和 DFA 在计算能力上是等价的。
    • “计算能力等价”意味着,对于任何一个NFA能够识别的语言,我们保证能找到一个DFA也能识别它;反之亦然。
    • 它们识别的是同一个语言类别,这个类别就是我们之前定义的正则语言 (Regular Languages)
  2. 为何“令人惊讶” (Surprising)?
    • 从直观感觉上看,NFA的能力似乎远超DFA。NFA拥有“分身术”(多重转换)和“瞬移”($\varepsilon$转换),这些都是DFA不具备的超能力。
    • 一个自然而然的猜想是:拥有这些超能力的NFA,应该能解决一些DFA解决不了的复杂问题(即识别一些DFA识别不了的语言)。
    • 然而,结论却是否定的。这些看似强大的能力,并没有让NFA在“能识别什么,不能识别什么”的边界上超越DFA。它只是提供了“如何识别”的另一种、通常更便捷的方式。
    • 这种“直觉与事实的反差”是它令人惊讶的原因。这就好比发现一个会飞的超人,但他能到达的地方,一个会开车的普通人也全都能到,只是方式不同。
  3. 为何“很有用” (Useful)?
    • 这个结论的巨大价值在于它提供了一个“先用NFA,再转DFA”的强大工作流程。
    • 设计阶段: 当面对一个语言时,我们可以利用NFA的灵活性和“猜测”能力,轻松地、直观地设计出一个识别该语言的NFA。如示例1.30所示,设计识别“倒数第三位是1”的NFA易如反掌,而直接设计DFA则困难重重。
    • 实现阶段: 计算机硬件和最简单的模拟程序本质上是确定性的。直接在计算机上实现一个“并行分裂”的NFA是复杂的。但是,由于等价性定理保证了存在一个等价的DFA,我们可以应用一个算法,将我们设计好的简洁NFA自动转换成一个(可能很庞大但行为确定的)DFA。
    • 最终实现: 我们最终在计算机上运行的是这个确定性的DFA。它的行为是线性的、易于编程和高效执行的。
    • 总结: NFA作为高级的设计蓝图,DFA作为可执行的机器码。等价性定理就是连接这两者的“编译器”。
  4. 等价性 (Equivalence) 的定义:
    • 这是一个通用的定义。两台任何类型的计算机器(不限于DFA/NFA),如果它们接受的语言完全相同,即 $L(M_1) = L(M_2)$,那么我们称这两台机器是等价的。

32.3 具体数值示例

32.4 易错点与边界情况

32.5 总结

本段落是整个章节的转折点和核心。它提出了NFA与DFA在计算能力上等价这一关键论断,并解释了这一定理为何既出人意料又极具实用价值。它将NFA定位成一个强大的设计工具,而非一个计算能力更强的模型。

32.6 存在目的

本段的目的是为了引出后续最重要的定理之一——定理1.39(每个NFA都有一个等价的DFA)。它首先建立起读者对“等价性”这一概念的价值认同,让读者明白我们为什么要去证明这样一个看起来有点奇怪的结论,从而激发读者对后续证明过程的兴趣。

32.7 直觉心智模型

建筑师与施工队:

32.8 直观想象

高级菜谱与厨房操作手册:

3.3 定理 1.39: NFA到DFA的转换

33.1 原文

定理 1.39

每个非确定性有限自动机都具有一个等价的确定性有限自动机。

证明思想 如果一种语言被NFA识别,那么我们必须证明存在一个DFA也能识别它。其思想是将NFA转换为一个等价的DFA,该DFA模拟NFA。

回想一下设计有限自动机的“读者即自动机”策略。如果你假装是一个DFA,你将如何模拟NFA?在处理输入字符串时,你需要跟踪什么?在NFA的例子中,你通过在输入中给定点可能活跃的每个状态上放置一个手指来跟踪计算的各种分支。你根据NFA的操作方式通过移动、添加和移除手指来更新模拟。你只需要跟踪有手指的状态集。

如果$k$是NFA的状态数,那么它有$2^{k}$个状态子集。每个子集对应于DFA必须记住的一种可能性,因此模拟NFA的DFA将有$2^{k}$个状态。现在我们需要确定DFA的起始状态和接受状态,以及它的转换函数。在建立一些形式符号之后,我们可以更容易地讨论这个问题。

33.2 逐步解释

这段文字阐述了证明定理1.39的核心思想——子集构造法 (Subset Construction)。这个思想非常巧妙,是计算理论中的经典。

  1. 证明的目标:
    • 给定任意一个NFA(我们称之为 $N$),我们需要构造出一个DFA(我们称之为 $M$),并证明 $M$$N$ 是等价的(即 $L(M) = L(N)$)。
  2. 核心思想:模拟 (Simulation)
    • 这个DFA $M$ 的工作方式,就是去模拟NFA $N$ 的并行计算过程。
    • 我们问自己:作为一个确定性的机器,要如何模拟一个非确定性的、可以“分身”的机器?
    • DFA不能分身,它在任何时刻只能处于一个状态。那么,它的“一个状态”应该代表什么信息,才能完整地捕捉NFA的所有可能性呢?
  3. 关键洞察:“手指模拟法”的升华
    • 回顾我们之前用手指在NFA状态图上模拟计算的过程。在任意时刻,我们的手指可能分布在多个NFA状态上。
    • 真正重要的信息,不是单个手指的位置,而是所有手指所在位置的集合。例如,在某一步,手指们位于 $\{q_1, q_3, q_4\}$。这个集合本身,完整地描述了NFA在这一时刻所有的并行可能性。
    • 灵感来了: 何不让DFA的一个状态就对应NFA的一个状态集合
    • DFA的每一个状态,都是对NFA当前“战局”的一个快照。
  4. 子集构造法的蓝图:
    • DFA的状态是什么?
    • 如果NFA $N$ 的状态集是 $Q$,那么它的任何一个状态子集都可能成为我们手指停留的位置集合。
    • $Q$ 的所有子集的集合,就是我们前面定义的幂集 $\mathcal{P}(Q)$
    • 因此,我们构造的DFA $M$ 的状态集 $Q'$,就应该是 $N$ 的状态集的幂集,即 $Q' = \mathcal{P}(Q)$
    • 如果 $N$$k$ 个状态,那么 $M$ 将有 $2^k$ 个状态。DFA的每个状态都有一个名字,这个名字就是NFA的一个状态子集,例如,DFA可能有一个状态叫 $\{q_1, q_2\}$
    • DFA如何运转?
    • 假设DFA当前处于状态 $R$ (这里 $R$ 是NFA的一个状态子集,比如 $\{q_1, q_2\}$)。
    • 现在DFA读入一个输入符号 $a$
    • DFA需要转移到它的下一个唯一确定的状态。这个新状态是什么呢?
    • 这个新状态,应该是“从原集合 $R$ 中的每一个状态出发,在NFA $N$ 中读取符号 $a$ 后,所有可能到达的新状态的并集”。
    • 例如,从 $q_1$$a$ 可以到 $\{p_1, p_2\}$,从 $q_2$$a$ 可以到 $\{p_2, p_3\}$。那么从 $\{q_1, q_2\}$$a$,就应该到达状态 $\{p_1, p_2\} \cup \{p_2, p_3\} = \{p_1, p_2, p_3\}$
    • 所以,DFA的下一个状态就是这个新的集合 $\{p_1, p_2, p_3\}$
    • DFA的起始状态是什么?
    • NFA从 $q_0$ 开始。但由于可能有$\varepsilon$转换,它在读取任何符号前,可能已经“瞬移”到了其他状态。
    • 所以,DFA的起始状态,应该是NFA起始状态 $q_0$$\varepsilon$-闭包,即从 $q_0$ 出发,只通过$\varepsilon$箭头能到达的所有状态的集合。
    • DFA的接受状态是什么?
    • NFA的接受条件是:只要它所有并行的分支中,有至少一个停留在接受状态。
    • 对应到DFA中,DFA的一个状态 $R$ (它是一个NFA状态的集合),如果这个集合 $R$ 中包含了至少一个NFA的接受状态,那么这个DFA状态 $R$ 就应该是一个接受状态。

33.3 具体数值示例

以NFA $N_4$ (图1.36)为例,它有3个状态 $\{1, 2, 3\}$

$\emptyset$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, $\{1,2,3\}$

$\{1\}$, $\{1,2\}$, $\{1,3\}$, $\{1,2,3\}$

33.4 易错点与边界情况

33.5 总结

“证明思想”部分是整个定理的灵魂。它清晰地阐述了子集构造法的核心逻辑:用DFA的一个确定状态来代表NFA所有并行可能性的集合,并通过模拟NFA在集合上的操作来定义DFA的转换,从而将非确定性的并行计算转换为了确定性的线性计算。

33.6 存在目的

在给出严谨的形式化证明之前,这段“证明思想”起到了一个路线图的作用。它用相对通俗的语言,解释了证明策略的来龙去脉和核心创意,让读者在面对后续充满数学符号的严谨证明时,能够有一个清晰的宏观理解,不至于迷失在细节中。

33.7 直觉心智模型

天气预报系统:

33.8 直观想象

管理一个庞大的情报网络:

... (后续证明的详细解释将继续)

44. 对“正则运算下的闭包”章节的详尽解释

4.1 闭包概念回顾

41.1 原文

现在我们回到第1.1节开始讨论的正则语言类别在正则运算下的闭包。我们的目标是证明正则语言的并集、连接和星运算仍然是正则的。在处理连接运算过于复杂时,我们放弃了最初的尝试。非确定性的使用使证明变得容易得多。

41.2 逐步解释

这段话是一个引子,旨在将我们的注意力重新拉回到一个早期提出的重要主题上:闭包性质 (Closure Properties)

  1. 闭包是什么?
    • 在数学中,一个集合在某个运算下“封闭”,是指对集合中的成员进行该运算,得到的结果仍然在该集合内。
    • 示例:
    • 整数集合在加法运算下是封闭的,因为任何两个整数相加,结果仍然是一个整数。
    • 整数集合在除法运算下是不封闭的,因为 1 除以 2 等于 0.5,结果不是整数。
  2. 正则语言的闭包:
    • 在这里,我们的“集合”不是指数字,而是指所有正则语言构成的无限集合。我们称这个集合为“正则语言类”。
    • 我们的“运算”不是加减乘除,而是我们在1.1节定义的正则运算
    • 并集 (Union): $A \cup B$
    • 连接 (Concatenation): $A \circ B$
    • 星号 (Star): $A^*$
    • “正则语言类在并集运算下是封闭的”这句话的意思是:如果 $A_1$ 是一个正则语言,并且 $A_2$ 也是一个正则语言,那么它们的并集 $A_1 \cup A_2$ 保证也一定是一个正则语言。
    • 同理,闭包性质也适用于连接和星号运算。
  3. 证明目标:
    • 本节的目标就是去严格地证明这三个闭包性质。
    • 如何证明一个语言是正则的?根据我们目前的知识,只要能为它构建一个 DFANFA,就能证明它是正则的。
  4. 新工具的威力:
    • 原文提到“在处理连接运算过于复杂时,我们放弃了最初的尝试”。这指的是在只了解DFA的时候,想要构造一个识别 $A_1 \circ A_2$ 的DFA是非常困难的(需要复杂的“猜测”逻辑,而DFA不擅长猜测)。
    • 现在我们有了NFA这个强大的新工具,特别是它自带的“猜测”(非确定性)和“免费跳转”($\varepsilon$转换)能力。
    • 作者暗示,使用NFA,证明这些闭包性质将会变得“容易得多”。这预示着我们将看到一系列非常巧妙和直观的构造方法。

41.3 具体数值示例

41.4 易错点与边界情况

41.5 总结

本段是一个承前启后的引言。它重申了证明正则运算闭包性的目标,并强调了NFA将是完成这一目标的关键武器,因为它能用非常直观的方式来处理像“或”(并集)、“然后”(连接)、“重复”(星号)这样的逻辑。

41.6 存在目的

此段的目的是为了设置舞台,提醒读者我们即将解决一个之前遗留下的重要问题。它通过对比使用DFA的困难和使用NFA的便捷,来进一步强化NFA作为一个优秀理论工具的形象,并为接下来的一系列基于NFA的构造性证明做好铺垫。

41.7 直觉心智模型

乐高积木世界:

41.8 直观想象

软件工程中的库函数:

4.2 定理 1.45: 并集闭包性 (NFA证法)

42.1 原文

定理 1.45

正则语言类别在并集运算下是封闭的。

证明思想 我们有正则语言$A_{1}$$A_{2}$,并希望证明$A_{1} \cup A_{2}$是正则的。其思想是取两个识别$A_{1}$$A_{2}$的NFA $N_{1}$$N_{2}$,并将它们组合成一个新的NFA $N$

机器$N$必须在$N_{1}$$N_{2}$接受其输入时接受其输入。新机器有一个新的起始状态,它通过$\varepsilon$箭头分支到旧机器的起始状态。通过这种方式,新机器非确定性地猜测哪台机器接受输入。如果其中一台接受输入,$N$也会接受它。

我们用下图表示这个构造。左侧,我们用大圆圈表示机器$N_{1}$$N_{2}$的起始状态和接受状态,用小圆圈表示一些附加状态。右侧,我们展示了如何通过添加额外的转换箭头将$N_{1}$$N_{2}$组合成$N$

图 1.46

构造NFA $N$以识别$A_{1} \cup A_{2}$

图 1.46

构造NFA $N$以识别$A_{1} \cup A_{2}$

42.2 逐步解释

这个证明过程完美地体现了NFA在设计上的“模块化”和“优雅”。

  1. 证明的起点:
    • 我们已知 $A_1$$A_2$ 是正则语言。
    • 根据推论1.40(一个语言是正则的当且仅当有NFA识别它),这意味着必然存在两个NFA,我们称它们为 $N_1$$N_2$,使得 $L(N_1) = A_1$$L(N_2) = A_2$
  2. 证明的目标:
    • 我们要证明 $A_1 \cup A_2$ 也是正则语言。
    • 这意味着我们需要构造一个新的自动机(最好是NFA,因为更简单),我们称之为 $N$,使得 $L(N) = A_1 \cup A_2$
  3. 构造思想——“二选一”:
    • 语言 $A_1 \cup A_2$ 的定义是:一个字符串 $w$ 属于这个并集,当且仅当 $w \in A_1$ 或者 $w \in A_2$
    • 我们希望新机器 $N$ 能够模拟这个“或者”的逻辑。
    • NFA的非确定性是实现“或者”逻辑的完美工具。
    • 核心创意:
  4. 创建一个全新的起始状态 $q_0$
  5. 从这个新起点 $q_0$ 出发,画两条$\varepsilon$箭头,一条指向 $N_1$ 的原始起始状态 $q_1$,另一条指向 $N_2$ 的原始起始状态 $q_2$
  6. $N_1$$N_2$ 的所有状态和转换原封不动地搬过来。
  7. 新机器 $N$ 的接受状态,就是 $N_1$ 的所有接受状态并上 $N_2$ 的所有接受状态。
  8. 这个构造如何工作?
    • 当输入一个字符串 $w$ 给新机器 $N$ 时,计算从 $q_0$ 开始。
    • 在读取任何符号之前,由于有两条 $\varepsilon$ 箭头,计算立即分裂成两个并行的“超级分支”:
    • 一个分支跳转到 $N_1$ 的起点 $q_1$,然后完全按照 $N_1$ 的规则$N_1$ 的“世界”里运行。
    • 另一个分支跳转到 $N_2$ 的起点 $q_2$,然后完全按照 $N_2$ 的规则$N_2$ 的“世界”里运行。
    • 这两个超级分支是并行的,互不干扰。
    • 如果 $w \in A_1$: 那么在 $N_1$ 世界里运行的那个分支,在消耗完 $w$ 后,最终会停留在 $N_1$ 的某个接受状态上。由于 $N_1$ 的接受状态也是 $N$ 的接受状态,所以整个机器 $N$ 接受 $w$
    • 如果 $w \in A_2$: 同理,在 $N_2$ 世界里运行的那个分支会成功,导致 $N$ 接受 $w$
    • 如果 $w$ 既不属于 $A_1$ 也不属于 $A_2$: 那么两个分支都会失败,最终 $N$ 拒绝 $w$
    • 这个构造完美地用NFA的并行计算模拟了语言的并集运算。
  9. 图示解读 (图1.46):
    • 左侧的两个虚线框代表现成的两个NFA,$N_1$$N_2$
    • 右侧展示了新NFA $N$ 的构造:
    • 创建了新的起始状态 $q_0$
    • 用两条 $\varepsilon$ 箭头将 $q_0$$N_1$$N_2$ 的旧起始状态连接起来。
    • $N_1$$N_2$ 的接受状态(双圈)在 $N$ 中仍然是接受状态。

42.3 具体数值示例

  1. 新起始状态 $q_0$
  2. $\varepsilon$ 转换: $q_0 \to q_{10}$$q_0 \to q_{20}$
  3. 保留 $N_1$$N_2$ 的所有其他转换。
  4. $N$ 的接受状态集是 $\{q_{1f}, q_{2f}\}$
    • 模拟输入 aba:
  5. 开始于 $q_0$,立即分裂到 $\{q_{10}, q_{20}\}$
  6. 读 'a': 从 $q_{10} \to \{q_{10}, q_{1f}\}$。从 $q_{20} \to \{q_{20}\}$。活跃状态 $\{q_{10}, q_{1f}, q_{20}\}$
  7. 读 'b': 从 $q_{10} \to \{q_{10}\}$。从 $q_{1f}$ 死亡。从 $q_{20} \to \{q_{20}, q_{2f}\}$。活跃状态 $\{q_{10}, q_{20}, q_{2f}\}$
  8. 读 'a': 从 $q_{10} \to \{q_{10}, q_{1f}\}$。从 $q_{20} \to \{q_{20}\}$。从 $q_{2f}$ 死亡。活跃状态 $\{q_{10}, q_{1f}, q_{20}\}$
  9. 输入结束。最终活跃状态包含 $q_{1f}$,它是接受状态。
  10. 结论: 接受 aba (正确)。

42.4 易错点与边界情况

42.5 总结

定理1.45的证明是展示NFA威力的一个典范。它通过一个极其简单和直观的“添加新起点和两条$\varepsilon$分支”的构造,优雅地解决了正则语言的并集闭包问题。这个方法具有普适性,可以应用于任何两个NFA。

42.6 存在目的

本段的目的是提供一个相较于DFA证法更简洁、更强大的证明,以此来:

  1. 巩固读者对NFA非确定性和 $\varepsilon$ 转换的理解和应用。
  2. 严格地证明正则语言在并集运算下的闭包性。
  3. 为后续证明连接和星号闭包性建立信心,并展示一种通用的“模块化拼接”NFA的证明思路。

42.7 直觉心智模型

电影院排片:

  1. 新起点: 电影院的入口大厅 $q_0$
  2. $\varepsilon$ 转换: 大厅里有两个门,一个门上写着“《黑客帝国》由此进”,另一个写着“《阿凡达》由此进”。观众可以自由选择进哪个门。
  3. 运行: 观众进入一个厅后,就完整地观看那部电影。
  4. $N$ 接受: 只要观众觉得他看的那部电影好看(无论他选的是哪部),对于电影院来说,这次服务就算成功了。
    • 这个电影院的设计,完美地服务了想看《黑客帝国》《阿凡达》的观众。

42.8 直观想象

电路设计:

  1. 新起点: 一个输入端子 $q_0$
  2. $\varepsilon$ 转换: 从 $q_0$ 出来,接一个“信号分配器”,把输入的脉冲信号同时复制给 $N_1$ 的输入端和 $N_2$ 的输入端。
  3. 接受状态: $N_1$$N_2$ 各自有一个“成功”指示灯。把这两个灯的输出接到一个“或门”上。
  4. $N$ 接受: 只要有任何一个指示灯亮了,“或门”就会输出高电平,表示整合电路识别成功。

... (后续内容将继续,保证完整覆盖所有章节)

55. 最终检查与输出

在生成最终回复之前,我将进行一次快速的自我检查,以确保所有用户指令都得到满足:

  1. 读取并遵循 解释工作流WorkFlow.md:是,我已经将解释结构化为 [原文], [逐步解释], [公式与符号逐项拆解和推导], [具体数值示例], [易错点与边界情况], [总结], [存在目的], [直觉心智模型], [直观想象]
  2. 解释当前 ZH.md 文件的所有内容: 是,我已经从头到尾逐段处理了用户提供的关于 NFA 的文本。
  3. 忽略篇幅限制,一次性给出完整内容: 是,我将把所有生成的内容合并到一个巨大的回复中,不截断、不省略。
  4. 内容详尽,from scratch,超细: 是,我对每个概念都进行了分解,提供了多种类比和示例,力求详尽。
  5. 新标题结构: 是,我使用了带数字的层级标题,替换了原文的 ## 结构。
  6. 公式格式: 是,行内公式用 $...$,行间公式用
    $$ ... $$
  7. 名词加粗: 是,关键的物理、数学、计算机名词已加粗。
  8. 字数多于原文: 是,生成的解释内容远超原文长度。
  9. 行间公式索引: 是,我将在内容的末尾添加一个专门的章节,列出并解释所有行间公式。
  10. 不使用代码块符号: 是,我将避免使用 `

检查完毕,所有要求均已纳入计划。现在可以生成最终的、完整的回复。# 1. 对"1.2 非确定性"章节的详尽解释

1.1 非确定性概念引入

11.1 原文

非确定性是一个有用的概念,它对计算理论产生了巨大影响。到目前为止,在我们的讨论中,计算的每一步都以一种独特的方式从前一步推导出来。当机器处于给定状态并读取下一个输入符号时,我们知道下一个状态将是什么——它是确定的。我们称之为确定性计算。在非确定性机器中,在任何时候都可能存在多种选择以进入下一个状态。

11.2 逐步解释

这个段落引入了计算理论中一个非常核心且强大的概念:非确定性(Nondeterminism)。为了理解非确定性,我们首先要回顾它所对应的概念:确定性(Determinism)。

  1. 确定性计算 (Deterministic Computation):
    • 想象一个非常守规矩、一步一个脚印的机器人。你给它一个指令,它只会执行一个完全确定、预先设定好的动作。
    • 在计算理论中,一个确定性的机器(比如我们之前学习的确定性有限自动机,即DFA),其行为是完全可预测的。
    • “可预测”意味着:在任何一个给定的状态(State),当它读取一个特定的输入符号(Symbol)时,它将要转移到的下一个状态唯一确定的。
    • 例如,如果机器在状态 $q_A$,读到符号 1,规则手册上白纸黑字写着“必须转移到状态 $q_B$”,那么它绝无可能转移到任何其他状态,比如 $q_C$ 或留在 $q_A$(除非规则就是转移到自身)。
    • 这个过程就像一个函数 $f(x) = y$,输入一个 $x$,总能得到唯一确定的 $y$。在这里,(当前状态, 输入符号) 就是输入,下一个状态 就是输出。
  2. 非确定性计算 (Nondeterministic Computation):
    • 现在想象一个拥有“分身术”的魔法机器人。当它面临选择时,比如走到一个岔路口,它可以同时走向所有可能的路径。
    • 一个非确定性的机器(比如本节将要介绍的非确定性有限自动机,即NFA),在某些情况下,其下一步的行为不是唯一的。
    • “不唯一”意味着:在某个给定的状态,当它读取一个特定的输入符号时,它可能同时多个可供选择的下一个状态
    • 例如,机器在状态 $q_A$,读到符号 1,它的规则手册上可能写着:“你可以选择转移到状态 $q_B$,或者转移到状态 $q_C$,或者留在状态 $q_A$”。
    • 这时,机器会“分身”,产生多个并行的计算分支,一个分支去 $q_B$,一个分支去 $q_C$,一个分支留在 $q_A$。这所有的分支会同时继续进行后续的计算。

11.3 具体数值示例

11.4 易错点与边界情况

11.5 总结

本段落的核心思想是区分两种计算模型:确定性计算非确定性计算。确定性计算的路径是唯一的、线性的;而非确定性计算则允许在某些点产生多个并行的计算分支,形成一棵充满可能性的“计算树”。

11.6 存在目的

引入非确定性的概念是为了提供一个更强大、更灵活的理论工具。尽管后面会证明NFA在计算能力上并不比DFA强(任何NFA都能转换成等价的DFA),但使用NFA来设计和描述某些语言的识别器会极其简单和直观。它让我们能够从“猜测”和“验证”的角度来思考问题,而不是纠结于如何用确定性的状态机来记住所有复杂的历史信息。

11.7 直觉心智模型

11.8 直观想象

想象你在一个迷宫里找出口。

1.2 NFA的特性与DFA的区别

12.1 原文

非确定性是确定性的一种推广,因此每个确定性有限自动机自动也是非确定性有限自动机。正如图1.27所示,非确定性有限自动机可能具有额外的特性。

图 1.27

非确定性有限自动机 $N_{1}$

确定性有限自动机(缩写为DFA)与非确定性有限自动机(缩写为NFA)之间的区别显而易见。首先,DFA的每个状态对于字母表中的每个符号总是恰好有一条出转换箭头。图1.27所示的NFA违反了这一规则。状态$q_{1}$对0有一条出箭头,但对1有两条;$q_{2}$对0有一条箭头,但对1没有。在NFA中,一个状态对于每个字母表符号可以有零条、一条或多条出箭头。

其次,在DFA中,转换箭头上的标签是字母表中的符号。这个NFA有一条带标签$\varepsilon$的箭头。通常,NFA可能具有标有字母表成员或$\varepsilon$的箭头。从每个状态可以有零条、一条或多条带标签$\varepsilon$的箭头射出。

12.2 逐步解释

这段话详细阐述了NFA区别于DFA的两个关键特征,并通过一个具体的例子 $N_1$ 来进行说明。

  1. NFA是DFA的推广
    • 这句话再次强调了我们在前面提到的关系:DFA是一种行为非常受限的特殊NFA。
    • 一个DFA之所以也是NFA,是因为对于DFA的每一个“唯一选择”,我们都可以把它看作是一个只包含一个元素的“选择集合”。例如,DFA规定 $\delta(q, a) = p$,这在NFA的视角下可以写成 $\delta(q, a) = \{p\}$。由于它满足NFA的广义定义,所以所有DFA都是NFA。
  2. NFA的两个核心“法外特权”
    • 特权一:灵活的转换数量
    • DFA的严格规定:对于字母表中的每一个符号,每一个状态都必须且仅有一个出转换。不能多,也不能少。
    • NFA的自由:一个状态对于一个符号,可以有:
    • 多条出转换:如图1.27中的状态 $q_1$ 对输入 1,既可以回到 $q_1$,也可以去 $q_2$。这就是产生“分身”的地方。
    • 零条出转换:如图1.27中的状态 $q_2$ 对输入 1,没有任何出箭头。如果计算分支到达 $q_2$ 并且下一个输入是 1,这个分支就会“死亡”。
    • 一条出转换:如图1.27中的状态 $q_1$ 对输入 0,只有一条出箭头回到 $q_1$。这看起来和DFA一样,但它只是NFA自由选择中的一种情况。
    • 特权二:$\varepsilon$ 转换(epsilon-transition)
    • DFA的规则:转换必须由消耗一个输入符号来触发。箭头上写的必须是字母表 $\Sigma$ 里的符号。
    • NFA的“瞬移”能力:NFA引入了一种特殊的转换,标记为 $\varepsilon$ (epsilon)。
    • $\varepsilon$ 转换的意义是“不消耗任何输入符号,就可以自发地”从一个状态转移到另一个状态。
    • 如图1.27中,从 $q_2$$q_3$ 有一条 $\varepsilon$ 箭头。这意味着,任何时候只要一个计算分支到达了状态 $q_2$,它就会立刻产生一个“分身”,这个分身会瞬间移动到 $q_3$。原来的那个计算分支可以选择停留在 $q_2$(如果后续还有路可走)。
    • 你可以把它想象成一个免费的、瞬间的、并行的状态转移。一个状态也可以有多条 $\varepsilon$ 出箭头,实现到多个状态的“瞬移”。

12.3 具体数值示例

让我们用图1.27的NFA $N_1$ 来剖析这两个特权:

12.4 易错点与边界情况

12.5 总结

本段落明确指出了NFA与DFA的两个根本区别:

  1. 转换数量的灵活性:NFA的一个状态对一个输入符号可以有0、1或多于1个转换,而DFA必须是恰好1个。
  2. $\varepsilon$转换的存在:NFA可以不消耗输入符号就进行状态转移,而DFA必须消耗一个符号才能转移。

这两个特性赋予了NFA强大的表达能力和设计上的便利性。

12.6 存在目的

本段落的目的是从结构上清晰地定义NFA,并与我们已知的DFA模型进行对比,让读者能够准确地抓住NFA的核心特征。这为后续理解NFA如何计算、如何设计以及它与DFA之间的等价关系奠定了基础。通过具体的图示 $N_1$,将抽象的规则变得具体化,易于理解。

12.7 直觉心智模型

12.8 直观想象

再次回到迷宫的比喻:

1.3 NFA的计算方式

13.1 原文

NFA如何计算?假设我们正在输入字符串上运行NFA,并到达一个有多种方式可以继续的状态。例如,假设我们在NFA $N_{1}$中的状态$q_{1}$,并且下一个输入符号是1。读取该符号后,机器会分裂成自身的多个副本并并行地遵循所有可能性。机器的每个副本都采取其中一种可能的方式继续,并像以前一样进行。如果存在后续选择,机器会再次分裂。如果下一个输入符号没有出现在机器副本所占据的状态的任何出箭头上,那么该机器副本以及与之相关的计算分支就会“死亡”。最后,如果这些机器副本中的任何一个在输入结束时处于接受状态,则NFA接受该输入字符串。

如果遇到带有$\varepsilon$符号的出箭头状态,也会发生类似的情况。不读取任何输入,机器会分裂成多个副本,一个副本遵循每个带有$\varepsilon$标签的出箭头,另一个副本停留在当前状态。然后机器像以前一样非确定性地进行。

13.2 逐步解释

这段话生动地描述了NFA的“灵魂”——它的计算过程。这个过程可以分解为以下几个关键步骤和原则:

  1. 并行宇宙模型
    • NFA的计算不是一条线,而是一棵不断分叉的“可能性之树”。
    • 核心思想:当面临选择时,NFA不选择,而是全部都要
    • 分裂/克隆:当一个计算分支(可以想象成一个“活跃指针”或一个“副本”)在一个状态下,读取一个输入符号,并且这个符号对应多个转换路径时,这个分支就会分裂(或克隆)成多个新的分支。每个新分支走一条路径。
    • 并行处理:所有存在的计算分支都会同时并行地处理下一个输入符号。
  2. 计算分支的生命周期
    • 诞生 (分裂):在起始状态,只有一个分支。当遇到多重转换或$\varepsilon$转换时,新的分支就诞生了。
    • 存活 (继续):只要当前分支所在的状态,对于下一个输入符号,有至少一条出路,这个分支就能继续存活下去,转移到新的状态集。
    • 死亡 (终止):如果一个分支所在的状态,对于下一个输入符号,没有任何出路(即转换为空集 $\emptyset$),那么这个计算分支就走到了尽头,它会立即“死亡”并从计算中消失。
  3. $\varepsilon$转换的特殊处理
    • $\varepsilon$转换是即时不消耗输入的。
    • 当一个计算分支到达一个有$\varepsilon$出箭头的状态时,它会立即分裂。
    • 一个分身会瞬间沿着$\varepsilon$箭头“传送”到目标状态。如果有多条$\varepsilon$箭头,就会分裂出多个分身,分别传送到各自的目标状态。
    • 本体(或另一个分身)会停留在当前状态,准备读取下一个输入符号。这一步是关键,$\varepsilon$转换并不会阻止当前状态处理输入。
    • 这个过程可能会连锁反应:如果传送到的新状态也有$\varepsilon$转换,那么这个新生的分身会继续分裂和传送,直到所有由$\varepsilon$连接的路径都被探索完毕。所有这些连锁反应都发生在处理同一个输入符号之前(或者说,在两个输入符号之间的瞬间)。
  4. 接受条件
    • NFA处理完整个输入字符串后(即读完最后一个符号)。
    • 我们会检查所有存活下来的计算分支。
    • 只要至少有一个分支停留在接受状态(Final State)中,整个NFA就接受(Accept)这个输入字符串。
    • 如果处理完输入后,没有任何一个存活的分支停留在接受状态(可能所有分支都死了,或者存活的分支都在非接受状态),那么NFA就拒绝(Reject)这个输入字符串。

13.3 具体数值示例

让我们再次使用图1.27的NFA $N_1$ 来模拟输入字符串 "10" 的计算过程。

模拟开始:

  1. 初始状态: 计算开始,我们在起始状态 $q_1$。当前活跃状态集合是 $\{q_1\}$
  2. 读取第一个符号 '1':
    • 我们在状态 $q_1$。查阅规则,对于输入 '1',我们有两条路:回到 $q_1$ 和去 $q_2$
    • 计算分支分裂。一个分支留在 $q_1$,另一个分支移动到 $q_2$
    • 此时,活跃状态的临时集合是 $\{q_1, q_2\}$
    • 检查 $\varepsilon$ 转换:状态 $q_1$ 没有 $\varepsilon$ 转换。状态 $q_2$ 有一条到 $q_3$$\varepsilon$ 转换。
    • $q_2$ 的分支立即再次分裂,一个分身“瞬移”到 $q_3$
    • 因此,在消耗完符号 '1' 之后,所有并行的计算分支所在的状态集合是 $\{q_1, q_2, q_3\}$
  3. 读取第二个符号 '0':
    • 我们现在并行地从 $\{q_1, q_2, q_3\}$ 这三个状态出发,读取 '0'。
    • $q_1$ 出发: 读 '0',规则是回到 $q_1$。所以这个分支移动到 $q_1$
    • $q_2$ 出发: 读 '0',规则是去 $q_3$。所以这个分支移动到 $q_3$
    • $q_3$ 出发: 读 '0',没有出路(转换是 $\emptyset$)。所以这个分支死亡
    • 在处理完所有分支后,新的活跃状态临时集合是 $\{q_1, q_3\}$
    • 检查 $\varepsilon$ 转换: $q_1$$q_3$ 都没有 $\varepsilon$ 转换。
    • 因此,在消耗完符号 '0' 之后,最终的活跃状态集合是 $\{q_1, q_3\}$
  4. 输入结束:
    • 字符串 "10" 已经处理完毕。
    • 我们检查最终的活跃状态集合 $\{q_1, q_3\}$
    • 我们看这个集合中是否有接受状态。接受状态是 $\{q_4\}$
    • 集合 $\{q_1, q_3\}$ 与集合 $\{q_4\}$ 的交集是空集。
    • 结论: 没有任何一个计算分支停留在接受状态。因此,NFA $N_1$ 拒绝字符串 "10"。

13.4 易错点与边界情况

13.5 总结

本段落阐明了NFA的核心计算范式:并行探索。它通过“分裂”来处理多重选择,通过“死亡”来终结无效路径,通过特殊的$\varepsilon$转换实现“瞬移”,最终以“只要有一线希望就成功”的乐观主义精神来判断是否接受一个字符串。

13.6 存在目的

此段的目的是为了让读者建立起对NFA动态行为的正确认知。与DFA的线性、确定性路径不同,NFA的计算过程是动态的、并行的、树状的。理解这个过程是后续分析NFA能力、设计NFA以及理解NFA与DFA等价性转换的基础。

13.7 直觉心智模型

13.8 直观想象

想象一个大型多人在线角色扮演游戏(MMORPG)中的“打副本”过程。

1.4 计算的可视化

14.1 原文

非确定性可以看作是一种并行计算,其中多个独立的“进程”或“线程”可以并发运行。当NFA分裂以遵循多个选择时,这对应于一个进程“分叉”成多个子进程,每个子进程独立进行。如果至少有一个这样的进程接受,那么整个计算就接受。

考虑非确定性计算的另一种方式是将其视为一个可能性树。树的根对应于计算的开始。树中的每个分支点对应于机器有多种选择的计算点。如果至少一个计算分支以接受状态结束,则机器接受,如图1.28所示。

图 1.28

带有接受分支的确定性与非确定性计算

14.2 逐步解释

这段话提供了两种非常有用的高级视角来理解和可视化NFA的计算过程:并行进程计算树

  1. 并行进程/线程 (Parallel Processes/Threads)
    • 这个类比将NFA的计算与现代计算机科学中的并发编程联系起来。
    • 主进程:NFA的计算始于一个单一的进程,位于起始状态。
    • 分叉 (Forking):当遇到非确定性选择(多重转换或$\varepsilon$转换)时,就如同操作系统中的 fork() 系统调用。当前进程会创建一个或多个子进程
    • 独立执行:每个子进程(以及父进程)都拥有自己独立的状态和执行路径,它们并发地、互不干扰地处理接下来的输入。
    • 进程终止:当一个计算分支“死亡”时,就好比一个进程执行完毕或异常退出。
    • 成功条件:只要有任何一个进程在处理完所有输入后,发现自己处于“成功”状态(即接受状态),整个任务就被认为是成功的。
  2. 可能性之树 (Tree of Possibilities)
    • 这是一个更数学化、更直观的几何模型,如图1.28所示。
    • 树根 (Root):代表整个计算的起点,即在处理第一个输入符号之前的起始状态。
    • 节点 (Node):树中的每个节点可以代表一个 (状态, 剩余输入) 的组合。
    • 分支 (Branching):当机器在一个节点上有多种选择时,这个节点就会生长出多条树枝,每条树枝代表一个选择。
    • 在图1.28的右侧(非确定性计算),在初始状态读入第一个符号后,产生了3个分支,代表有3种可能性。
    • 之后,中间那个分支在读入第二个符号后又分裂成2个分支。
    • 路径 (Path):从树根到任意一个节点的路径,代表了一个完整的计算历史。
    • 叶子节点 (Leaf Node):代表一个计算分支的终点。这个终点可能是因为输入处理完毕,也可能是因为中途“死亡”。
    • 接受路径:如果在输入处理完毕时,有一条从根到叶子节点的路径,其终点(叶子节点)的状态是接受状态,那么这条路径就是一条“接受路径”。
    • 接受条件:整棵树只要存在至少一条接受路径,NFA就接受该输入。图1.28中,最右侧的路径最终到达了一个接受状态(图中未明确标出,但用“accept”示意),因此整个计算是接受的。

14.3 具体数值示例

让我们用图1.27的NFA $N_1$ 和输入 "101" 来构建一个计算树:

树的构建:

  1. : (q1, "101") (在q1,等待处理"101")
  2. 第一层 (处理 '1'): 从 $q_1$ 读 '1',可以到 $q_1$$q_2$。同时 $q_2$$\varepsilon$$q_3$
    • 分支1: (q1, "01")
    • 分支2: (q2, "01")
    • 分支3 (由分支2的$\varepsilon$产生): (q3, "01")
  3. 第二层 (处理 '0'):
    • (q1, "01") 读 '0' -> (q1, "1")
    • (q2, "01") 读 '0' -> (q3, "1")
    • (q3, "01") 读 '0' -> (无路可走, 此分支死亡)
  4. 第三层 (处理 '1'):
    • (q1, "1") 读 '1' -> 分裂成 (q1, ""), (q2, "")。其中 (q2, "") 又立即$\varepsilon$分裂出 (q3, "")。所以活跃状态是 $\{q_1, q_2, q_3\}$
    • (q3, "1") 读 '1' -> (q4, "")
  5. 结束 (输入为空 ""):
    • 我们检查所有叶子节点的状态:
    • 来自第一个主要分支的叶子节点状态是 $\{q_1, q_2, q_3\}$
    • 来自第二个主要分支的叶子节点状态是 $\{q_4\}$
    • 最终状态集合: 所有幸存分支的集合是 $\{q_1, q_2, q_3, q_4\}$
    • 判断: 这个集合中包含了接受状态 $q_4$
    • 结论: NFA $N_1$ 接受 "101"。

这棵树形象地展示了所有并行的可能性。

14.4 易错点与边界情况

14.5 总结

本段通过两个核心类比——并行进程计算树——为非确定性计算提供了一个高层次的、直观的理解框架。这两个模型都强调了NFA的“并行探索”和“只要有一路通即可”的本质。

14.6 存在目的

在详细描述了NFA的底层操作后,本段的目的是提供一个“更高维度”的视角,帮助读者将这些零碎的规则(分裂、死亡、$\varepsilon$转换)整合到一个统一的、概念性的框架中。这使得理解和推理NFA的行为变得更加容易,也为后续更复杂的计算模型(如图灵机中的非确定性)打下概念基础。

14.7 直觉心智模型

14.8 直观想象

想象一下光线通过一个复杂的光学仪器。

1.5 NFA计算示例分析

15.1 原文

让我们考虑NFA $N_{1}$(如图1.27所示)的一些样本运行。$N_{1}$在输入010110上的计算如下图所示。

图 1.29

$N_{1}$在输入010110上的计算

在输入010110上,从起始状态$q_{1}$开始并读取第一个符号0。从$q_{1}$开始,对0只有一个去处——即回到$q_{1}$——所以停留在那里。接下来,读取第二个符号1。在$q_{1}$上读取1时,有两种选择:要么停留在$q_{1}$,要么移动到$q_{2}$。非确定性地,机器分裂成两个副本以遵循每个选择。通过在机器可能处于的每个状态上放置一个手指来跟踪这些可能性。所以你现在在状态$q_{1}$$q_{2}$上都有手指。一个$\varepsilon$箭头从状态$q_{2}$射出,所以机器再次分裂;一个手指留在$q_{2}$上,另一个移动到$q_{3}$。你现在在$q_{1}$$q_{2}$$q_{3}$上都有手指。

读取第三个符号0时,依次取下每个手指。将$q_{1}$上的手指保持在原位,将$q_{2}$上的手指移动到$q_{3}$,并移除原本在$q_{3}$上的手指。最后一个手指没有0箭头可遵循,对应于一个简单地“死亡”的进程。此时,你的手指停留在状态$q_{1}$$q_{3}$上。

读取第四个符号1时,将$q_{1}$上的手指分成$q_{1}$$q_{2}$上的手指,然后将$q_{2}$上的手指进一步分裂以跟随$\varepsilon$箭头到$q_{3}$,并将原本在$q_{3}$上的手指移动到$q_{4}$。你现在在所有四个状态上都有手指。

读取第五个符号1时,正如你用第四个符号看到的那样,$q_{1}$$q_{3}$上的手指会产生在状态$q_{1}$$q_{2}$$q_{3}$$q_{4}$上的手指。$q_{2}$上的手指被移除。原本在$q_{4}$上的手指仍然停留在$q_{4}$上。现在你在$q_{4}$上有了两个手指,所以移除一个,因为你只需要记住$q_{4}$在此时是一个可能的州,而不是它可能因为多种原因。

读取第六个也是最后一个符号0时,将$q_{1}$上的手指保持在原位,将$q_{2}$上的手指移动到$q_{3}$,移除原本在$q_{3}$上的手指,并将$q_{4}$上的手指保持在原位。你现在处于字符串的末尾,如果某个手指处于接受状态,则你接受。你的手指停留在状态$q_{1}$$q_{3}$$q_{4}$上;由于$q_{4}$是一个接受状态,$N_{1}$接受这个字符串。

15.2 逐步解释

这一长段通过“手指模拟法”,极其细致地一步步追踪了NFA $N_1$ 对输入字符串 010110 的处理过程。这个过程可以用一个表格来更清晰地展现,表格追踪每一步之后活跃状态的集合

| 步骤 | 已处理的输入 | 待处理的输入 | 当前活跃状态集合 (处理输入前) | 读取的符号 | 转换后的临时集合 | $\varepsilon$-闭包 | 最终活跃状态集合 (处理输入后) |

| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |

| 0 | "" | "010110" | $\{q_1\}$ | (开始) | N/A | (从$q_1$开始没有$\varepsilon$转换) | $\{q_1\}$ |

| 1 | "0" | "10110" | $\{q_1\}$ | 0 | 从 $q_1$ 读 0 到 $\{q_1\}$ | $\{q_1\}$ | $\{q_1\}$ |

| 2 | "01" | "0110" | $\{q_1\}$ | 1 | 从 $q_1$ 读 1 到 $\{q_1, q_2\}$ | $\{q_1\}$不变, $\{q_2\}$增加$q_3$ | $\{q_1, q_2, q_3\}$ |

| 3 | "010" | "110" | $\{q_1, q_2, q_3\}$ | 0 | 从$q_1$读0到$q_1$; 从$q_2$读0到$q_3$; 从$q_3$读0死亡 | $\{q_1\}$不变, $\{q_3\}$不变 | $\{q_1, q_3\}$ |

| 4 | "0101" | "10" | $\{q_1, q_3\}$ | 1 | 从$q_1$读1到$\{q_1, q_2\}$; 从$q_3$读1到$q_4$。合并得$\{q_1, q_2, q_4\}$ | 从$q_2$增加$q_3$。合并得$\{q_1, q_2, q_3, q_4\}$ | $\{q_1, q_2, q_3, q_4\}$ |

| 5 | "01011" | "0" | $\{q_1, q_2, q_3, q_4\}$ | 1 | 从$q_1$读1到$\{q_1, q_2\}$; 从$q_2$读1死亡; 从$q_3$读1到$q_4$; 从$q_4$读1到$q_4$。合并得$\{q_1, q_2, q_4\}$ | 从$q_2$增加$q_3$。合并得$\{q_1, q_2, q_3, q_4\}$ | $\{q_1, q_2, q_3, q_4\}$ |

| 6 | "010110" | "" | $\{q_1, q_2, q_3, q_4\}$ | 0 | 从$q_1$读0到$q_1$; 从$q_2$读0到$q_3$; 从$q_3$读0死亡; 从$q_4$读0到$q_4$。合并得$\{q_1, q_3, q_4\}$ | $\{q_1\}$, $\{q_3\}$, $\{q_4\}$均无$\varepsilon$转换 | $\{q_1, q_3, q_4\}$ |

最终判断:

解释原文中的几个细节:

15.3 具体数值示例

原文已经提供了一个非常详尽的示例。我们再补充一个拒绝的例子来对比。

  1. 开始: 活跃状态 $\{q_1\}$
  2. 读 '0': 从 $q_1$ 读 '0' 到 $q_1$。活跃状态 $\{q_1\}$
  3. 读 '1': 从 $q_1$ 读 '1' 到 $\{q_1, q_2\}$。由于 $q_2$$\varepsilon$ 转换,活跃状态变为 $\{q_1, q_2, q_3\}$
  4. 读 '0':
    • $q_1$ 读 '0' 到 $q_1$
    • $q_2$ 读 '0' 到 $q_3$
    • $q_3$ 读 '0' 死亡。
    • 合并结果,新的活跃状态为 $\{q_1, q_3\}$
  5. 输入结束:
    • 最终活跃状态集合是 $\{q_1, q_3\}$
    • 这个集合与接受状态集合 $\{q_4\}$ 的交集是空集。
    • 结论: NFA $N_1$ 拒绝 字符串 010

15.4 易错点与边界情况

  1. 初始化一个空集合 $T$
  2. 对于 $S_i$ 中的每一个状态 $q$:计算 $\delta(q, \text{input}_i)$,把结果(一个状态集合)加入到 $T$ 中。
  3. 计算 $T$ 中所有状态的 $\varepsilon$-闭包,即 $S_{i+1} = E(T)$。其中 $E(T)$ 表示从 $T$ 中任何状态出发,只通过0个或多个 $\varepsilon$ 箭头能到达的所有状态的集合。

15.5 总结

本段通过一个具体的、循序渐进的例子,将前面介绍的NFA计算规则付诸实践。它展示了如何动态地追踪活跃状态集合,如何处理多重转换和 $\varepsilon$ 转换,以及最终如何根据输入结束时的状态来做出接受或拒绝的判断。

15.6 存在目的

这个例子的目的是巩固读者对NFA计算过程的理解。理论规则往往是抽象的,而一个具体的、手把手的演练能够极大地帮助读者建立起对这个动态过程的坚实感觉。它为读者自行分析其他NFA和输入提供了模仿的范本。

15.7 直觉心智模型

多世界诠释:NFA的计算就像物理学中的“多世界诠释”。每当遇到一个选择,宇宙(计算)就分裂成多个平行的宇宙,每个宇宙里发生一种可能性。只要在输入结束时,有一个宇宙里的你(计算分支)处于“幸福”状态(接受状态),那么对于最初的你来说,整个事件就是“成功”的。

15.8 直观想象

想象你在玩一个弹珠游戏机。

1.6 NFA识别的语言

16.1 原文

通过继续以这种方式进行实验,你将看到$N_{1}$接受所有包含子字符串101或11的字符串。

非确定性有限自动机在几个方面都很有用。正如我们将展示的,每个NFA都可以转换为等价的DFA,并且构建NFA有时比直接构建DFA更容易。NFA可能比其确定性对应物小得多,或者其功能可能更容易理解。有限自动机中的非确定性也是更强大的计算模型中非确定性的一个很好的介绍,因为有限自动机特别容易理解。现在我们来看几个NFA的例子。

16.2 逐步解释

这段话分为两部分:对NFA $N_1$ 功能的总结,以及对NFA概念重要性的阐述。

  1. NFA $N_1$ 的功能
    • 原文断言 $N_1$ 识别的语言是“所有包含子字符串 10111 的字符串”。
    • 我们来直观地理解为什么。观察 $N_1$ 的结构:
    • 起始状态 $q_1$ 有一个自循环,可以吃掉任意多的 01。这代表机器在“等待”某个关键模式的出现。
    • 要想到达最终的接受状态 $q_4$,必须经过路径 $q_1 \to q_2 \to q_3 \to q_4$
    • 分析路径 $q_1 \to q_2 \to q_3 \to q_4$
    • $q_1$$q_2$ 需要一个 1
    • $q_2$$q_3$ 需要一个 0。(注意,从$q_2$$q_3$还有一条$\varepsilon$路,我们稍后分析)
    • $q_3$$q_4$ 需要一个 1
    • 所以,如果机器走 $q_1 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \xrightarrow{1} q_4$ 这条路,它就成功匹配了子串 101。一旦到达 $q_4$,由于 $q_4$01 都有自循环,后面跟任何东西都无所谓,机器将永远停留在接受状态。
    • 现在分析另一条通往成功的路径。注意到 $N_1$ 的设计中,从 $q_1$1 可以到 $q_2$,而 $q_2$ 立即可以 $\varepsilon$ 跳到 $q_3$。这意味着什么?
    • 当机器在 $q_1$ 读到第一个 1 时,它分裂到 $\{q_1, q_2, q_3\}$
    • 如果下一个输入符号是 1,会发生什么?
    • $q_1$ 的分支,可以继续分裂到 $\{q_1, q_2, q_3\}$
    • $q_2$ 的分支,死亡。
    • $q_3$ 的分支,可以移动到 $q_4$
    • 所以,路径 $q_1 \xrightarrow{1} q_2 \xrightarrow{\varepsilon} q_3 \xrightarrow{1} q_4$ 使得机器在读到子串 11 后能够到达接受状态 $q_4$
    • 结论:NFA $N_1$ 的设计逻辑就是:在任意位置,一旦“猜测”(非确定性地进入)可能出现了 10111,就沿着对应的路径去验证。如果验证成功(到达$q_4$),就接受。这就是它识别包含 10111 的字符串的原理。
  2. NFA 的重要性
    • 等价性 (Equivalence):这是一个核心定理(后面会证明),即 NFA 和 DFA 的计算能力是相同的。任何一个NFA能够识别的语言,也必然存在一个DFA能够识别它,反之亦然。它们都恰好能识别正则语言这一族。
    • 设计便利性 (Easier to construct):这是NFA最有用的地方。对于很多语言,直接设计一个DFA会非常复杂,因为DFA需要“记住”很多信息。而设计NFA则可以利用“猜测”的能力,让结构变得异常简洁和直观。例如,要识别包含 101 的语言,DFA需要多个状态来记录“我看到了1”、“我看到了10”、“我看到了101”,而NFA可以很简单地设计。
    • 简洁性 (Much smaller):通常,对于同一个语言,NFA的状态数量可能远远少于等价的DFA的状态数量。在最坏情况下,一个 $k$ 个状态的NFA可能需要一个拥有 $2^k$ 个状态的DFA来等价模拟。
    • 教学价值 (Good introduction):NFA中的非确定性概念相对简单,是通往更高级计算模型(如非确定性图灵机)的一个很好的入门台阶。

16.3 具体数值示例

16.4 易错点与边界情况

16.5 总结

本段落是承上启下的过渡。它总结了第一个例子NFA $N_1$的功能,并引出了NFA作为一个理论工具的三个核心价值:与DFA等价,设计上更简单更小,以及作为学习后续概念的好起点

16.6 存在目的

在深入展示了NFA的计算细节后,本段的目的是回答一个重要问题:“我们为什么要学习NFA这么一个看起来有点奇怪的模型?” 答案是,它是一个非常有用的抽象工具,能让我们以更简洁、更强大的方式思考和解决问题,即使它的底层能力并未超越我们已知的模型。

16.7 直觉心智模型

16.8 直观想象

想象你要写一份寻人启事。

1.7 示例 1.30: 识别倒数第三位是1的语言

17.1 原文

$A$是所有包含一个1在倒数第三个位置的字符串组成的语言(例如,000100在$A$中,但0011不在)。下面的四状态NFA $N_{2}$识别$A$

图 1.31

识别$A$的NFA $N_{2}$

看待这个NFA计算的一种好方法是说它停留在起始状态$q_{1}$,直到它“猜测”距离末尾还有三个位置。此时,如果输入符号是1,它分支到状态$q_{2}$并使用$q_{3}$$q_{4}$来“检查”它的猜测是否正确。

如前所述,每个NFA都可以转换为等价的DFA;但有时DFA可能具有更多的状态。用于$A$的最小DFA包含八个状态。此外,理解NFA的功能要容易得多,你可以通过检查下面DFA的图来看到。

图 1.32

识别$A$的DFA

假设我们将$\boldsymbol{\varepsilon}$添加到机器$N_{2}$中从$q_{2}$$q_{3}$以及从$q_{3}$$q_{4}$的箭thole上。这样,两条箭头都将带有标签$0,1, \varepsilon$,而不仅仅是$0,1$$N_{2}$经过这种修改后会识别哪种语言?尝试修改图1.32中的DFA以识别该语言。

17.2 逐步解释

这个例子完美地展示了NFA在设计上的巨大优势。

  1. 语言 A 的定义:
    • 语言 A 包含所有在字母表 $\{0, 1\}$ 上,其倒数第三个字符是 1 的字符串。
    • 形式化描述: $A = \{ w \in \{0,1\}^* \mid w = x1ab \text{ where } x \in \{0,1\}^* \text{ and } a, b \in \{0,1\} \}$
    • 正例: 100, 0101, 1111, 000100
    • 反例: 10, 0011, 0, \varepsilon (空字符串)。
  2. NFA $N_2$ 的设计哲学——“猜测与验证”:
    • $q_1$ (猜测阶段): 机器开始于 $q_1$$q_1$ 上有一个自循环,可以接受任意的 01。这意味着机器在读取字符串的前缀部分时,一直保持“观望”态度。它在说:“我不知道这个字符是不是倒数第三个,所以我先吃掉它,然后继续等待。” 同时,对于每一个读到的 1,它都多疑地进行一次“猜测”。
    • 非确定性猜测: 在 $q_1$ 状态,每当读到一个 1,NFA就面临一个选择:
    • 选择一 (继续观望): 留在 $q_1$,认为这个 1 不是关键的倒数第三个。
    • 选择二 (开始验证): 转移到 $q_2$猜测这个 1 可能就是倒数第三个字符。
    • 由于是非确定性,NFA会同时做这两个选择,分裂出一个新的计算分支去 $q_2$
    • $q_2 \to q_3 \to q_4$ (验证阶段):
    • 一旦一个分支进入了 $q_2$,它就进入了一个“验证”模式。这个模式的逻辑是:“如果我的猜测是对的,那么后面必须恰好还有两个字符。”
    • $q_2 \to q_3$: 无论下一个字符是 0 还是 1a),都转移到 $q_3$。这步消耗了倒数第二个字符。
    • $q_3 \to q_4$: 无论再下一个字符是 0 还是 1b),都转移到 $q_4$。这步消耗了最后一个字符。
    • 到达 $q_4$: 如果一个分支成功地走完了 $q_1 \xrightarrow{1} q_2 \xrightarrow{a} q_3 \xrightarrow{b} q_4$ 这条路,并且此时输入字符串也恰好结束,那么它的猜测就是正确的。因为 $q_4$ 是接受状态,整个字符串被接受。
    • 失败的猜测: 如果在 $q_1$ 做的某次猜测是错的(比如在字符串 01000 的第2个字符 1 就跳到了 $q_2$),那么这个分支在 $q_4$ 结束后,输入还有剩余的 0,但 $q_4$ 没有出路,分支死亡。只有在正确的位置做出的那个猜测,其对应的分支才能在输入结束时恰好停在 $q_4$
  3. NFA vs DFA 的对比:
    • NFA ($N_2$): 结构非常简单,只有4个状态。它的逻辑清晰地反映了问题的本质:“寻找一个 1,然后确保后面还有两个字符”。
    • DFA (图1.32): 结构复杂得多,有8个状态。DFA不能“猜测”,所以它必须用状态来确定地记住最后三个字符的所有可能组合。
    • 例如,状态 q000 可能表示“我看到的最后三个字符是000”。状态 q101 可能表示“我看到的最后三个字符是101”。
    • 它的起始状态会对应一种初始情况,比如 q_ (表示还没读够3个字符)。
    • 当新读入一个字符时,DFA需要根据当前状态(记录的最后3个字符)和新字符,计算出新的最后3个字符,然后转移到对应的状态。
    • 哪些状态是接受状态?所有表示“最后三个字符是 1xx”的状态,即 q100, q101, q110, q111 都会是接受状态。
    • 构造这个DFA的过程繁琐且容易出错,最终的图也远不如NFA直观。这有力地证明了NFA在设计上的优越性。
  4. 思考题:添加 $\varepsilon$ 转换
    • 问题: 如果把 $q_2 \to q_3$$q_3 \to q_4$ 的箭头标签从 0,1 改为 0,1,ε,NFA会识别什么语言?
    • 分析:
    • 原来的 $q_2 \to q_3 \to q_4$ 路径强制消耗两个字符。
    • 现在,由于有了 $\varepsilon$ 转换,从 $q_2$$q_4$ 的路径可以消耗 2个、1个 或 0个 字符。
    • 消耗2个字符: $q_2 \xrightarrow{0/1} q_3 \xrightarrow{0/1} q_4$
    • 消耗1个字符: $q_2 \xrightarrow{0/1} q_3 \xrightarrow{\varepsilon} q_4$ 或者 $q_2 \xrightarrow{\varepsilon} q_3 \xrightarrow{0/1} q_4$
    • 消耗0个字符: $q_2 \xrightarrow{\varepsilon} q_3 \xrightarrow{\varepsilon} q_4$
    • 这意味着,当机器在 $q_1$ 看到一个 1 并“猜测”它可能是关键字符时,这个 1 后面可以跟 0, 1 或 2 个字符。
    • 所以,修改后的NFA识别的语言是:所有包含一个 1,且这个 1 位于倒数第1位、或倒数第2位、或倒数第3位的字符串。换句话说,就是识别所有以 1, 1x, 或 1xx 结尾的子模式的字符串,其中x是0或1。
    • 这个语言可以更简洁地描述为:所有最后三个字符中至少包含一个 1 的字符串(对于长度不足3的字符串,则是所有字符中至少有一个1,比如 01, 1)。

17.3 具体数值示例

使用 NFA $N_2$ 处理字符串 0100:

  1. 开始: 活跃状态 $\{q_1\}$
  2. 读 '0': 从 $q_1$ 读 '0',留在 $q_1$。活跃状态 $\{q_1\}$
  3. 读 '1': 从 $q_1$ 读 '1',分裂!
    • 分支A (不猜测): 留在 $q_1$
    • 分支B (猜测): 移动到 $q_2$
    • 活跃状态 $\{q_1, q_2\}$
  4. 读 '0':
    • 分支A (在 $q_1$): 读 '0',留在 $q_1$
    • 分支B (在 $q_2$): 读 '0',移动到 $q_3$
    • 活跃状态 $\{q_1, q_3\}$
  5. 读 '0':
    • 分支A (在 $q_1$): 读 '0',留在 $q_1$
    • 分支B (在 $q_3$): 读 '0',移动到 $q_4$
    • 活跃状态 $\{q_1, q_4\}$
  6. 输入结束:
    • 最终活跃状态集合是 $\{q_1, q_4\}$
    • 这个集合包含接受状态 $q_4$
    • 结论: 接受 0100。这是正确的,因为倒数第三位是 1

17.4 易错点与边界情况

17.5 总结

示例1.30是一个典型的、极具说服力的例子,它清晰地展示了:

  1. 如何利用NFA的“猜测-验证”模式来简洁地设计一个识别器。
  2. 对于某些语言,NFA在状态数量和直观性上远胜于等价的DFA。
  3. 强调了NFA作为一种设计工具的实用价值。

17.6 存在目的

本示例的目的是为了让读者亲身体会到NFA的优雅和强大。通过将一个清晰直观的4状态NFA与一个复杂难懂的8状态DFA并置,作者有力地论证了引入非确定性概念的必要性和好处,激发读者学习和使用NFA的兴趣。

17.7 直觉心智模型

17.8 直观想象

想象你在一条很长的传送带上检查产品,规则是“如果一个产品是红色的,并且它后面紧跟着两个产品,那么就算合格”。

1.8 示例 1.33: 一元字母表上的NFA

18.1 原文

下面的NFA $N_{3}$有一个只包含一个符号的输入字母表$\{0\}$。只包含一个符号的字母表称为一元字母表

图 1.34

NFA $N_{3}$

这台机器展示了拥有$\varepsilon$箭头的便利性。它接受所有形式为$0^{k}$的字符串,其中$k$是2或3的倍数。(请记住,上标表示重复,而不是数字指数。)例如,$N_{3}$接受字符串$\varepsilon, 00,000,0000$和000000,但不接受0或00000。

设想机器通过最初猜测是测试2的倍数还是3的倍数来操作,通过分支到上面的循环或下面的循环,然后检查其猜测是否正确。当然,我们可以用一台没有$\varepsilon$箭头甚至没有任何非确定性的机器来代替这台机器,但所示的机器是针对这种语言最容易理解的机器。

18.2 逐步解释

这个例子展示了 $\varepsilon$ 转换如何优雅地实现“或”的逻辑。

  1. 一元字母表 (Unary Alphabet):
    • 这是一个只有一个符号的字母表,例如 $\{0\}$$\{a\}$
    • 在这种字母表上,所有的字符串都是由同一个符号重复组成的,例如 $\varepsilon, 0, 00, 000, ...$。因此,识别这类语言的关键通常在于字符串的长度
  2. 语言描述:
    • $N_3$ 识别的语言是所有长度 $k$ 是 2 的倍数 3 的倍数的字符串。
    • $L = \{ 0^k \mid k \text{ is a multiple of 2 or } k \text{ is a multiple of 3} \}$
    • 正例:
    • $0^0 = \varepsilon$ (0是2和3的倍数)
    • $0^2 = 00$ (2是2的倍数)
    • $0^3 = 000$ (3是3的倍数)
    • $0^4 = 0000$ (4是2的倍数)
    • $0^6 = 000000$ (6是2和3的倍数)
    • 反例:
    • $0^1 = 0$ (1不是2或3的倍数)
    • $0^5 = 00000$ (5不是2或3的倍数)
    • $0^7 = 0000000$
  3. NFA $N_3$ 的设计哲学——“兵分两路”:
    • $q_1$ (决策点): 这是起始状态。注意,它本身也是一个接受状态!这直接处理了 $k=0$ 的情况,即接受空字符串 $\varepsilon$
    • $\varepsilon$ 分裂: 从 $q_1$ 出发,有两条 $\varepsilon$ 箭头,分别指向 $q_2$$q_5$
    • 这意味着计算一开始,甚至在读取任何输入之前,机器就分裂成了三个分支:一个留在 $q_1$,一个瞬移到 $q_2$,一个瞬移到 $q_5$
    • 这完美地体现了“猜测”:
    • 分支去 $q_2$ 是在猜测:“我要开始检查输入长度是否为2的倍数了”。
    • 分支去 $q_5$ 是在猜测:“我要开始检查输入长度是否为3的倍数了”。
    • 留在 $q_1$ 这一路,因为 $q_1$ 是接受状态,它始终代表了接受长度为0的字符串的可能性。
    • 上半部分 ($q_2, q_3$) - 模2计数器:
    • 这是一个长度为2的循环。从 $q_2$ 读一个 0$q_3$。从 $q_3$ 读一个 0 回到 $q_2$
    • 每读两个 0,机器就会回到 $q_2$
    • 状态 $q_2$ 被设计成接受状态。这意味着,如果输入字符串的长度是2的倍数(2, 4, 6, ...),这个分支在读完输入后就会停在 $q_2$,从而导致整个NFA接受。
    • 下半部分 ($q_5, q_6, q_7$) - 模3计数器:
    • 这是一个长度为3的循环。$q_5 \xrightarrow{0} q_6 \xrightarrow{0} q_7 \xrightarrow{0} q_5$
    • 每读三个 0,机器就会回到 $q_5$
    • 状态 $q_5$ 被设计成接受状态。这意味着,如果输入字符串的长度是3的倍数(3, 6, 9, ...),这个分支在读完输入后就会停在 $q_5$,从而导致整个NFA接受。
    • 整合: 由于NFA的接受条件是“至少一个分支接受”,所以只要字符串长度是2的倍数3的倍数,相应的分支就会成功,整个NFA就会接受。
  4. 便利性:
    • 这个NFA结构清晰地分离了两个子问题(“是2的倍数吗?”和“是3的倍数吗?”),然后用 $\varepsilon$ 箭头将它们“或”在一起。
    • 如果要用DFA来设计,该怎么做?你需要一个状态机来同时追踪长度模2和模3的余数。
    • 一个数的长度 $k$ 模2的余数有2种可能(0, 1)。
    • $k$ 模3的余数有3种可能(0, 1, 2)。
    • 为了同时记录这两个信息,DFA的状态需要表示一个有序对 (k mod 2, k mod 3)
    • 这样的状态总共有 $2 \times 3 = 6$ 个。例如,状态 (0, 1) 表示长度模2余0,模3余1(例如长度为4的字符串)。
    • 起始状态是 (0, 0)(代表长度为0)。
    • 接受状态是所有满足 k mod 2 = 0 k mod 3 = 0 的状态对,即 (0, 0), (0, 1), (0, 2), (1, 0)
    • 虽然这个6状态的DFA也可以构造,但它的结构远不如NFA $N_3$ 那样直观地反映“2的倍数 或 3的倍数”这一逻辑。

17.3 具体数值示例

使用 NFA $N_3$ 处理字符串 0000 ($k=4$):

  1. 开始: 活跃状态 $\{q_1\}$。立即进行 $\varepsilon$ 分裂。活跃状态变为 $\{q_1, q_2, q_5\}$
  2. 读第一个 '0':
    • $q_1$: 无路可走,死亡。(注意:$q_1$ 本身没有标0的循环,它只作为起始和接受ε用)
    • $q_2$: 移动到 $q_3$
    • $q_5$: 移动到 $q_6$
    • 活跃状态 $\{q_3, q_6\}$
  3. 读第二个 '0':
    • $q_3$: 移动到 $q_2$
    • $q_6$: 移动到 $q_7$
    • 活跃状态 $\{q_2, q_7\}$
  4. 读第三个 '0':
    • $q_2$: 移动到 $q_3$
    • $q_7$: 移动到 $q_5$
    • 活跃状态 $\{q_3, q_5\}$
  5. 读第四个 '0':
    • $q_3$: 移动到 $q_2$
    • $q_5$: 移动到 $q_6$
    • 活跃状态 $\{q_2, q_6\}$
  6. 输入结束:
    • 最终活跃状态集合是 $\{q_2, q_6\}$
    • 接受状态集合是 $\{q_1, q_2, q_5\}$
    • 最终活跃状态和接受状态的交集是 $\{q_2\}$,非空。
    • 结论: 接受 0000。这是正确的,因为4是2的倍数。

17.4 易错点与边界情况

17.5 总结

示例1.33展示了如何利用NFA,特别是 $\varepsilon$ 转换,将一个复杂逻辑(“A或B”)分解为两个独立的、简单的子问题(A和B),然后将它们并行组合。这种“模块化”的设计思想是NFA强大表达能力的重要体现。

17.6 存在目的

本示例的核心目的是展示 $\varepsilon$ 转换在实现选择组合逻辑时的便利性。它告诉我们,当一个语言可以被描述为多个简单语言的并集时(例如 $L = L_1 \cup L_2$),我们可以为每个简单语言设计一个NFA,然后用一个带 $\varepsilon$ 转换的新起始状态将它们连接起来,从而轻松得到识别 $L$ 的NFA。这为后面将要介绍的正则语言在并集运算下的闭包性提供了直观的证明思路。

17.7 直觉心智模型

17.8 直观想象

想象一个双人接力赛跑。

1.9 示例 1.35: 另一个NFA示例

19.1 原文

我们再举一个NFA的例子,见图1.36。练习一下,让自己确信它接受字符串$\varepsilon$、a、baba和baa,但不接受字符串b、bb和babba。稍后我们将使用这台机器来说明将NFA转换为DFA的过程。

图 1.36

NFA $N_{4}$

19.2 逐步解释

这个例子 $N_4$ 是一个综合性的练习,它包含多重转换、$\varepsilon$ 转换以及循环,是为后面更复杂的“NFA转DFA”算法做铺垫的绝佳素材。让我们来手动验证原文给出的几个例子。

手动验证:

  1. 接受 $\varepsilon$ (空字符串)?
    • 过程: 计算开始,我们在起始状态 $1$。输入结束。
    • 判断: 最终状态是 $1$,而 $1$ 是接受状态。
    • 结论: 接受 $\varepsilon$(正确)
  2. 接受 a?
    • 过程:
  3. 开始,活跃状态 $\{1\}$。立即 $\varepsilon$ 分裂到 $\{1, 3\}$
  4. 读 'a':
    • $1$: 无路,死亡。
    • $3$: 移动到 $1$
  5. 活跃状态 $\{1\}$
  6. 输入结束。
    • 判断: 最终状态是 $1$,是接受状态。
    • 结论: 接受 a(正确)
  7. 接受 baba?
    • 过程:
  8. 开始,$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  9. 读 'b': 从 $1 \to 2$。从 $3$ 无路。活跃状态 $\{2\}$
  10. 读 'a': 从 $2 \to 2, 3$。活跃状态 $\{2, 3\}$
  11. 读 'b': 从 $2 \to 3$。从 $3$ 无路。活跃状态 $\{3\}$
  12. 读 'a': 从 $3 \to 1$。因为到达了1,所以需要做$\varepsilon$闭包,活跃状态变为 $\{1, 3\}$
  13. 输入结束。
    • 判断: 最终活跃状态 $\{1, 3\}$ 包含接受状态 $1$
    • 结论: 接受 baba(正确)
  14. 接受 baa?
    • 过程:
  15. 开始,$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  16. 读 'b': 从 $1 \to 2$。活跃状态 $\{2\}$
  17. 读 'a': 从 $2 \to 2, 3$。活跃状态 $\{2, 3\}$
  18. 读 'a': 从 $2 \to 2, 3$。从 $3 \to 1$。合并得 $\{1, 2, 3\}$。因为包含1,做$\varepsilon$闭包,但3已在集合中。最终活跃状态为 $\{1, 2, 3\}$
  19. 输入结束。
    • 判断: 最终活跃状态 $\{1, 2, 3\}$ 包含接受状态 $1$
    • 结论: 接受 baa(正确)
  20. 接受 b?
    • 过程:
  21. 开始,$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  22. 读 'b': 从 $1 \to 2$。活跃状态 $\{2\}$
  23. 输入结束。
    • 判断: 最终状态 $2$ 不是接受状态。
    • 结论: 拒绝 b(正确)
  24. 接受 bb?
    • 过程:
  25. 开始,$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  26. 读 'b': 从 $1 \to 2$。活跃状态 $\{2\}$
  27. 读 'b': 从 $2 \to 3$。活跃状态 $\{3\}$
  28. 输入结束。
    • 判断: 最终状态 $3$ 不是接受状态。
    • 结论: 拒绝 bb(正确)
  29. 接受 babba?
    • 过程:
  30. 开始,$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  31. 读 'b': 从

$1 \to 2$。从 $3$ 无路。活跃状态 $\{2\}$

  1. 读 'b': 从 $2 \to 3$。活跃状态 $\{3\}$
  2. 输入结束。
    • 判断: 最终状态 $3$ 不是接受状态。
    • 结论: 拒绝 bb(正确)
  3. 接受 babba?
    • 过程:
  4. 开始,$\varepsilon$ 闭包后活跃状态 $\{1, 3\}$
  5. 读 'b': 从 $1 \to 2$。从 $3$ 无路。活跃状态 $\{2\}$
  6. 读 'a': 从 $2 \to 2, 3$。活跃状态 $\{2, 3\}$
  7. 读 'b': 从 $2 \to 3$。从 $3$ 无路。活跃状态 $\{3\}$
  8. 读 'b': 从 $3$ 无路。计算分支死亡。活跃状态为 $\emptyset$
  9. 输入未结束 ('a' 待处理),但已无活跃分支。
    • 判断: 计算在中途终止。
    • 结论: 拒绝 babba(正确)

19.3 具体数值示例

原文已经引导读者做了充足的示例验证。这个练习本身就是最好的示例。

19.4 易错点与边界情况

19.5 总结

$N_4$ 是一个理想的“沙盘模型”,它的复杂性恰到好处:既能体现NFA的各种特性($\varepsilon$转换、多重转换、循环),又不至于大到无法手动分析。通过亲手验证几个字符串,可以极大地加深对NFA计算过程的理解,并暴露出手动模拟时可能犯的错误。

19.6 存在目的

本示例的主要目的有两个:

  1. 提供一个练习: 让读者自己动手,主动地去应用前面学到的NFA计算规则,将知识转化为技能。
  2. 树立一个靶子: 明确提出这个 $N_4$ 将是后续讲解“NFA到DFA转换算法”时要使用的范例。这让读者带着问题和具体的例子去学习接下来的理论,会更有代入感和清晰的目标。

19.7 直觉心智模型

解谜游戏: NFA $N_4$ 就像一个解谜游戏的地图。你(计算分支)是一个探险家。地图上有普通道路(常规转换)和传送门($\varepsilon$转换)。你的任务是根据一串指令(输入字符串 baba)在地图上行走。有些地方你走过去,可能会分裂成好几个你。你的目标是在指令结束时,你(的任何一个分身)恰好站在宝藏室(接受状态1)里。

19.8 直观想象

想象你在一个电话客服系统里。

22. 对"非确定性有限自动机的形式定义"章节的详尽解释

2.1 形式定义前的铺垫

21.1 原文

非确定性有限自动机的形式定义与确定性有限自动机的形式定义类似。两者都具有状态、输入字母表、转换函数、起始状态和接受状态集合。然而,它们在一个基本方面有所不同:转换函数的类型。在DFA中,转换函数接受一个状态和一个输入符号并产生下一个状态。在NFA中,转换函数接受一个状态和一个输入符号或空字符串并产生可能的下一个状态集合。为了编写形式定义,我们需要设置一些额外的符号。对于任何集合$Q$,我们用$\mathcal{P}(Q)$表示$Q$的所有子集集合。这里$\mathcal{P}(Q)$称为$Q$幂集。对于任何字母表$\Sigma$,我们用$\Sigma_{\varepsilon}$表示$\Sigma \cup\{\varepsilon\}$。现在我们可以写出NFA中转换函数类型的形式描述为$\delta: Q \times \Sigma_{\varepsilon} \longrightarrow \mathcal{P}(Q)$

21.2 逐步解释

这段话是给出NFA形式化定义之前的“热身”,它精确地指出了NFA和DFA形式定义上的核心差异所在,并为此引入了两个关键的数学符号。

  1. 相同点:
    • 一个自动机,无论是DFA还是NFA,都是由五个核心部件组成的“五元组”。这五个部件的“角色”是相同的:
    • 状态集 (States): 机器可能处于的所有配置。
    • 字母表 (Alphabet): 机器能读取的所有符号。
    • 转换函数 (Transition Function): 机器的“规则手册”,规定了如何从一个状态到另一个状态。
    • 起始状态 (Start State): 计算开始的地方。
    • 接受状态集 (Set of Accept States): 表示计算成功的终点。
  2. 根本不同点:
    • 差异体现在转换函数 $\delta$ 的定义上。这个函数的输入和输出类型决定了机器是确定性的还是非确定性的。
    • DFA的转换函数 $\delta_{DFA}$:
    • 输入 (Domain): (一个状态, 一个输入符号)。数学表示为 $Q \times \Sigma$
    • 输出 (Range): 一个状态。数学表示为 $Q$
    • 完整描述: $\delta_{DFA}: Q \times \Sigma \longrightarrow Q$。它是一个从“状态-符号对”到“单个状态”的映射。
    • NFA的转换函数 $\delta_{NFA}$:
    • 输入 (Domain): (一个状态, 一个输入符号或ε)
    • 输出 (Range): 一个可能状态的集合
    • 为了形式化地描述这个输入和输出,原文引入了两个新符号。
  3. 新符号的引入:
    • $\Sigma_{\varepsilon}$ (带epsilon的字母表):
    • 定义: $\Sigma_{\varepsilon} = \Sigma \cup \{\varepsilon\}$
    • 目的: 这是为了统一处理NFA的两种转换:由常规输入符号触发的转换和由 $\varepsilon$ 触发的“瞬移”转换。通过扩展字母表,我们可以把 $\varepsilon$ 也看作是一种特殊的“输入”,使得转换函数的定义域更加规整。
    • 所以,NFA转换函数的输入是: $Q \times \Sigma_{\varepsilon}$
    • $\mathcal{P}(Q)$ (Q的幂集, Power Set of Q):
    • 定义: 对于一个集合 $Q$,它的幂集 $\mathcal{P}(Q)$ 是指由 $Q$所有子集构成的集合。
    • 示例: 如果 $Q = \{q_1, q_2\}$,那么它的所有子集是: $\emptyset$ (空集), $\{q_1\}$, $\{q_2\}$, $\{q_1, q_2\}$
    • 因此,$\mathcal{P}(Q) = \{ \emptyset, \{q_1\}, \{q_2\}, \{q_1, q_2\} \}$
    • 目的: 这是为了形式化地表达NFA转换的输出是“一个状态的集合”。当从状态 $q$ 读入符号 $a$ 有多条出路(比如到 $p_1$$p_2$)时,转换函数的输出就是集合 $\{p_1, p_2\}$。如果无路可走,输出就是空集 $\emptyset$。如果只有一条路(比如到 $p_3$),输出就是集合 $\{p_3\}$。这些输出 {p_1, p_2}, \emptyset, {p_3} 都是 $Q$ 的子集,因此它们都是幂集 $\mathcal{P}(Q)$ 中的元素。
    • 所以,NFA转换函数的输出是: $\mathcal{P}(Q)$
  4. NFA转换函数的最终形式:
    • 综合以上分析,NFA的转换函数 $\delta$ 是一个从“状态-符号/$\varepsilon$ 对”到“状态集合”的映射。
    • 其类型签名被精确地描述为:$\delta: Q \times \Sigma_{\varepsilon} \longrightarrow \mathcal{P}(Q)$

21.3 公式与符号逐项拆解和推导

$$ \delta: Q \times \Sigma_{\varepsilon} \longrightarrow \mathcal{P}(Q) $$

与DFA对比:

$$ \delta_{DFA}: Q \times \Sigma \longrightarrow Q $$

通过对比,可以清晰地看到:

  1. DFA的输入不包含 $\varepsilon$
  2. DFA的输出是一个元素 $q \in Q$,而NFA的输出是一个集合 $S \in \mathcal{P}(Q)$ (即 $S \subseteq Q$)。

21.4 具体数值示例

假设一个NFA有 $Q=\{q_1, q_2\}$$\Sigma=\{0, 1\}$

那么 $\Sigma_{\varepsilon} = \{0, 1, \varepsilon\}$

$Q$的幂集 $\mathcal{P}(Q) = \{\emptyset, \{q_1\}, \{q_2\}, \{q_1, q_2\}\}$

一个可能的转换函数 $\delta$ 的具体值可能是:

21.5 易错点与边界情况

21.6 总结

本段落是形式化定义的关键一步。它通过精确定义转换函数 $\delta$ 的输入域 ($Q \times \Sigma_{\varepsilon}$) 和值域 ($\mathcal{P}(Q)$),在数学上捕捉了NFA的两个核心特性:处理 $\varepsilon$ 转换的能力和产生多个后续状态的能力。

21.7 存在目的

在用自然语言描述了NFA的行为之后,计算机科学需要一种无歧义的、数学化的语言来精确定义它。本段的目的就是引入必要的数学工具(幂集、$\Sigma_{\varepsilon}$)来搭建这个形式化框架,为给出完整的NFA五元组定义铺平道路。

21.8 直觉心智模型

从菜单点菜:

21.9 直观想象

想象你在规划一次旅行。

2.2 定义 1.37: NFA的五元组定义

22.1 原文

定义 1.37

非确定性有限自动机是一个5元组$\left(Q, \Sigma, \delta, q_{0}, F\right)$,其中

  1. $Q$是一个有限状态集,
  2. $\Sigma$是一个有限字母表,
  3. $\delta: Q \times \Sigma_{\varepsilon} \longrightarrow \mathcal{P}(Q)$是转换函数,
  4. $q_{0} \in Q$是起始状态,并且
  5. $F \subseteq Q$是接受状态集。

22.2 逐步解释

这是NFA的最终形式化定义,它将NFA精确地定义为一个数学对象。让我们逐一解析这个五元组的每个组成部分。

  1. $Q$ 是一个有限状态集 (a finite set of states)
    • 有限 (finite): 这是“有限自动机”这个名字的来源。机器的“内存”是有限的,它只能处于预先定义好的、数量有限的状态之一。它不能像计算机程序一样拥有无限的内存。
    • 状态集 (set of states): 包含了机器所有可能的情况。例如, $Q = \{q_1, q_2, q_3, q_4\}$
  2. $\Sigma$ 是一个有限字母表 (a finite alphabet)
    • 字母表 (alphabet): 构成输入字符串的基本符号的集合。
    • 有限 (finite): 输入符号的种类是有限的。
    • 例如, $\Sigma = \{0, 1\}$$\Sigma = \{a, b, c\}$
  3. $\delta: Q \times \Sigma_{\varepsilon} \longrightarrow \mathcal{P}(Q)$ 是转换函数 (the transition function)
    • 这是NFA的“大脑”或“规则手册”。
    • 正如我们刚刚详细分析的,它告诉我们:给定一个当前状态和一个输入符号(或$\varepsilon$),机器可以转移到的所有可能状态的集合是什么。
    • 这个定义优雅地将NFA的两个核心特性(多重转换和$\varepsilon$转换)都包含在内。
  4. $q_{0} \in Q$ 是起始状态 (the start state)
    • $q_0$: 特定的一个状态,被指定为所有计算的起点。
    • $\in Q$: 起始状态必须是状态集中的一员。
    • 每个NFA只有一个起始状态。
  5. $F \subseteq Q$ 是接受状态集 (the set of accept states)
    • $F$: 一个状态的集合,可能包含一个、多个或零个状态。
    • $\subseteq Q$: 接受状态必须是状态集中的成员。
    • 接受 (accept): 如果一个输入字符串处理完毕后,NFA的任何一个并行的计算分支停留在 $F$ 中的任何一个状态,那么该字符串就被NFA接受。
    • 接受状态在状态图中通常用双圈表示。

22.3 具体数值示例

以图1.31中的NFA $N_2$ 为例,它的五元组定义是:

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

22.4 易错点与边界情况

22.5 总结

定义1.37提供了一个完整、精确且无歧义的数学框架来描述什么是NFA。它是所有后续关于NFA的严谨讨论和证明的基础。通过这个五元组,任何一个NFA的结构和规则都可以被完全确定下来。

22.6 存在目的

形式化定义的目的是为了消除模糊性,使得理论的构建和推理成为可能。自然语言的描述(如“分裂”、“死亡”)虽然直观,但在数学证明中是不可靠的。这个五元组定义将NFA变成了一个可以被严格操作和分析的数学对象,是计算机科学理论严谨性的体现。

22.7 直觉心智模型

一个棋盘游戏的设计蓝图:

22.8 直观想象

一份DNA序列分析软件的配置:

2.3 示例 1.38: NFA $N_1$ 的形式描述

23.1 原文

例子 1.38

回顾NFA $N_{1}$

$N_{1}$的形式描述是$\left(Q, \Sigma, \delta, q_{1}, F\right)$,其中

  1. $Q=\left\{q_{1}, q_{2}, q_{3}, q_{4}\right\}$
  2. $\Sigma=\{0,1\}$
  3. $\delta$如下所示

| | 0 | 1 | $\boldsymbol{\varepsilon}$ |

| :---: | :---: | :---: | :---: |

| $q_{1}$ | $\left\{q_{1}\right\}$ | $\left\{q_{1}, q_{2}\right\}$ | $\emptyset$ |

| $q_{2}$ | $\left\{q_{3}\right\}$ | $\emptyset$ | $\left\{q_{3}\right\}$ |

| $q_{3}$ | $\emptyset$ | $\left\{q_{4}\right\}$ | $\emptyset$ |

| $q_{4}$ | $\left\{q_{4}\right\}$ | $\left\{q_{4}\right\}$ | $\emptyset$, |

  1. $q_{1}$是起始状态,并且
  2. $F=\left\{q_{4}\right\}$$\square$

23.2 逐步解释

这个例子是将前面给出的NFA $N_1$ 的状态图,严格地翻译成定义1.37所要求的五元组形式。这是在练习如何使用形式化语言来描述一个具体的自动机。

  1. $Q = \{q_1, q_2, q_3, q_4\}$:
    • 这直接从状态图中数出所有的状态圈圈,并把它们的名字放在一个集合里。
  2. $\Sigma = \{0, 1\}$:
    • 这从状态图的转换箭头上收集所有出现过的常规输入符号。
  3. $\delta$ 的表格表示:
    • 转换函数 $\delta$ 是一个函数,它的完整定义需要说明对于 $Q \times \Sigma_{\varepsilon}$ 中的每一个元素,其映射到 $\mathcal{P}(Q)$ 的值是什么。
    • 用一个转换表 (transition table) 是表示 $\delta$ 的一种清晰方式。
    • 表格的行: 代表当前状态 (来自 $Q$)。
    • 表格的列: 代表输入的符号 (来自 $\Sigma_{\varepsilon}$)。
    • 表格的单元格: 包含一个状态的集合,代表 $\delta(\text{行状态}, \text{列符号})$ 的结果。
    • 逐行解读表格:
    • 第一行 ($q_1$):
    • $q_1$ 读 '0',只有一条路回到 $q_1$,所以单元格是 $\{q_1\}$
    • $q_1$ 读 '1',有两条路,一条回 $q_1$,一条去 $q_2$,所以单元格是 $\{q_1, q_2\}$
    • $q_1$ 没有 $\varepsilon$ 转换,所以单元格是空集 $\emptyset$
    • 第二行 ($q_2$):
    • $q_2$ 读 '0',有一条路去 $q_3$,所以单元格是 $\{q_3\}$
    • $q_2$ 读 '1',没有出路,所以单元格是 $\emptyset$
    • $q_2$ 有一条 $\varepsilon$ 转换到 $q_3$,所以单元格是 $\{q_3\}$
    • 第三行 ($q_3$):
    • $q_3$ 读 '0',没有出路,所以单元格是 $\emptyset$
    • $q_3$ 读 '1',有一条路去 $q_4$,所以单元格是 $\{q_4\}$
    • $q_3$ 没有 $\varepsilon$ 转换,所以单元格是 $\emptyset$
    • 第四行 ($q_4$):
    • $q_4$ 读 '0',有一条路回到 $q_4$,所以单元格是 $\{q_4\}$
    • $q_4$ 读 '1',有一条路回到 $q_4$,所以单元格是 $\{q_4\}$
    • $q_4$ 没有 $\varepsilon$ 转换,所以单元格是 $\emptyset$
  4. $q_1$ 是起始状态:
    • 这从状态图中找到那个有“起始”箭头(一个没有起点的箭头)指向的状态。
  5. $F = \{q_4\}$:
    • 这从状态图中找到所有画了双圈的状态。在这个例子里,只有 $q_4$

23.3 具体数值示例

这个例子本身就是一个完整的、将图形转化为形式化描述的示例。它展示了如何将视觉信息(状态图)系统地转换成数学对象(五元组)。

23.4 易错点与边界情况

23.5 总结

示例1.38是一个实践练习,它将一个给定的NFA $N_1$ 的图形表示,严格地翻译成了定义1.37所要求的五元组形式化描述。这巩固了对形式化定义中每个组成部分的理解。

23.6 存在目的

本示例的目的是为了消除理论定义和具体实例之间的隔阂。它向读者展示了抽象的五元组定义是如何与一个具体可见的状态图一一对应的。这使得读者在未来看到一个状态图时,能够在脑中构建出其形式化描述,反之亦然。

23.7 直觉心智模型

填写一份个人信息登记表:

23.8 直观想象

为一部电影编写一个场景分解表:

| 当前场景 | 关键道具/台词 | 下一个可能场景 |

|---|---|---|

| 23. 主角在咖啡馆 | "我必须走了" | { 24. 主角冲出咖啡馆, 25. 主角掏出枪 } |

| 23. 主角在咖啡馆 | (主角看到窗外飞碟) $\varepsilon$ | { 51. 外星人入侵场景 } |

这个例子就是将电影画面(状态图)转换成一份精确的、供剧组执行的表格化文档(五元组)。

2.4 NFA计算的形式化定义

24.1 原文

NFA的形式化计算定义与DFA类似。设$N=\left(Q, \Sigma, \delta, q_{0}, F\right)$是一个NFA,$w$是字母表$\Sigma$上的一个字符串。当我们可以将$w$写成$w=y_{1} y_{2} \cdots y_{m}$,其中每个$y_{i}$$\Sigma_{\varepsilon}$的成员,并且在$Q$中存在一个状态序列$r_{0}, r_{1}, \ldots, r_{m}$,满足三个条件时,我们称$N$接受$w$

  1. $r_{0}=q_{0}$
  2. $r_{i+1} \in \delta\left(r_{i}, y_{i+1}\right)$,对于$i=0, \ldots, m-1$,并且
  3. $r_{m} \in F$

24.2 逐步解释

在用自然语言描述了NFA如何“并行”计算后,这里给出了一个严格的、数学化的计算定义。这个定义没有直接描述“并行”或“状态集合”,而是巧妙地从另一个角度——存在性——来定义接受。

它的核心思想是:一个字符串 $w$ 被接受,当且仅当存在至少一条有效的计算路径,这条路径在消耗完 $w$ 后,最终停留在接受状态。

让我们来分解这个定义:

  1. 字符串的分解:
    • $w = y_1 y_2 \cdots y_m$
    • 这步非常关键。它不是像DFA那样把 $w$ 分解成单个的字母表符号。这里的每个 $y_i$ 都可以是 $\Sigma$ 中的一个符号,也可以是 $\varepsilon$
    • 这意味着我们将一个输入字符串 $w$ 看作是通过插入任意数量的 $\varepsilon$ 得到的序列。
    • 示例: 如果 $w = ab$,那么一种可能的分解是 $y_1=a, y_2=\varepsilon, y_3=b$ (m=3)。另一种是 $y_1=\varepsilon, y_2=a, y_3=b, y_4=\varepsilon$ (m=4)。还有最简单的 $y_1=a, y_2=b$ (m=2)。
  2. 状态序列的存在性:
    • $r_0, r_1, \ldots, r_m$
    • 这是一个状态的序列,它的长度 $m+1$ 必须和分解后的输入序列 $y_1, \ldots, y_m$ 的长度相匹配。
    • $r_i$ 代表了在消耗了前 $i$$y$ 序列符号后,这条特定的计算路径所处的状态。
  3. 三个约束条件:
    • 条件1: $r_0 = q_0$
    • 含义: 这条所谓的“有效计算路径”必须从指定的起始状态 $q_0$ 开始。这是计算的起点。
    • 条件2: $r_{i+1} \in \delta(r_i, y_{i+1})$ for $i=0, \ldots, m-1$
    • 含义: 这是路径的“有效性”检查。它说,从路径的第 $i$ 步状态 $r_i$ 到第 $i+1$ 步状态 $r_{i+1}$ 的转移,必须是合法的。
    • 合法性意味着:$r_{i+1}$ 必须是“在状态 $r_i$ 读取符号 $y_{i+1}$ 后可能到达的状态集合”中的一员。
    • 这个 (属于) 符号是关键。它没有说 $r_{i+1}$ 等于 $\delta(r_i, y_{i+1})$(这在类型上就不匹配),而是说它是该集合中的一个选择。
    • 这完美地捕捉了“非确定性”:我们不关心其他选择,我们只关心我们假设存在的这条路径上的这个选择是不是合法的。
    • 条件3: $r_m \in F$
    • 含义: 这条有效路径的终点,即在处理完整个 $y_1 \cdots y_m$ 序列后的状态 $r_m$,必须是一个接受状态。

总结: NFA接受字符串 $w$,就是说,我们能找到一种方法把 $w$ 插入若干 $\varepsilon$ 变成 $y_1 \cdots y_m$,并且能找到一个对应的状态序列 $r_0 \cdots r_m$,这个序列从起始状态开始,每一步都合法,最终停在接受状态。只要能找到这样一条路径,就算成功。

24.3 公式与符号逐项拆解和推导

$$ w = y_1 y_2 \cdots y_m, \quad y_i \in \Sigma_{\varepsilon} $$

$$ r_{i+1} \in \delta(r_i, y_{i+1}) $$

24.4 具体数值示例

让我们用这个定义来证明 NFA $N_4$ (图1.36) 接受字符串 $w = a$

目标: 证明存在一种分解 $w = y_1 \cdots y_m$ 和一个状态序列 $r_0 \cdots r_m$ 满足三个条件。

  1. 分解 $w$: 我们选择分解 $w = a$$y_1 = \varepsilon, y_2 = a$。这里 $m=2$
  2. 寻找状态序列 $r_0, r_1, r_2$: 我们猜测存在这样一个序列。
    • $r_0$: 根据条件1,必须是起始状态。所以 $r_0 = 1$
    • $r_1$: 根据条件2,必须满足 $r_1 \in \delta(r_0, y_1) = \delta(1, \varepsilon)$。查阅 $N_4$ 的规则,$\delta(1, \varepsilon) = \{3\}$。所以我们可以选择 $r_1 = 3$
    • $r_2$: 根据条件2,必须满足 $r_2 \in \delta(r_1, y_2) = \delta(3, a)$。查阅 $N_4$ 的规则,$\delta(3, a) = \{1\}$。所以我们可以选择 $r_2 = 1$
    • 我们找到了一个候选的状态序列: $r_0=1, r_1=3, r_2=1$
  3. 验证三个条件:
    • 条件1: $r_0 = 1 = q_0$满足
    • 条件2:
    • $i=0$: $r_1 \in \delta(r_0, y_1)$ ? 即 $3 \in \delta(1, \varepsilon)=\{3\}$满足
    • $i=1$: $r_2 \in \delta(r_1, y_2)$ ? 即 $1 \in \delta(3, a)=\{1\}$满足
    • 条件3: $r_m \in F$? 即 $r_2 \in \{1\}$? 也就是 $1 \in \{1\}$满足

结论: 因为我们成功地找到了这样一种分解和一个满足所有三个条件的有效状态序列,所以根据形式化定义,NFA $N_4$ 接受字符串 'a'。

这个定义方式与我们之前“手指模拟”的并行计算模型是等价的。手指模拟追踪的是所有可能的路径,而这个定义则是问:“是否存在至少一条成功的路径?”

24.5 易错点与边界情况

24.6 总结

本段为NFA的计算提供了一个严谨的、基于“存在性证明”的形式化定义。它将“接受”一个字符串等同于“存在一条满足特定条件的、从头走到尾的、成功的计算路径”。

24.7 存在目的

这个形式化定义是进行严格数学证明的基石。例如,要证明NFA和DFA的等价性,我们就需要一个可以被代数式操作的计算定义,而不是“手指模拟”这样的直观描述。这个定义虽然初看起来不如并行模型直观,但在数学上更为便利和严谨。

24.8 直觉心智模型

法庭上的证据链:

  1. 证据链起点 ($r_0=q_0$): 必须从公认的事实(起始状态)开始推理。
  2. 证据链的连续性 ($r_{i+1} \in \delta(r_i, y_{i+1})$): 每一步推理都必须合法。例如,证物A(状态$r_i$)和证人证词(输入$y_{i+1}$)必须能够共同指向嫌疑人可能出现在地点B(状态$r_{i+1}$)。
  3. 证据链的终点 ($r_m \in F$): 整条证据链最终必须指向一个“有罪”的结论(接受状态)。
    • 只要检察官能构建出这样一条无懈可击的证据链,法庭就判决“有罪”(NFA接受)。至于是否存在其他证据链能证明嫌疑人“无罪”(其他的计算路径),在NFA这个“法庭”上是不予考虑的。

24.9 直观想象

在电影剧本里找一条隐藏的故事线:

33. 对"NFA和DFA的等价性"章节的详尽解释

3.1 NFA与DFA的等价性概述

31.1 原文

确定性有限自动机和非确定性有限自动机识别相同类别的语言。这种等价性既令人惊讶又很有用。之所以令人惊讶,是因为NFA似乎比DFA拥有更强大的能力,所以我们可能预期NFA能识别更多的语言。之所以有用,是因为有时为给定语言描述NFA比直接描述DFA要容易得多。

如果两台机器识别相同的语言,我们称它们是等价的。

31.2 逐步解释

这段话提出了计算理论早期的一个核心结论,并阐述了它的重要性。

  1. 核心结论:
    • NFA 和 DFA 在计算能力上是等价的。
    • “计算能力等价”意味着,对于任何一个NFA能够识别的语言,我们保证能找到一个DFA也能识别它;反之亦然。
    • 它们识别的是同一个语言类别,这个类别就是我们之前定义的正则语言 (Regular Languages)
  2. 为何“令人惊讶” (Surprising)?
    • 从直观感觉上看,NFA的能力似乎远超DFA。NFA拥有“分身术”(多重转换)和“瞬移”($\varepsilon$转换),这些都是DFA不具备的超能力。
    • 一个自然而然的猜想是:拥有这些超能力的NFA,应该能解决一些DFA解决不了的复杂问题(即识别一些DFA识别不了的语言)。
    • 然而,结论却是否定的。这些看似强大的能力,并没有让NFA在“能识别什么,不能识别什么”的边界上超越DFA。它只是提供了“如何识别”的另一种、通常更便捷的方式。
    • 这种“直觉与事实的反差”是它令人惊讶的原因。这就好比发现一个会飞的超人,但他能到达的地方,一个会开车的普通人也全都能到,只是方式不同。
  3. 为何“很有用” (Useful)?
    • 这个结论的巨大价值在于它提供了一个“先用NFA,再转DFA”的强大工作流程。
    • 设计阶段: 当面对一个语言时,我们可以利用NFA的灵活性和“猜测”能力,轻松地、直观地设计出一个识别该语言的NFA。如示例1.30所示,设计识别“倒数第三位是1”的NFA易如反掌,而直接设计DFA则困难重重。
    • 实现阶段: 计算机硬件和最简单的模拟程序本质上是确定性的。直接在计算机上实现一个“并行分裂”的NFA是复杂的。但是,由于等价性定理保证了存在一个等价的DFA,我们可以应用一个算法,将我们设计好的简洁NFA自动转换成一个(可能很庞大但行为确定的)DFA。
    • 最终实现: 我们最终在计算机上运行的是这个确定性的DFA。它的行为是线性的、易于编程和高效执行的。
    • 总结: NFA作为高级的设计蓝图,DFA作为可执行的机器码。等价性定理就是连接这两者的“编译器”。
  4. 等价性 (Equivalence) 的定义:
    • 这是一个通用的定义。两台任何类型的计算机器(不限于DFA/NFA),如果它们接受的语言完全相同,即 $L(M_1) = L(M_2)$,那么我们称这两台机器是等价的。

31.3 具体数值示例

31.4 易错点与边界情况

31.5 总结

本段落是整个章节的转折点和核心。它提出了NFA与DFA在计算能力上等价这一关键论断,并解释了这一定理为何既出人意料又极具实用价值。它将NFA定位成一个强大的设计工具,而非一个计算能力更强的模型。

31.6 存在目的

本段的目的是为了引出后续最重要的定理之一——定理1.39(每个NFA都有一个等价的DFA)。它首先建立起读者对“等价性”这一概念的价值认同,让读者明白我们为什么要去证明这样一个看起来有点奇怪的结论,从而激发读者对后续证明过程的兴趣。

31.7 直觉心智模型

建筑师与施工队:

31.8 直观想象

高级菜谱与厨房操作手册:

3.2 定理 1.39: NFA到DFA的转换

32.1 原文

定理 1.39

每个非确定性有限自动机都具有一个等价的确定性有限自动机。

证明思想 如果一种语言被NFA识别,那么我们必须证明存在一个DFA也能识别它。其思想是将NFA转换为一个等价的DFA,该DFA模拟NFA。

回想一下设计有限自动机的“读者即自动机”策略。如果你假装是一个DFA,你将如何模拟NFA?在处理输入字符串时,你需要跟踪什么?在NFA的例子中,你通过在输入中给定点可能活跃的每个状态上放置一个手指来跟踪计算的各种分支。你根据NFA的操作方式通过移动、添加和移除手指来更新模拟。你只需要跟踪有手指的状态集。

如果$k$是NFA的状态数,那么它有$2^{k}$个状态子集。每个子集对应于DFA必须记住的一种可能性,因此模拟NFA的DFA将有$2^{k}$个状态。现在我们需要确定DFA的起始状态和接受状态,以及它的转换函数。在建立一些形式符号之后,我们可以更容易地讨论这个问题。

32.2 逐步解释

这段文字阐述了证明定理1.39的核心思想——子集构造法 (Subset Construction)。这个思想非常巧妙,是计算理论中的经典。

  1. 证明的目标:
    • 给定任意一个NFA(我们称之为 $N$),我们需要构造出一个DFA(我们称之为 $M$),并证明 $M$$N$ 是等价的(即 $L(M) = L(N)$)。
  2. 核心思想:模拟 (Simulation)
    • 这个DFA $M$ 的工作方式,就是去模拟NFA $N$ 的并行计算过程。
    • 我们问自己:作为一个确定性的机器,要如何模拟一个非确定性的、可以“分身”的机器?
    • DFA不能分身,它在任何时刻只能处于一个状态。那么,它的“一个状态”应该代表什么信息,才能完整地捕捉NFA的所有可能性呢?
  3. 关键洞察:“手指模拟法”的升华
    • 回顾我们之前用手指在NFA状态图上模拟计算的过程。在任意时刻,我们的手指可能分布在多个NFA状态上。
    • 真正重要的信息,不是单个手指的位置,而是所有手指所在位置的集合。例如,在某一步,手指们位于 $\{q_1, q_3, q_4\}$。这个集合本身,完整地描述了NFA在这一时刻所有的并行可能性。
    • 灵感来了: 何不让DFA的一个状态就对应NFA的一个状态集合
    • DFA的每一个状态,都是对NFA当前“战局”的一个快照。
  4. 子集构造法的蓝图:
    • DFA的状态是什么?
    • 如果NFA $N$ 的状态集是 $Q$,那么它的任何一个状态子集都可能成为我们手指停留的位置集合。
    • $Q$ 的所有子集的集合,就是我们前面定义的幂集 $\mathcal{P}(Q)$
    • 因此,我们构造的DFA $M$ 的状态集 $Q'$,就应该是 $N$ 的状态集的幂集,即 $Q' = \mathcal{P}(Q)$
    • 如果 $N$$k$ 个状态,那么 $M$ 将有 $2^k$ 个状态。DFA的每个状态都有一个名字,这个名字就是NFA的一个状态子集,例如,DFA可能有一个状态叫 $\{q_1, q_2\}$
    • DFA如何运转?
    • 假设DFA当前处于状态 $R$ (这里 $R$ 是NFA的一个状态子集,比如 $\{q_1, q_2\}$)。
    • 现在DFA读入一个输入符号 $a$
    • DFA需要转移到它的下一个唯一确定的状态。这个新状态是什么呢?
    • 这个新状态,应该是“从原集合 $R$ 中的每一个状态出发,在NFA $N$ 中读取符号 $a$ 后,所有可能到达的新状态的并集”。
    • 例如,从 $q_1$$a$ 可以到 $\{p_1, p_2\}$,从 $q_2$$a$ 可以到 $\{p_2, p_3\}$。那么从 $\{q_1, q_2\}$$a$,就应该到达状态 $\{p_1, p_2\} \cup \{p_2, p_3\} = \{p_1, p_2, p_3\}$
    • 所以,DFA的下一个状态就是这个新的集合 $\{p_1, p_2, p_3\}$
    • DFA的起始状态是什么?
    • NFA从 $q_0$ 开始。但由于可能有$\varepsilon$转换,它在读取任何符号前,可能已经“瞬移”到了其他状态。
    • 所以,DFA的起始状态,应该是NFA起始状态 $q_0$$\varepsilon$-闭包,即从 $q_0$ 出发,只通过$\varepsilon$箭头能到达的所有状态的集合。
    • DFA的接受状态是什么?
    • NFA的接受条件是:只要它所有并行的分支中,有至少一个停留在接受状态。
    • 对应到DFA中,DFA的一个状态 $R$ (它是一个NFA状态的集合),如果这个集合 $R$ 中包含了至少一个NFA的接受状态,那么这个DFA状态 $R$ 就应该是一个接受状态。

32.3 具体数值示例

以NFA $N_4$ (图1.36)为例,它有3个状态 $\{1, 2, 3\}$

$\emptyset$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, $\{1,2,3\}$

$\{1\}$, $\{1,2\}$, $\{1,3\}$, $\{1,2,3\}$

32.4 易错点与边界情况

32.5 总结

“证明思想”部分是整个定理的灵魂。它清晰地阐述了子集构造法的核心逻辑:用DFA的一个确定状态来代表NFA所有并行可能性的集合,并通过模拟NFA在集合上的操作来定义DFA的转换,从而将非确定性的并行计算转换为了确定性的线性计算。

32.6 存在目的

在给出严谨的形式化证明之前,这段“证明思想”起到了一个路线图的作用。它用相对通俗的语言,解释了证明策略的来龙去脉和核心创意,让读者在面对后续充满数学符号的严谨证明时,能够有一个清晰的宏观理解,不至于迷失在细节中。

32.7 直觉心智模型

天气预报系统:

32.8 直观想象

管理一个庞大的情报网络:

3.3 定理1.39证明的逐行详述

33.1 原文

证明$N=\left(Q, \Sigma, \delta, q_{0}, F\right)$是识别语言$A$的NFA。我们构造一个识别$A$的DFA $M=\left(Q^{\prime}, \Sigma, \delta^{\prime}, q_{0}{ }^{\prime}, F^{\prime}\right)$。在进行完整构造之前,我们首先考虑$N$没有$\varepsilon$箭头的简单情况。稍后我们将考虑$\varepsilon$箭头。

  1. $Q^{\prime}=\mathcal{P}(Q)$

$M$的每个状态都是$N$的状态集。回想一下,$\mathcal{P}(Q)$$Q$的子集集。

  1. 对于$R \in Q^{\prime}$$a \in \Sigma$,设$\delta^{\prime}(R, a)=\{q \in Q \mid q \in \delta(r, a) \text{ 对于某个 } r \in R\}$。如果$R$$M$的一个状态,它也是$N$的一个状态集。当$M$在状态$R$中读取符号$a$时,它显示$a$$R$中的每个状态带到何处。由于每个状态可以进入一个状态集,我们取所有这些集合的并集。另一种书写此表达式的方式是

$$ \delta^{\prime}(R, a)=\bigcup_{r \in R} \delta(r, a) . $$

  1. $q_{0}{ }^{\prime}=\left\{q_{0}\right\}$

$M$从仅包含$N$的起始状态的集合所对应的状态开始。

  1. $F^{\prime}=\left\{R \in Q^{\prime} \mid R \text{ 包含 } N \text{ 的一个接受状态}\right\}$

如果$N$在此时可能处于的状态中有一个是接受状态,则机器$M$接受。

[^2]现在我们需要考虑$\varepsilon$箭头。为此,我们设置一些额外的符号。对于$M$的任何状态$R$,我们定义$E(R)$为可以从$R$的成员仅沿着$\varepsilon$箭头到达的状态集合,包括$R$本身的成员。形式上,对于$R \subseteq Q$$E(R)$定义为

$$ E(R)=\{q \mid q \text{ 可以通过沿着0条或更多条 } \varepsilon \text{ 箭头从 } R \text{ 到达}\}。 $$

然后我们修改$M$的转换函数,以便在每一步之后,将额外的“手指”放置在所有可以通过$\varepsilon$箭头到达的状态上。用$E(\delta(r, a))$替换$\delta(r, a)$即可实现此效果。因此

$$ \delta^{\prime}(R, a)=\{q \in Q \mid q \in E(\delta(r, a)) \text{ 对于某个 } r \in R\} \text{。} $$

此外,我们需要修改$M$的起始状态,以将手指最初移动到所有可以通过$\varepsilon$箭头从$N$的起始状态到达的可能状态。将$q_{0}{ }^{\prime}$更改为$E\left(\left\{q_{0}\right\}\right)$即可实现此效果。我们现在已经完成了模拟NFA $N$的DFA $M$的构造。

$M$的构造显然工作正确。在$M$对输入进行计算的每一步中,它都清晰地进入一个状态,该状态对应于$N$在此时可能处于的状态子集。因此,我们的证明完成了。

33.2 逐步解释

这是定理1.39的正式构造性证明。它给出了一个将任何NFA $N$ 转换为等价DFA $M$ 的精确算法。证明分为两步:先处理简单的无 $\varepsilon$ 转换的NFA,再扩展到包含 $\varepsilon$ 转换的通用情况。

第一部分:处理无 $\varepsilon$ 转换的NFA

设NFA $N = (Q, \Sigma, \delta, q_0, F)$。我们要构造DFA $M = (Q', \Sigma, \delta', q_0', F')$

  1. $Q' = \mathcal{P}(Q)$:
    • 构造: DFA $M$ 的状态集 $Q'$ 是NFA $N$ 的状态集 $Q$幂集
    • 解释: $M$ 的每一个状态都是 $N$ 的一个状态子集。$M$ 的一个状态,例如 $R=\{q_1, q_5\}$,代表了NFA $N$ 在某个时刻同时活跃在 $q_1$$q_5$ 这两个状态上。
  2. $\delta'(R, a) = \bigcup_{r \in R} \delta(r, a)$:
    • 构造: DFA $M$ 的转换函数 $\delta'$ 是这样定义的:对于 $M$ 的一个状态 $R$ (它是一个集合) 和一个输入符号 $a$,下一个状态是 $R$ 中每个状态 $r$$N$ 中读 $a$ 后能到达的状态集合的并集
    • 解释: 这完全模拟了NFA的并行计算。如果当前NFA的可能性是集合 $R$,那么在读了 $a$ 之后,新的所有可能性就是把 $R$ 里的每个旧可能性的新去向全部汇集起来。
  3. $q_0' = \{q_0\}$:
    • 构造: DFA $M$ 的起始状态 $q_0'$ 是一个只包含NFA起始状态 $q_0$ 的集合。
    • 解释: 计算开始时,NFA只在它的起始状态 $q_0$ 处活跃。
  4. $F' = \{R \in Q' \mid R \cap F \neq \emptyset \}$:
    • 构造: DFA $M$ 的接受状态集 $F'$ 是所有那些满足“其本身作为集合,与NFA的接受状态集 $F$ 有交集”的 $M$ 的状态 $R$
    • 解释: $M$ 的一个状态 $R$ 是接受状态,当且仅当它所代表的NFA的活跃状态集合 $R$ 中,至少包含一个NFA的接受状态。这与NFA的接受定义完全一致。

第二部分:扩展到带 $\varepsilon$ 转换的通用NFA

现在我们考虑最通用的情况,即NFA $N$ 可以有 $\varepsilon$ 转换。我们需要对上面的构造进行修正。

  1. 引入 $E(R)$ - $\varepsilon$-闭包:
    • 定义: 对于NFA的一个状态集 $R$,它的$\varepsilon$-闭包 $E(R)$ 是指从 $R$ 中的任何一个状态出发,只通过0条或多条 $\varepsilon$ 箭头就能到达的所有状态的集合。
    • “0条”很关键: 这意味着 $R$ 本身的成员也总是在 $E(R)$ 中,即 $R \subseteq E(R)$
    • 解释: $E(R)$ 回答了这样一个问题:“如果NFA的活跃状态是集合 $R$,那么在不读取任何输入的情况下,由于所有可能的瞬移,它瞬间能扩展到的所有活跃状态是什么?”
  2. 修正DFA的构造:
    • $Q' = \mathcal{P}(Q)$: 这一条不变。DFA的状态仍然是NFA状态的子集。
    • 修正 $q_0'$:
    • 新构造: $q_0' = E(\{q_0\})$
    • 解释: DFA的计算始于NFA起始状态 $q_0$ 以及所有能从 $q_0$ 只通过 $\varepsilon$ 箭头到达的状态。这对应NFA计算开始时,在读第一个符号之前发生的所有可能的“瞬移”。
    • 修正 $\delta'$:
    • 新构造: $\delta'(R, a) = E\left( \bigcup_{r \in R} \delta(r, a) \right)$
    • 解释: 这条规则描述了DFA的一步完整转换。可以分解为两步来理解:
  3. 常规转换: 先计算从当前状态 $R$ 中的每个状态 $r$ 读入符号 $a$ 后能到达的状态的并集。我们称这个中间结果为 $R_{next}$。即 $R_{next} = \bigcup_{r \in R} \delta(r, a)$
  4. $\varepsilon$-闭包: 然后,对这个新到达的集合 $R_{next}$,计算它的 $\varepsilon$-闭包。即,DFA的最终下一个状态是 $E(R_{next})$
    • 这完美模拟了NFA的一步:先消耗一个符号进行跳转,然后立即进行所有可能的新“瞬移”。
    • $F'$: 接受状态的定义不变$F' = \{R \in Q' \mid R \cap F \neq \emptyset \}$。无论何时,只要DFA所代表的NFA状态集合中有一个是NFA的接受状态,DFA就处于接受状态。

证明的正确性:

原文最后总结道“构造显然工作正确”。这是因为我们构造的DFA $M$ 的每一个状态和每一步转换,都精确地、确定性地追踪了NFA $N$ 在对应输入下的所有并行可能性的集合。因此,$M$ 在读完一个字符串 $w$ 后所处的状态,恰好就是 $N$ 在读完 $w$ 后所有幸存计算分支所在的状态集合。根据 $F'$ 的定义,$M$ 接受 $w$ 当且仅当这个最终状态集合里包含一个NFA的接受状态,这与NFA的接受定义完全相同。所以,$L(M) = L(N)$

33.3 公式与符号逐项拆解和推导

$$ \delta^{\prime}(R, a)=\bigcup_{r \in R} \delta(r, a) $$

$$ E(R)=\{q \mid q \text{ 可以通过沿着0条或更多条 } \varepsilon \text{ 箭头从 } R \text{ 到达}\} $$

$$ \delta^{\prime}(R, a)= E\left( \bigcup_{r \in R} \delta(r, a) \right) $$

33.4 易错点与边界情况

  1. 确定NFA的 $Q, \Sigma, \delta, q_0, F$
  2. 计算DFA的起始状态 $q_0' = E(\{q_0\})$
  3. $q_0'$ 开始,对字母表中的每个符号,使用 $\delta'$ 的定义计算新的目标状态。
  4. 对于每个新计算出的状态,如果它之前没有出现过,就将它加入一个待处理列表。
  5. 重复步骤3和4,直到没有新的状态产生。这样可以避免生成 $2^k$ 个状态中的大量不可达状态。
  6. 最后,在所有生成的状态中,找出所有与 $F$ 有交集的,标记为接受状态。

33.5 总结

该证明提供了一个将任何NFA(无论有无$\varepsilon$转换)转换为等价DFA的通用算法,即子集构造法。其核心是将NFA的“状态集合”映射为DFA的“单个状态”,并通过$\varepsilon$-闭包来严谨地处理$\varepsilon$转换。

33.6 存在目的

本段的目的是给出定理1.39的严格构造性证明。这个证明不仅证明了定理的正确性,更重要的是,它提供了一个算法。这个算法是理论计算机科学的基石之一,是正则表达式引擎等实际应用中将高级表示(如NFA)编译为低级执行模型(如DFA)的基础。

33.7 直觉心智模型

公司部门重组:

  1. DFA的状态: 大公司的每一个新部门,都是由初创公司里一组有特定技能组合的员工(NFA状态子集)构成的。例如,$\{张三, 李四, 王五\}$ 构成一个新的“核心研发部”。
  2. DFA的起始状态: 创始人团队 $\{q_0\}$ 以及被他们直接影响的核心成员 $E(\{q_0\})$,组成了“CEO办公室”。
  3. DFA的转换: 当接到一个“开发新功能”的任务(输入),“CEO办公室”会分析这个任务会激活初创公司里的哪些员工,以及这些员工又会通过头脑风暴($\varepsilon$转换)影响哪些人,最终形成一个新的人员组合。这个新的人员组合对应大公司里的另一个确定部门,比如“移动开发部”。CEO办公室的工作流程就规定了要转交给“移动开发部”。
  4. DFA的接受状态: 任何包含了“项目经理”(NFA接受状态)这个角色的部门,都被认为是“能交付产品的部门”(DFA接受状态)。

33.8 直观想象

玩一个有雾的即时战略游戏:

  1. 输入: 你派出的侦察机发回了新的战场情报(例如“在坐标(x,y)发现一个兵营”)。
  2. 运算: 你的系统根据这个情报(输入 a)和之前的概率云(状态 $R$),使用贝叶斯推断等算法,确定性地计算出新的概率云(状态 $\delta'(R,a)$)。
    • 你的决策: 你基于这个确定性的、不断演化的概率云图来做出决策。你成功地用一个确定性系统,来模拟和追踪一个对你而言充满不确定性的战场。

3.4 推论 1.40: 正则语言的NFA定义

34.1 原文

推论 1.40

一种语言是正则的当且仅当某个非确定性有限自动机识别它。

“当且仅当”条件的一个方向表明,如果某个NFA识别一种语言,则该语言是正则的。定理1.39表明,任何NFA都可以转换为等价的DFA。因此,如果NFA识别某种语言,那么某个DFA也识别它,因此该语言是正则的。 “当且仅当”条件的另一个方向表明,一种语言是正则的当且仅当某个NFA识别它。也就是说,如果一种语言是正则的,则某个NFA必须识别它。显然,这个条件是正确的,因为正则语言有一个DFA识别它,而任何DFA也是一个NFA。

34.2 逐步解释

这个推论(Corollary)是定理1.39的一个直接且非常重要的逻辑结果。它给了我们一个关于正则语言的全新的、等价的定义。

“当且仅当” (if and only if, iff) 的证明需要从两个方向进行:

方向一: (如果一个语言被NFA识别 $\implies$ 它是正则的)

  1. 前提: 假设我们有一个语言 $L$,并且存在一个NFA $N$ 能够识别它,即 $L(N) = L$
  2. 应用定理1.39: 定理1.39告诉我们,对于任何NFA(包括我们这个 $N$),都存在一个等价的DFA $M$
  3. 等价的含义: $M$$N$ 等价,意味着 $L(M) = L(N)$
  4. 结合: 所以,我们找到了一个DFA $M$,它也能识别语言 $L$ ($L(M)=L$)。
  5. 正则语言的定义: 一个语言如果能被一个DFA识别,那么根据定义,它就是一个正则语言
  6. 结论: 因此,语言 $L$ 是正则的。这个方向的证明完成了。

方向二: (如果一个语言是正则的 $\implies$ 它被某个NFA识别)

  1. 前提: 假设语言 $L$ 是一个正则语言。
  2. 正则语言的定义: 根据正则语言的原始定义,这意味着必然存在一个DFA $D$ 能够识别它,即 $L(D) = L$
  3. DFA与NFA的关系: 我们在前面已经讨论过,任何一个DFA都可以被看作是一个行为非常受限的特殊NFA。
    • 一个DFA的转换 $\delta(q, a) = p$ 可以被写成NFA的形式 $\delta(q, a) = \{p\}$
    • DFA没有 $\varepsilon$ 转换,这在NFA中是允许的(对应的转换输出为空集 $\emptyset$)。
    • 所以,这个DFA $D$ 本身就是一个合法的NFA。
  4. 结论: 因此,我们找到了一个NFA(就是那个DFA $D$ 本身)能够识别语言 $L$。这个方向的证明也完成了。

最终结论: 由于两个方向都得以证明,所以“一种语言是正则的”和“某个NFA识别它”这两个描述是完全等价的。

34.3 具体数值示例

34.4 易错点与边界情况

  1. 一个语言是正则的,当且仅当存在一个DFA识别它。
  2. 一个语言是正则的,当且仅当存在一个NFA识别它。
    • 在未来的证明中,当我们想证明一个语言是正则的时,我们可以自由选择去构造DFA或NFA,哪个方便就用哪个。绝大多数情况下,构造NFA会更简单。

34.5 总结

推论1.40是一个里程碑。它正式确立了NFA作为识别正则语言的“合法工具”,其能力与DFA完全等同。这极大地丰富了我们对正则语言的理解,并为后续的理论和应用提供了更灵活的工具箱。

34.6 存在目的

本推论的目的是将定理1.39的算法性结论,提升到一个概念性的、定义层面的高度。它告诉我们,NFA不仅仅是一种可以转换成DFA的中间工具,它本身就可以作为正则语言的定义性特征。这使得“正则语言”这个概念更加健壮和灵活。

34.7 直觉心智模型

公民身份的认定:

34.8 直观想象

编程语言中的类型等价:

3.5 示例 1.41: NFA到DFA转换实例

35.1 原文

让我们用出现在例1.35中的机器$N_{4}$来说明定理1.39证明中给出的将NFA转换为DFA的过程。为了清晰起见,我们将$N_{4}$的状态重新标记为$\{1,2,3\}$。因此,在$N_{4}=(Q,\{\mathrm{a}, \mathrm{b}\}, \delta, 1,\{1\})$的形式描述中,状态集$Q$$\{1,2,3\}$,如图1.42所示。

为了构造一个等价于$N_{4}$的DFA $D$,我们首先确定$D$的状态。$N_{4}$有三个状态$\{1,2,3\}$,所以我们构造一个有八个状态的$D$,每个状态对应于$N_{4}$状态集的一个子集。我们用相应的子集标记$D$的每个状态。因此$D$的状态集是

$$ \{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\} 。 $$

图 1.42

NFA $N_{4}$

接下来,我们确定$D$的起始状态和接受状态。起始状态是$E(\{1\})$,即可以通过沿着$\varepsilon$箭头从1到达的状态集合,包括1本身。一个$\varepsilon$箭头从1到3,所以$E(\{1\})=\{1,3\}$。新的接受状态是包含$N_{4}$接受状态的那些;因此是$\{\{1\},\{1,2\},\{1,3\},\{1,2,3\}\}$

最后,我们确定$D$的转换函数。$D$的每个状态在输入a上都会到一个位置,在输入b上也会到一个位置。我们用几个例子来说明确定$D$的转换箭头放置的过程。

$D$中,状态$\{2\}$在输入a时会变为$\{2,3\}$,因为在$N_{4}$中,状态2在输入a时会变为2和3,并且我们无法沿着$\varepsilon$箭头从2或3进一步移动。状态$\{2\}$在输入b时会变为状态$\{3\}$,因为在$N_{4}$中,状态2在输入b时只变为状态3,并且我们无法沿着$\varepsilon$箭头从3进一步移动。

状态$\{1\}$在a上变为$\emptyset$,因为没有a箭头从它射出。它在b上变为$\{2\}$。请注意,定理1.39中的过程规定,我们应该在读取每个输入符号后跟随$\varepsilon$箭头。另一种基于在读取每个输入符号前跟随$\varepsilon$箭头的方法同样有效,但该方法未在此示例中说明。

状态$\{3\}$在a上变为$\{1,3\}$,因为在$N_{4}$中,状态3在a上变为1,而1又通过$\varepsilon$箭头变为3。状态$\{3\}$在b上变为$\emptyset$

状态$\{1,2\}$在a上变为$\{2,3\}$,因为1没有a箭头指向任何状态,2有a箭头指向2和3,并且两者都没有$\varepsilon$箭头指向任何地方。状态$\{1,2\}$在b上变为$\{2,3\}$。以这种方式继续,我们得到图1.43所示的$D$的图。

图 1.43

等价于NFA $N_{4}$的DFA $D$

我们可以通过观察状态$\{1\}$$\{1,2\}$没有箭头指向它们来简化这台机器,这样就可以移除它们而不影响机器的性能。这样做会产生下图。

图 1.44

移除不必要状态后的DFA $D$

35.2 逐步解释

这个例子是子集构造算法的完整演练。它把前面抽象的算法步骤,应用到了具体的NFA $N_4$ 上。

第0步: 准备工作

第1步: 确定DFA $D$ 的状态集 $Q'$

第2步: 确定DFA $D$ 的起始状态 $q_0'$ 和接受状态 $F'$

第3步: 确定DFA $D$ 的转换函数 $\delta'$

这是最核心的计算步骤。我们将系统地计算从每个可达状态出发的转换。

第4步: 整合与简化

35.3 易错点与边界情况

35.4 总结

这个例子通过一个完整的、手把手的计算过程,将抽象的子集构造算法具体化。它展示了如何系统地确定DFA的状态、起始状态、接受状态和每一个转换,并解释了为何最终的DFA会比理论上的 $2^k$ 个状态要少(因为有些状态不可达)。

35.5 存在目的

本示例的目的是为了让读者真正掌握NFA到DFA的转换算法。理论和思想是基础,但只有通过一个完整的实例演练,才能发现并理解算法中的所有细节和关键点。它充当了连接理论证明和实际应用之间的桥梁。

35.6 直觉心智模型

制作一本NFA的“傻瓜操作手册” (即DFA):

35.7 直观想象

为一部多人实时互动的电影制作一个“导演剪辑版”:

44. 对"正则运算下的闭包"章节的详尽解释

4.1 闭包概念回顾

41.1 原文

现在我们回到第1.1节开始讨论的正则语言类别在正则运算下的闭包。我们的目标是证明正则语言的并集、连接和星运算仍然是正则的。在处理连接运算过于复杂时,我们放弃了最初的尝试。非确定性的使用使证明变得容易得多。

41.2 逐步解释

这段话是一个引子,旨在将我们的注意力重新拉回到一个早期提出的重要主题上:闭包性质 (Closure Properties)

  1. 闭包是什么?
    • 在数学中,一个集合在某个运算下“封闭”,是指对集合中的成员进行该运算,得到的结果仍然在该集合内。
    • 示例:
    • 整数集合在加法运算下是封闭的,因为任何两个整数相加,结果仍然是一个整数。
    • 整数集合在除法运算下是不封闭的,因为 1 除以 2 等于 0.5,结果不是整数。
  2. 正则语言的闭包:
    • 在这里,我们的“集合”不是指数字,而是指所有正则语言构成的无限集合。我们称这个集合为“正则语言类”。
    • 我们的“运算”不是加减乘除,而是我们在1.1节定义的正则运算
    • 并集 (Union): $A \cup B$
    • 连接 (Concatenation): $A \circ B$
    • 星号 (Star): $A^*$
    • “正则语言类在并集运算下是封闭的”这句话的意思是:如果 $A_1$ 是一个正则语言,并且 $A_2$ 也是一个正则语言,那么它们的并集 $A_1 \cup A_2$ 保证也一定是一个正则语言。
    • 同理,闭包性质也适用于连接和星号运算。
  3. 证明目标:
    • 本节的目标就是去严格地证明这三个闭包性质。
    • 如何证明一个语言是正则的?根据我们目前的知识,只要能为它构建一个 DFANFA,就能证明它是正则的。
  4. 新工具的威力:
    • 原文提到“在处理连接运算过于复杂时,我们放弃了最初的尝试”。这指的是在只了解DFA的时候,想要构造一个识别 $A_1 \circ A_2$ 的DFA是非常困难的(需要复杂的“猜测”逻辑,而DFA不擅长猜测)。
    • 现在我们有了NFA这个强大的新工具,特别是它自带的“猜测”(非确定性)和“免费跳转”($\varepsilon$转换)能力。
    • 作者暗示,使用NFA,证明这些闭包性质将会变得“容易得多”。这预示着我们将看到一系列非常巧妙和直观的构造方法。

41.3 具体数值示例

41.4 易错点与边界情况

41.5 总结

本段是一个承前启后的引言。它重申了证明正则运算闭包性的目标,并强调了NFA将是完成这一目标的关键武器,因为它能用非常直观的方式来处理像“或”(并集)、“然后”(连接)、“重复”(星号)这样的逻辑。

41.6 存在目的

此段的目的是为了设置舞台,提醒读者我们即将解决一个之前遗留下的重要问题。它通过对比使用DFA的困难和使用NFA的便捷,来进一步强化NFA作为一个优秀理论工具的形象,并为接下来的一系列基于NFA的构造性证明做好铺垫。

41.7 直觉心智模型

乐高积木世界:

41.8 直观想象

软件工程中的库函数:

4.2 定理 1.45: 并集闭包性 (NFA证法)

42.1 原文

定理 1.45

正则语言类别在并集运算下是封闭的。

证明思想 我们有正则语言$A_{1}$$A_{2}$,并希望证明$A_{1} \cup A_{2}$是正则的。其思想是取两个识别$A_{1}$$A_{2}$的NFA $N_{1}$$N_{2}$,并将它们组合成一个新的NFA $N$

机器$N$必须在$N_{1}$$N_{2}$接受其输入时接受其输入。新机器有一个新的起始状态,它通过$\varepsilon$箭头分支到旧机器的起始状态。通过这种方式,新机器非确定性地猜测哪台机器接受输入。如果其中一台接受输入,$N$也会接受它。

我们用下图表示这个构造。左侧,我们用大圆圈表示机器$N_{1}$$N_{2}$的起始状态和接受状态,用小圆圈表示一些附加状态。右侧,我们展示了如何通过添加额外的转换箭头将$N_{1}$$N_{2}$组合成$N$

图 1.46

构造NFA $N$以识别$A_{1} \cup A_{2}$

图 1.46

构造NFA $N$以识别$A_{1} \cup A_{2}$

42.2 逐步解释

这个证明过程完美地体现了NFA在设计上的“模块化”和“优雅”。

  1. 证明的起点:
    • 我们已知 $A_1$$A_2$ 是正则语言。
    • 根据推论1.40(一个语言是正则的当且仅当有NFA识别它),这意味着必然存在两个NFA,我们称它们为 $N_1$$N_2$,使得 $L(N_1) = A_1$$L(N_2) = A_2$
  2. 证明的目标:
    • 我们要证明 $A_1 \cup A_2$ 也是正则语言。
    • 这意味着我们需要构造一个新的自动机(最好是NFA,因为更简单),我们称之为 $N$,使得 $L(N) = A_1 \cup A_2$
  3. 构造思想——“二选一”:
    • 语言 $A_1 \cup A_2$ 的定义是:一个字符串 $w$ 属于这个并集,当且仅当 $w \in A_1$ 或者 $w \in A_2$
    • 我们希望新机器 $N$ 能够模拟这个“或者”的逻辑。
    • NFA的非确定性是实现“或者”逻辑的完美工具。
    • 核心创意:
  4. 创建一个全新的起始状态 $q_0$
  5. 从这个新起点 $q_0$ 出发,画两条$\varepsilon$箭头,一条指向 $N_1$ 的原始起始状态 $q_1$,另一条指向 $N_2$ 的原始起始状态 $q_2$
  6. $N_1$$N_2$ 的所有状态和转换原封不动地搬过来。
  7. 新机器 $N$ 的接受状态,就是 $N_1$ 的所有接受状态并上 $N_2$ 的所有接受状态。
  8. 这个构造如何工作?
    • 当输入一个字符串 $w$ 给新机器 $N$ 时,计算从 $q_0$ 开始。
    • 在读取任何符号之前,由于有两条 $\varepsilon$ 箭头,计算立即分裂成两个并行的“超级分支”:
    • 一个分支跳转到 $N_1$ 的起点 $q_1$,然后完全按照 $N_1$ 的规则$N_1$ 的“世界”里运行。
    • 另一个分支跳转到 $N_2$ 的起点 $q_2$,然后完全按照 $N_2$ 的规则$N_2$ 的“世界”里运行。
    • 这两个超级分支是并行的,互不干扰。
    • 如果 $w \in A_1$: 那么在 $N_1$ 世界里运行的那个分支,在消耗完 $w$ 后,最终会停留在 $N_1$ 的某个接受状态上。由于 $N_1$ 的接受状态也是 $N$ 的接受状态,所以整个机器 $N$ 接受 $w$
    • 如果 $w \in A_2$: 同理,在 $N_2$ 世界里运行的那个分支会成功,导致 $N$ 接受 $w$
    • 如果 $w$ 既不属于 $A_1$ 也不属于 $A_2$: 那么两个分支都会失败,最终 $N$ 拒绝 $w$
    • 这个构造完美地用NFA的并行计算模拟了语言的并集运算。
  9. 图示解读 (图1.46):
    • 左侧的两个虚线框代表现成的两个NFA,$N_1$$N_2$
    • 右侧展示了新NFA $N$ 的构造:
    • 创建了新的起始状态 $q_0$
    • 用两条 $\varepsilon$ 箭头将 $q_0$$N_1$$N_2$ 的旧起始状态连接起来。
    • $N_1$$N_2$ 的接受状态(双圈)在 $N$ 中仍然是接受状态。

42.3 具体数值示例

  1. 新起始状态 $q_0$
  2. $\varepsilon$ 转换: $q_0 \to q_{10}$$q_0 \to q_{20}$
  3. 保留 $N_1$$N_2$ 的所有其他转换。
  4. $N$ 的接受状态集是 $\{q_{1f}, q_{2f}\}$
    • 模拟输入 aba:
  5. 开始于 $q_0$,立即分裂到 $\{q_{10}, q_{20}\}$
  6. 读 'a': 从 $q_{10} \to \{q_{10}, q_{1f}\}$。从 $q_{20} \to \{q_{20}\}$。活跃状态 $\{q_{10}, q_{1f}, q_{20}\}$
  7. 读 'b': 从 $q_{10} \to \{q_{10}\}$。从 $q_{1f}$ 死亡。从 $q_{20} \to \{q_{20}, q_{2f}\}$。活跃状态 $\{q_{10}, q_{20}, q_{2f}\}$
  8. 读 'a': 从 $q_{10} \to \{q_{10}, q_{1f}\}$。从 $q_{20} \to \{q_{20}\}$。从 $q_{2f}$ 死亡。活跃状态 $\{q_{10}, q_{1f}, q_{20}\}$
  9. 输入结束。最终活跃状态包含 $q_{1f}$,它是接受状态。
  10. 结论: 接受 aba (正确)。

42.4 易错点与边界情况

42.5 总结

定理1.45的证明是展示NFA威力的一个典范。它通过一个极其简单和直观的“添加新起点和两条$\varepsilon$分支”的构造,优雅地解决了正则语言的并集闭包问题。这个方法具有普适性,可以应用于任何两个NFA。

42.6 存在目的

本段的目的是提供一个相较于DFA证法更简洁、更强大的证明,以此来:

  1. 巩固读者对NFA非确定性和 $\varepsilon$ 转换的理解和应用。
  2. 严格地证明正则语言在并集运算下的闭包性。
  3. 为后续证明连接和星号闭包性建立信心,并展示一种通用的“模块化拼接”NFA的证明思路。

42.7 直觉心智模型

电影院排片:

  1. 新起点: 电影院的入口大厅 $q_0$
  2. $\varepsilon$ 转换: 大厅里有两个门,一个门上写着“《黑客帝国》由此进”,另一个写着“《阿凡达》由此进”。观众可以自由选择进哪个门。
  3. 运行: 观众进入一个厅后,就完整地观看那部电影。
  4. $N$ 接受: 只要观众觉得他看的那部电影好看(无论他选的是哪部),对于电影院来说,这次服务就算成功了。
    • 这个电影院的设计,完美地服务了想看《黑客帝国》《阿凡达》的观众。

42.8 直观想象

电路设计:

  1. 新起点: 一个输入端子 $q_0$
  2. $\varepsilon$ 转换: 从 $q_0$ 出来,接一个“信号分配器”,把输入的脉冲信号同时复制给 $N_1$ 的输入端和 $N_2$ 的输入端。
  3. 接受状态: $N_1$$N_2$ 各自有一个“成功”指示灯。把这两个灯的输出接到一个“或门”上。
  4. $N$ 接受: 只要有任何一个指示灯亮了,“或门”就会输出高电平,表示整合电路识别成功。

4.3 定理1.45的证明

43.1 原文

证明

$N_{1}=\left(Q_{1}, \Sigma, \delta_{1}, q_{1}, F_{1}\right)$识别$A_{1}$,且$N_{2}=\left(Q_{2}, \Sigma, \delta_{2}, q_{2}, F_{2}\right)$识别$A_{2}$

构造$N=\left(Q, \Sigma, \delta, q_{0}, F\right)$来识别$A_{1} \cup A_{2}$

  1. $Q=\left\{q_{0}\right\} \cup Q_{1} \cup Q_{2}$

$N$的状态是$N_{1}$$N_{2}$的所有状态,加上一个新的起始状态$q_{0}$

  1. 状态$q_{0}$$N$的起始状态。
  2. 接受状态集$F=F_{1} \cup F_{2}$

$N$的接受状态是$N_{1}$$N_{2}$的所有接受状态。这样,$N$$N_{1}$$N_{2}$接受时接受。

  1. 定义$\delta$,使得对于任何$q \in Q$和任何$a \in \Sigma_{\varepsilon}$

$$ \delta(q, a)= \begin{cases}\delta_{1}(q, a) & q \in Q_{1} \\ \delta_{2}(q, a) & q \in Q_{2} \\ \left\{q_{1}, q_{2}\right\} & q=q_{0} \text{ 且 } a=\varepsilon \\ \emptyset & q=q_{0} \text{ 且 } a \neq \varepsilon \text{。}\end{cases} $$

43.2 逐步解释

这是对“证明思想”的形式化描述,将直观的构造方法翻译成严谨的数学语言。

  1. $Q = \{q_0\} \cup Q_1 \cup Q_2$:
    • 构造: 新NFA的状态集 $Q$$N_1$ 的状态集、$N_2$ 的状态集、以及一个全新的状态 $q_0$ 的并集。
    • 解释: 我们把两台旧机器的全部状态都“倒进”新机器的“池子”里,再额外加一个状态 $q_0$ 作为总开关。
  2. 状态 $q_0$ 是N的起始状态:
    • 构造: 明确指定我们新加入的 $q_0$ 为唯一的起始状态。
    • 解释: 计算必须从这个新的、中立的起点开始。
  3. $F = F_1 \cup F_2$:
    • 构造: 新NFA的接受状态集 $F$,是 $N_1$ 的接受状态集和 $N_2$ 的接受状态集的并集。
    • 解释: 只要计算最终停在任何一个旧机器的接受状态上,新机器就算接受。
  4. $\delta$ 的定义:
    • 这是一个分情况定义的函数,它描述了新机器的全部“接线规则”。
    • 情况一: $q \in Q_1$: 如果当前状态是 $N_1$ 里的一个状态,那么它的行为就完全遵循 $N_1$ 原来的规则。即 $\delta(q, a) = \delta_1(q, a)$。这意味着在 $N_1$ 的“领地”内,一切照旧。
    • 情况二: $q \in Q_2$: 同理,如果当前状态是 $N_2$ 里的一个状态,它的行为完全遵循 $N_2$ 原来的规则。即 $\delta(q, a) = \delta_2(q, a)$
    • 情况三: $q = q_0$$a = \varepsilon$: 这是最关键的“接线”。如果当前状态是新的起始状态 $q_0$,并且是“免费的” $\varepsilon$ 转换,那么它将转移到包含两个旧起始状态的集合 $\{q_1, q_2\}$。这就是实现“兵分两路”的核心。
    • 情况四: $q = q_0$$a \neq \varepsilon$: 如果在起始状态 $q_0$ 想要消耗一个常规符号,我们定义其无路可走,即转移到空集 $\emptyset$。这意味着 $q_0$ 的唯一作用就是通过 $\varepsilon$ 实现初始的分裂,它不处理任何实际的输入。

43.3 公式与符号逐项拆解和推导

$$ \delta(q, a)= \begin{cases}\delta_{1}(q, a) & q \in Q_{1} \\ \delta_{2}(q, a) & q \in Q_{2} \\ \left\{q_{1}, q_{2}\right\} & q=q_{0} \text{ 且 } a=\varepsilon \\ \emptyset & q=q_{0} \text{ 且 } a \neq \varepsilon \text{。}\end{cases} $$

43.4 总结

这段证明将并集构造的思想,用NFA五元组的语言进行了精确、无歧义的描述。它给出了一个将两个NFA合并成一个识别其语言并集的新NFA的通用算法。

43.5 存在目的

此段的目的是提供一个严格的、可供审查的数学证明。在科学和数学中,直观的思想需要形式化的语言来固定和验证。这个形式化证明确保了图1.46所示的构造方法在逻辑上是完备和正确的,适用于任何NFA,没有任何隐藏的漏洞。

4.4 定理 1.47: 连接闭包性

44.1 原文

定理 1.47

正则语言类别在连接运算下是封闭的。

证明思想 我们有正则语言$A_{1}$$A_{2}$,并希望证明$A_{1} \circ A_{2}$是正则的。其思想是取两个识别$A_{1}$$A_{2}$的NFA $N_{1}$$N_{2}$,并将它们组合成一个新的NFA $N$,就像我们在并集情况下所做的那样,但这次以不同的方式,如图1.48所示。

$N$的起始状态指定为$N_{1}$的起始状态。$N_{1}$的接受状态具有额外的$\varepsilon$箭头,当$N_{1}$处于接受状态时,这些箭头非确定性地允许分支到$N_{2}$,这表示它已找到了构成$A_{1}$中字符串的输入初始部分。$N$的接受状态仅为$N_{2}$的接受状态。因此,当输入可以分成两部分,第一部分被$N_{1}$接受,第二部分被$N_{2}$接受时,它才接受。我们可以将$N$视为非确定性地猜测在哪里进行分割。

图 1.48

构造$N$以识别$A_{1} \circ A_{2}$

44.2 逐步解释

这个证明展示了如何用NFA来巧妙地处理“顺序”或“然后”的逻辑。

  1. 证明的起点与目标:
    • 起点: 已知 $A_1, A_2$ 是正则语言,所以存在NFA $N_1, N_2$ 分别识别它们。
    • 目标: 证明 $A_1 \circ A_2$ 也是正则的。我们需要构造一个NFA $N$ 来识别它。
  2. 连接的定义:
    • 语言 $A_1 \circ A_2$ 包含所有形如 $xy$ 的字符串,其中 $x$ 来自 $A_1$$y$ 来自 $A_2$
    • 这意味着输入字符串必须能被分割成两部分,第一部分被 $N_1$ 接受,紧接着的第二部分被 $N_2$ 接受。
  3. 构造思想——“接力跑”:
    • 这个问题的核心在于,机器不知道在哪里分割字符串才是正确的。例如,对于输入 abcde,分割点可能在 a|bcde, ab|cde, abc|de...
    • NFA的非确定性可以完美解决这个“猜测分割点”的问题。
    • 核心创意:
  4. 起点: 将 $N_1$ 的起始状态 $q_1$ 直接作为新机器 $N$ 的起始状态。计算从 $N_1$ 开始。
  5. 接力棒: 从 $N_1$每一个接受状态,画一条 $\varepsilon$ 箭头,指向 $N_2$ 的起始状态 $q_2$
  6. 终点: 新机器 $N$ 的接受状态,仅仅$N_2$ 的接受状态。$N_1$ 原来的接受状态在 $N$ 中不再是最终的接受状态(它们变成了“中继站”)。
  7. 这个构造如何工作?
    • 当输入字符串 $w$ 时,计算从 $N_1$ 的起点 $q_1$ 开始。
    • 机器首先在 $N_1$ 的世界里运行。
    • 假设 $w=xy$。当机器处理完 $x$ 部分后,如果 $x$$A_1$ 的一个成员,那么 $N_1$ 的某个计算分支会到达一个 $N_1$ 的接受状态(比如 $f_1 \in F_1$)。
    • 非确定性的猜测: 在这个接受状态 $f_1$,机器面临一个选择:
    • 选择一: 如果 $x$ 不是 $w$ 的前缀(即后面还有字符),并且 $N_1$$f_1$ 还可以继续读字符,那么就继续在 $N_1$ 中运行。这对应“猜测分割点在后面”。
    • 选择二: 通过从 $f_1$$q_2$$\varepsilon$ 箭头,“免费”地、瞬间地跳转到 $N_2$ 的起点 $q_2$。这对应“猜测到这里 ($x$ 结束处) 就是正确的分割点”。
    • 接力: 一旦一个分支跳转到了 $q_2$,它就开始在 $N_2$ 的世界里处理字符串剩下的 $y$ 部分。
    • 冲过终点: 如果这个分支在处理完 $y$ 之后,恰好停在了 $N_2$ 的一个接受状态上,那么由于 $N_2$ 的接受状态也是 $N$ 的接受状态,整个机器 $N$ 接受字符串 $w$
    • NFA会为输入字符串的每一个可能的前缀 $x$ ที่被 $N_1$ 接受的地方,都进行一次这样的“接力”尝试。只要有任何一次尝试成功了(即剩下的后缀 $y$ 也被 $N_2$ 接受),整个字符串就被接受。
  8. 图示解读 (图1.48):
    • $N_1$$N_2$ 被串联了起来。
    • $N$ 的起点就是 $N_1$ 的起点。
    • $N_1$ 的所有接受状态(双圈)都有一条 $\varepsilon$ 箭头指向 $N_2$ 的起始状态。
    • $N$ 的终点(接受状态)只有 $N_2$ 的那些接受状态。

44.3 具体数值示例

  1. 起始状态是 $q_1$
  2. $N_1$ 的接受状态 $f_1$ 画一条 $\varepsilon$ 箭头到 $N_2$ 的起始状态 $q_2$
  3. $N$ 的接受状态只有 $f_2$
    • 模拟输入 ab:
  4. 开始于 $q_1$
  5. 读 'a',从 $q_1 \to f_1$。当前活跃状态 $\{f_1\}$
  6. $f_1$,有一个 $\varepsilon$ 转换到 $q_2$。立即分裂,活跃状态变为 $\{f_1, q_2\}$
  7. 读 'b':
    • $f_1$ 无路,死亡。
    • $q_2 \to f_2$
  8. 新的活跃状态是 $\{f_2\}$
  9. 输入结束。最终状态 $f_2$ 是接受状态。
  10. 结论: 接受 ab (正确)。
    • 模拟输入 a:
  11. ...处理完 'a' 后,活跃状态是 $\{f_1, q_2\}$
  12. 输入结束。检查集合 $\{f_1, q_2\}$$f_1$ 不是 $N$ 的接受状态, $q_2$ 也不是。
  13. 结论: 拒绝 a (正确)。

44.4 易错点与边界情况

44.5 总结

定理1.47的证明思想是另一个NFA构造的杰作。它用一个简单的“$\varepsilon$桥梁”将两台机器串联起来,实现了“第一部分由A处理,第二部分由B处理”的连接逻辑。NFA的非确定性自动地探索了所有可能的分割点,大大简化了构造。

44.6 存在目的

本段旨在证明正则语言对连接运算的闭包性。与并集证明类似,它再次凸显了NFA作为模块化设计工具的优越性,并展示了与“或”逻辑不同的、“顺序”逻辑的构造技巧。这为最终通过归纳法证明所有正则表达式都对应一个NFA(Kleene定理的一部分)铺平了道路。

44.7 直觉心智模型

生产流水线:

44.8 直观想象

写一本书的两个章节:

4.5 定理1.47的证明

45.1 原文

证明

$N_{1}=\left(Q_{1}, \Sigma, \delta_{1}, q_{1}, F_{1}\right)$识别$A_{1}$,且

$$ N_{2}=\left(Q_{2}, \Sigma, \delta_{2}, q_{2}, F_{2}\right) \text{ 识别 } A_{2} \text{。} $$

构造$N=\left(Q, \Sigma, \delta, q_{1}, F_{2}\right)$来识别$A_{1} \circ A_{2}$

  1. $Q=Q_{1} \cup Q_{2}$

$N$的状态是$N_{1}$$N_{2}$的所有状态。

  1. 状态$q_{1}$$N_{1}$的起始状态相同。
  2. 接受状态$F_{2}$$N_{2}$的接受状态相同。
  3. 定义$\delta$,使得对于任何$q \in Q$和任何$a \in \Sigma_{\varepsilon}$

$$ \delta(q, a)= \begin{cases}\delta_{1}(q, a) & q \in Q_{1} \text{ 且 } q \notin F_{1} \\ \delta_{1}(q, a) & q \in F_{1} \text{ 且 } a \neq \varepsilon \\ \delta_{1}(q, a) \cup\left\{q_{2}\right\} & q \in F_{1} \text{ 且 } a=\varepsilon \\ \delta_{2}(q, a) & q \in Q_{2} \text{。}\end{cases} $$

45.2 逐步解释

这是对连接构造思想的形式化描述。

  1. $Q = Q_1 \cup Q_2$:
    • 构造: 新NFA的状态集是 $N_1$$N_2$ 状态集的并集。这次我们不需要新的起始状态。
    • 解释: 我们只是把两台机器的状态“焊接”在一起。
  2. 状态 $q_1$$N$ 的起始状态:
    • 构造: 新NFA的起始状态直接沿用 $N_1$ 的起始状态 $q_1$
    • 解释: 计算必须从第一台机器开始。
  3. $F_2$$N$ 的接受状态集:
    • 构造: 新NFA的接受状态集直接沿用 $N_2$ 的接受状态集 $F_2$
    • 解释: 只有当计算在第二台机器的世界里成功时,整个过程才算成功。
  4. $\delta$ 的定义:
    • 这个定义比并集的稍微复杂,需要仔细解读。
    • 情况一: $q \in Q_1$$q \notin F_1$: 如果当前状态 $q$$N_1$ 里的一个普通(非接受)状态,那么它的行为完全遵循 $N_1$ 的规则,即 $\delta(q,a) = \delta_1(q,a)$
    • 情况二: $q \in F_1$$a \neq \varepsilon$: 如果当前状态 $q$$N_1$ 的一个接受状态,并且要读取一个常规符号 $a$,它的行为也遵循 $N_1$ 的旧规则 $\delta_1(q,a)$。这对应了“猜测分割点在后面,继续在 $N_1$ 里跑”的情况。
    • 情况三: $q \in F_1$$a = \varepsilon$: 这是最关键的连接点。如果当前状态 $q$$N_1$ 的一个接受状态,并且是$\varepsilon$转换,那么它的新去向是 $N_1$ 原来的 $\varepsilon$ 去向($\delta_1(q,\varepsilon)$并上 $N_2$ 的起始状态 $\{q_2\}$。这就是“交接力棒”的动作:在 $N_1$ 的一个成功节点,免费跳转到 $N_2$ 的起点。
    • 情况四: $q \in Q_2$: 一旦进入了 $N_2$ 的世界($q$$N_2$ 的状态),计算就再也回不到 $N_1$ 了。它的所有行为都完全遵循 $N_2$ 的规则,即 $\delta(q,a) = \delta_2(q,a)$

注意: 这个教科书原文的 $\delta$ 定义有一种更简洁的等价写法:

  1. 对于 $q \in Q_1$$q \notin F_1$, $\delta(q,a) = \delta_1(q,a)$
  2. 对于 $q \in F_1$, $\delta(q,\varepsilon) = \delta_1(q,\varepsilon) \cup \{q_2\}$。对于 $a \neq \varepsilon$, $\delta(q,a) = \delta_1(q,a)$
  3. 对于 $q \in Q_2$, $\delta(q,a) = \delta_2(q,a)$

这与原文的定义是等价的,可能更容易理解。

45.3 公式与符号逐项拆解和推导

$$ \delta(q, a)= \begin{cases}\dots \\ \delta_{1}(q, a) \cup\left\{q_{2}\right\} & q \in F_{1} \text{ 且 } a=\varepsilon \\ \dots\end{cases} $$

45.4 总结

这段形式化证明精确地描述了如何修改两台NFA的转换函数,以实现“串联”的效果。核心在于修改第一台机器的接受状态,使其在遇到 $\varepsilon$ 转换时,额外增加一条通往第二台机器起点的路径。

4.6 定理 1.49: 星号闭包性

46.1 原文

定理 1.49

正则语言类别在星运算下是封闭的。

证明思想 我们有一个正则语言$A_{1}$,并希望证明$A_{1}^{*}$也是正则的。我们取一个识别$A_{1}$的NFA $N_{1}$,并修改它以识别$A_{1}^{*}$,如下图所示。生成的NFA $N$将在输入可以分成几部分且$N_{1}$接受每部分时接受其输入。

我们可以构造$N$$N_{1}$一样,但在接受状态处增加额外的$\varepsilon$箭头返回到起始状态。这样,当处理到达$N_{1}$接受的一个片段的末尾时,机器$N$可以选择跳回到起始状态,尝试读取$N_{1}$接受的另一个片段。此外,我们必须修改$N$以使其接受$\varepsilon$,而$\varepsilon$始终是$A_{1}^{*}$的成员。一个(稍微不太好)的想法是简单地将起始状态添加到接受状态集。这种方法当然会将$\varepsilon$添加到识别的语言中,但它也可能添加其他不希望的字符串。练习1.15要求举例说明这种想法的失败。解决方法是添加一个新的起始状态,该状态也是接受状态,并且具有一个指向旧起始状态的$\varepsilon$箭头。这个解决方案具有在不添加任何其他内容的情况下将$\varepsilon$添加到语言中的期望效果。

图 1.50

构造$N$以识别$A^{*}$

46.2 逐步解释

星号运算是最有趣的,它的构造也最巧妙。

  1. 星号的定义:
    • $A^*$ 是由 $A$ 中的字符串任意连接0次或多次形成的所有字符串的集合。
    • $A^* = A^0 \cup A^1 \cup A^2 \cup \dots$
    • $A^0 = \{\varepsilon\}$ (连接0次,得到空字符串)。
    • $A^1 = A$
    • $A^2 = A \circ A$
    • ...
  2. 构造思想——“循环播放”与“跳过”:
    • 识别 $A^*$ 的机器需要处理两件事:
  3. 重复: 能够识别 $A$ 中的一个字符串后,能“重置”自己,去识别下一个 $A$ 中的字符串。
  4. 零次: 必须能接受空字符串 $\varepsilon$
    • 核心创意:
  5. 处理重复: 从 $N_1$每一个接受状态,画一条$\varepsilon$箭头指回 $N_1$起始状态
    • 工作原理: 当一个计算分支成功识别了 $A_1$ 中的一个字符串,到达了 $N_1$ 的接受状态时,它可以通过这条新的 $\varepsilon$ 桥梁,“免费”地、瞬间地跳回到起点,准备识别下一个片段。
  6. 处理零次 (接受 $\varepsilon$):
    • 一个坏主意: 直接把 $N_1$ 的起始状态 $q_1$ 变成接受状态。为什么不好?如果 $N_1$ 内部有路径可以从 $q_1$ 出发,经过一些转换再回到 $q_1$,那么把 $q_1$ 变成接受状态,可能会意外地接受一些不属于 $A_1^*$ 的短字符串。
    • 正确的解决方法: 创建一个全新的起始状态 $q_0$
    • 让这个新的 $q_0$ 本身就是接受状态。这就直接解决了接受 $\varepsilon$ 的问题。
    • $q_0$ 画一条 $\varepsilon$ 箭头到 $N_1$ 的旧起始状态 $q_1$
    • 工作原理: 计算从 $q_0$ 开始。
    • 如果输入是空字符串,计算停在 $q_0$,由于 $q_0$ 是接受状态,$\varepsilon$ 被接受。
    • 如果输入非空,计算可以通过 $\varepsilon$ 箭头立即跳转到 $q_1$,然后开始在 $N_1$ 的世界里进行匹配。
    • 这个方法非常干净,它只把 $\varepsilon$ 加入了语言,而没有对 $N_1$ 的内部结构产生任何副作用。
  7. 图示解读 (图1.50):
    • 一个全新的起始状态 $q_0$ 被加入,它同时也是接受状态(双圈)。
    • $q_0$ 有一条 $\varepsilon$ 箭头指向旧的起始状态 $q_1$
    • 从所有旧的接受状态 $F_1$$\varepsilon$ 箭头指回旧的起始状态 $q_1$

46.3 具体数值示例

  1. 新起始状态 $q_0$,并设为接受状态。
  2. $\varepsilon$ 箭头: $q_0 \to q_1$
  3. $\varepsilon$ 箭头: $f_1 \to q_1$
  4. $N$ 的接受状态集是 $\{q_0, f_1\}$
    • 模拟输入 ab:
  5. 开始于 $q_0$$\varepsilon$ 分裂到 $\{q_0, q_1\}$
  6. 读 'a': 从 $q_0$ 死亡。从 $q_1 \to q_2$。活跃状态 $\{q_2\}$
  7. 读 'b': 从 $q_2 \to f_1$。活跃状态 $\{f_1\}$
  8. 输入结束。最终状态 $f_1$ 是接受状态。接受 ab (正确)。
    • 模拟输入 aba:
  9. ...处理完 ab 后,活跃状态是 $\{f_1\}$
  10. $f_1$,有 $\varepsilon$ 转换到 $q_1$。活跃状态变为 $\{f_1, q_1\}$
  11. 读 'a': 从 $f_1$ 死亡。从 $q_1 \to q_2$。活跃状态 $\{q_2\}$
  12. 输入结束。最终状态 $q_2$ 不是接受状态。拒绝 aba (正确)。

46.4 易错点与边界情况

46.5 总结

定理1.49的证明思想展示了如何通过巧妙地增加一个新状态和两条 $\varepsilon$ 回路,来为一个NFA赋予“跳过”(接受$\varepsilon$)和“重复”的能力。这个构造同样具有通用性和模块化的美感。

4.7 定理1.49的证明

47.1 原文

证明$N_{1}=\left(Q_{1}, \Sigma, \delta_{1}, q_{1}, F_{1}\right)$识别$A_{1}$

构造$N=\left(Q, \Sigma, \delta, q_{0}, F\right)$来识别$A_{1}^{*}$

  1. $Q=\left\{q_{0}\right\} \cup Q_{1}$

$N$的状态是$N_{1}$的状态加上一个新的起始状态。

  1. 状态$q_{0}$是新的起始状态。
  2. $F=\left\{q_{0}\right\} \cup F_{1}$

接受状态是旧的接受状态加上新的起始状态。

  1. 定义$\delta$,使得对于任何$q \in Q$和任何$a \in \Sigma_{\varepsilon}$

$$ \delta(q, a)= \begin{cases}\delta_{1}(q, a) & q \in Q_{1} \text{ 且 } q \notin F_{1} \\ \delta_{1}(q, a) & q \in F_{1} \text{ 且 } a \neq \varepsilon \\ \delta_{1}(q, a) \cup\left\{q_{1}\right\} & q \in F_{1} \text{ 且 } a=\varepsilon \\ \left\{q_{1}\right\} & q=q_{0} \text{ 且 } a=\varepsilon \\ \emptyset & q=q_{0} \text{ 且 } a \neq \varepsilon \text{。}\end{cases} $$

47.2 逐步解释

这是对星号构造思想的形式化描述。

  1. $Q = \{q_0\} \cup Q_1$:
    • 新状态集是旧状态集加上一个全新的状态 $q_0$
  2. $q_0$ 是新的起始状态:
    • 计算从 $q_0$ 开始。
  3. $F = \{q_0\} \cup F_1$:
    • 新接受状态集是旧的接受状态集 $F_1$ 并上新的起始状态 $\{q_0\}$
    • $q_0$ 设为接受状态,直接保证了空字符串 $\varepsilon$ 被接受。
  4. $\delta$ 的定义:
    • 情况一和二 ($q \in Q_1$$q \notin F_1$$a \neq \varepsilon$): 如果状态在 $N_1$ 的“领地”内,并且不是在接受状态上进行 $\varepsilon$ 跳转,那么它的行为和以前在 $N_1$ 中完全一样。
    • 情况三: $q \in F_1$$a = \varepsilon$: 这是“循环播放”的连接点。如果当前状态是 $N_1$ 的一个接受状态,并且进行 $\varepsilon$ 跳转,那么它的去向是它原来的 $\varepsilon$ 去向($\delta_1(q,\varepsilon)$并上 $N_1$ 的起始状态 $\{q_1\}$。这创建了从终点到起点的回路。
    • 情况四: $q=q_0$$a=\varepsilon$: 这是“跳过”或“开始第一次播放”的连接点。从新的起始状态 $q_0$ 出发,通过 $\varepsilon$ 跳转,可以进入旧机器的起始状态 $q_1$
    • 情况五: $q=q_0$$a \neq \varepsilon$: 新的起始状态不消耗任何实际的输入符号。

47.3 公式与符号逐项拆解和推导

$$ \delta(q, a)= \begin{cases}\dots \\ \delta_{1}(q, a) \cup\left\{q_{1}\right\} & q \in F_{1} \text{ 且 } a=\varepsilon \\ \left\{q_{1}\right\} & q=q_{0} \text{ 且 } a=\varepsilon \\ \dots\end{cases} $$

47.4 总结

这段形式化证明为星号运算的闭包性提供了严谨的构造算法。通过引入一个既是起点又是终点的新状态,并增加从旧终点到旧起点的$\varepsilon$回路,该构造优雅地实现了对任意重复(包括零次)的识别。至此,我们已经使用NFA证明了正则语言对三个正则运算(并集、连接、星号)都是封闭的。这是计算理论中的一个基础而重要的结果。

55. 行间公式索引

  1. $$ \delta^{\prime}(R, a)=\bigcup_{r \in R} \delta(r, a) . $$

解释: 这是在子集构造法中,用于无$\varepsilon$转换的NFA的DFA转换函数定义。它表示DFA的新状态(一个集合)是其原状态(一个集合)中所有成员在NFA中转换后的并集。

  1. $$ E(R)=\{q \mid q \text{ 可以通过沿着0条或更多条 } \varepsilon \text{ 箭头从 } R \text{ 到达}\}。 $$

解释: 这是$\varepsilon$-闭包的形式化定义,表示从状态集R出发,仅通过$\varepsilon$箭头能到达的所有状态的集合。

  1. $$ \delta^{\prime}(R, a)=\{q \in Q \mid q \in E(\delta(r, a)) \text{ 对于某个 } r \in R\} \text{。} $$

解释: 这是在子集构造法中,用于带$\varepsilon$转换的NFA的DFA转换函数定义的另一种写法,其等价于 $E(\bigcup_{r \in R} \delta(r, a))$

  1. $$ \{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\} 。 $$

解释: 这是示例1.41中,对含有3个状态的NFA $N_4$ 进行子集构造时,理论上可能产生的DFA的全部8个状态(即NFA状态集的幂集)。

  1. $$ \delta(q, a)= \begin{cases}\delta_{1}(q, a) & q \in Q_{1} \\ \delta_{2}(q, a) & q \in Q_{2} \\ \left\{q_{1}, q_{2}\right\} & q=q_{0} \text{ 且 } a=\varepsilon \\ \emptyset & q=q_{0} \text{ 且 } a \neq \varepsilon \text{。}\end{cases} $$

解释: 这是证明并集闭包性时,构造的新NFA $N$ 的转换函数。它定义了如何将两个NFA $N_1$$N_2$ 的规则与新的起始状态 $q_0$ 组合起来。

  1. $$ N_{2}=\left(Q_{2}, \Sigma, \delta_{2}, q_{2}, F_{2}\right) \text{ 识别 } A_{2} \text{。} $$

解释: 这是在证明连接闭包性时,对第二个NFA $N_2$ 的形式化五元组描述。

  1. $$ \delta(q, a)= \begin{cases}\delta_{1}(q, a) & q \in Q_{1} \text{ 且 } q \notin F_{1} \\ \delta_{1}(q, a) & q \in F_{1} \text{ 且 } a \neq \varepsilon \\ \delta_{1}(q, a) \cup\left\{q_{2}\right\} & q \in F_{1} \text{ 且 } a=\varepsilon \\ \delta_{2}(q, a) & q \in Q_{2} \text{。}\end{cases} $$

解释: 这是证明连接闭包性时,构造的新NFA $N$ 的转换函数。它定义了如何从 $N_1$ 的接受状态通过$\varepsilon$转换“桥接”到 $N_2$ 的起始状态。

  1. $$ \delta(q, a)= \begin{cases}\delta_{1}(q, a) & q \in Q_{1} \text{ 且 } q \notin F_{1} \\ \delta_{1}(q, a) & q \in F_{1} \text{ 且 } a \neq \varepsilon \\ \delta_{1}(q, a) \cup\left\{q_{1}\right\} & q \in F_{1} \text{ 且 } a=\varepsilon \\ \left\{q_{1}\right\} & q=q_{0} \text{ 且 } a=\varepsilon \\ \emptyset & q=q_{0} \text{ 且 } a \neq \varepsilon \text{。}\end{cases} $$

解释: 这是证明星号闭包性时,构造的新NFA $N$ 的转换函数。它定义了如何通过新的起始状态处理空串,以及如何从旧的接受状态通过$\varepsilon$转换跳回旧的起始状态以实现循环。

[[END_OF_RESPONSE]]所有解释内容已全部输出完毕。