CSCI3130 L02 Part 2/4 Nondeterministic Finite Accepters

课程：CSCI3130 Formal Languages and Automata Theory · 2026T1（沿用既有原件版本标记） 本讲：L02 Part 2/4 Nondeterministic Finite Accepters · 原件 lec2.pdf（本地课件） p.75–158 定位：用存在一条成功分支理解非确定性，逐步追踪空转移与可达状态集合，避免把一条失败分支误当成整个机器拒绝。 前后：上一份 L02-P1-确定有限自动机.md · 下一份 L02-P3-DFA与NFA等价.md

p.75 Outline 分节页。

Nondeterministic Finite Accepters

同一输入可以有多个选择（p.76–78）【新】

图（p.76–78）：四状态NFA。 元素：初态q0，唯一终态q2；边为q0读a到q1、q0读a到q3、q1读a到q2；q2、q3没有出边。 看什么：p.76 给机器，p.77 强调q0读a有两个选择，p.78 强调某些状态可以没有后继。它既允许多个后继，也允许零个后继，与完整DFA不同。

非确定性（nondeterminism）在这里是一种数学接受规则，不是随机抽签，也没有为箭头分配概率。判断一个串时必须考虑所有可能分支；只要有一条完整成功便接受。

aa的成功分支（p.79–81）

题面（lec2.pdf · First Choice · p.79）

p.79 a a

p.79 输入aa；p.80 选择上支，读第一个a从q0到q1；p.81 读第二个a到q2。记录为 $(q_0,aa)\to(q_1,a)\to(q_2,\lambda)$：括号第二项是剩余输入，最后为空，同时q2为终态。

aa的另一条分支（p.82–84）

p.82 确认上支耗尽输入且接受。p.83 从头考察下支，p.84 第一位a让q0到q3，但还剩一个a。不能把第二次模拟接在第一条运行末尾；这两条是对同一输入的不同完整候选运行。

一条失败不会否定成功（p.85–87）

p.85 在q3找不到读a的边，p.86 说明这条分支无法消耗剩余输入而拒绝。p.87 定义整体接受：存在一个计算，既读完输入又在终态。这里上支已提供见证，所以aa仍然被机器接受。分支拒绝和整个NFA拒绝是不同层次。

p.87 when there is a computation of the NFA that accepts the string

单字符a：第一条分支（p.88–90）

p.88 并列两条aa运行，强调只需一个成功。p.89 改输入为a；p.90 选择上支，q0读唯一的a到q1。输入已经耗尽，但q1不是终态，不能为了到q2再“读取一个不存在的a”。

单字符a：第二条分支（p.91–93）

p.91 上支因最终停q1而拒绝。p.92 开始下支，p.93 读唯一a到q3；同样输入耗尽且非终态。没有剩余输入与没有出边分别描述不同事实，本例即使q3有额外读a的边，也不能读一个本来不存在的字符。

整体拒绝的量词（p.94–96）

p.94 下支也拒绝；p.95 给一般拒绝条件，p.96 汇总两支。NFA拒绝要证明不存在成功运行，等价于所有运行都失败。失败可因为输入耗尽时非终态，也可因为仍有输入却走不下去。将“存在成功”误改成“所有成功”，会错误地把NFA当作全称分支模型。

p.96 All possible computations lead to rejection

aaa：到了终态也可能失败（p.97–99）

p.97 输入aaa；p.98 从上支读前面的a，继续到q2；p.99 到q2时只读了两个a，还剩一个。终态没有a出边，因此整串不接受。这是“经过终态”不等于“读完整串后在终态”的第二个反例。

aaa的下支也走不完（p.100–102）

p.100 标上支拒绝；p.101 重新选下支；p.102 读第一个a到q3，还剩aa。两条分支走的步数不必相同，它们失败的具体位置也可以不同。

汇总拒绝（p.103–105）

p.103 q3没有a后继，p.104 下支拒绝；p.105 汇总aaa所有可能运行均失败。

把 p.79–105 的三种输入集中核算一次，仍沿原图的两条分支：

这张表把“分支失败的原因”与“整台机器的结果”分开。NFA 的接受见证必须是一条有限、完整消费输入的运行；不能从两条不同分支各借一半路径拼成图上不存在的成功运行。

接受语言（p.106）

p.106 给 $L=\{aa\}$。为什么恰好这一个串：通向唯一终态q2的路径只可能q0→q1→q2，标签恰为aa，且q2无出边；其他路径不可能增加新的接受串。

不消耗输入的转移（p.107–109）【新】

图（p.107）：含lambda的链。 元素：初态q0，唯一终态q3；q0读a到q1，q1经lambda到q2，q2读a到q3，无其他边。 看什么：lambda标在边上表示空串，不是要求输入带上真的lambda字符。

p.108 输入aa；p.109 第一位a使q0到q1，剩余a。此刻虽然下一条边不是a，也未必卡住，因为还可先做不耗输入的移动。

读头不动的那一步（p.110–112）

p.110 (read head does not move)

p.110 q1经lambda到q2，剩余输入仍是a；p.111 q2读第二个a到q3；p.112 输入耗尽而接受。三条边只消费两个字符，因此“路径边数=串长”仅对没有空转移的机器成立。

aaa的前半段（p.113–115）

p.113 改输入aaa。p.114 读第一位后剩aa；p.115 走lambda仍剩aa。空转移既没有吞掉一个a，也不会凭空生成输入字符；它只改变内部状态。

终态前的空转移也不万能（p.116–118）

p.116 读第二位到q3后还剩a，且没有出边；p.117 拒绝；p.118 总结语言仍为 $\{aa\}$。与前面四状态例子相比，内部图不同但接受语言相同。这种“同语言”即下一部分的机器等价。

ab循环：先走一轮（p.119–121）【新】

图（p.119）：正闭包机器。 元素：初态q0，唯一终态q2；q0读a到q1，q1读b到q2，q2经lambda到q3，q3经lambda回q0。 看什么：q2是双圈而q3不是，不能仅因q3在最右边就猜它为终态。

p.120 选输入ab，p.121 第一位a到q1。此图没有从初态直接空走到终态的路径，所以空串不接受。

接受以后还可选择继续（p.122–124）

p.122 读b到q2，p.123 输入已尽，可在q2结束接受；它不是被迫再走lambda离开终态。p.124 改输入abab，第一轮到q2时还有ab，因此可以经q3回q0准备再读一轮。

第二轮如何接起来（p.125–127）

p.125 读第一a到q1，p.126 读第一b到q2，p.127 经lambda到q3。已读前缀一直是ab，剩余一直为ab，不能把lambda算成第三个输入字符。

返回与再读（p.128–130）

p.128 q3空转移回q0；p.129 再读a到q1；p.130 再读b到q2。完整标签a、b、lambda、lambda、a、b连接后仍是abab，共四字符而六条边。

正闭包与空串机器（p.131–133）

p.131 abab在q2结束接受；p.132 语言为 $\{ab\}^+$，每次必须完整读一轮ab，至少一轮。p.133 强调lambda不会作为符号出现在输入带上；并画两台无边单状态机器：非终初态只接受空语言，终初态接受 $\{\lambda\}$。后者输入a也失败，因为没有消耗a的边。

为什么NFA往往更短（p.134–136）【新】

p.136 The set $\delta(q_i,a)$ may be empty

公式按讲义重排。p.134 中接受单串a的NFA只需初态q0、终态q1和一条a边；对应完整DFA还需陷阱q2，使q1读a后有去处且q2自环。省掉失败分支的显式结构便可减小图。

p.135–136 保留五元组，但 $\delta:Q\times(\Sigma\cup\{\lambda\})\to2^Q$，输出是状态集合。空集代表没有后继，单元素集合代表一个后继，多元素代表多个后继。$\varnothing$ 不是“空串状态”，$\{q\}$ 也不能在集合运算中当作裸q。

Example 2.8 的单步转移（p.137–139）

图（p.137）：三状态NFA。 元素：初态兼唯一终态q0；q0读1到q1，q1读0到q0；q1读0或1还可到q2；q0经lambda到q2；q2无出边。 看什么：q1读0有两个后继q0与q2，q0的lambda后继则只能沿图中的一条边到q2。

p.138 因此 $\delta(q_0,1)=\{q_1\}$；p.139 $\delta(q_1,0)=\{q_0,q_2\}$。遇到并行同标签边要取全部后继，不能凭“哪条看起来更合理”任意删掉一条。

单步lambda与闭包要分开（p.140–142）

p.140 页上写 $\delta(q_0,\lambda)=\{q_0,q_2\}$。已重新核图：没有q0的lambda自环，只有q0到q2的lambda边。按p.135的单步转移定义应为 $\{q_2\}$；包含q0自身的 $\{q_0,q_2\}$ 应解释为零步或多步lambda可达集合（lambda closure），或 $\delta^{\ast}(q_0,\lambda)$。这是原页记号混用，不能把它抄成单步定义。

p.141 的 $\delta(q_2,1)=\varnothing$，因为q2无出边；p.142 语言是 $\{10\}^{\ast}$。q0本为终态，所以接受空串；每轮1到q1、0回q0可重复。走入非终死端q2的分支永远不贡献接受串，因而它在接受语言意义上冗余。

表（p.137–141 原图对应的单步转移；空闭包另算）：

由本例展开空串与 10 的运行：初始空闭包是 {q0,q2}，其中有终态 q0，因此空串接受；读1后只有 {q1}；再读0先得到 {q0,q2}，空闭包没有新增状态，故10接受。若输入11，第二位后为 {q2}，与终态集合无交，所以拒绝。q2 出现在某次集合中并不代表整串必败，关键是是否还有 q0 这样的成功分支。

一次跟踪所有可达状态（p.143–145）【新】

图（p.143）：六状态NFA。 元素：初态q0，终态q0和q5；q0读a到q1；q1读a到q4或q5、读b到q2；q2空转移到q3；q3空转移回q0；q4、q5无出边。 看什么：同一个已读输入可能对应多个当前状态，且最后一次消费字符之后仍应加入lambda可达状态。

p.143 读a后只有 $\{q_1\}$；p.144 读aa后为 $\{q_4,q_5\}$；p.145 读ab先到q2，再空走到q3、q0，所以是 $\{q_2,q_3,q_0\}$。若只记消费最后字符瞬间的q2，就会错失终态q0，从而错误拒绝ab。

路径长度与输入长度不同（p.146–147）

p.146 定义 $q_j\in\delta^{\ast}(q_i,w)$ 表示存在从qi到qj、所有非空标签连接为w的walk。p.147 图的边是q0读a到q1、q1经lambda到q2、q2经lambda到q0；初态q0、终态q1。q1→q2→q0→q1→q2走四条边，标签却只有a。

算一遍：从q2空走可到q0，故 $\delta^{\ast}(q_2,\lambda)=\{q_2,q_0\}$；读一个a时从q0到q1，再空走得到q2、q0，所以集合成为全部三态。再读第二个a后仍为全部三态，故 $\delta^{\ast}(q_2,aa)=\{q_0,q_1,q_2\}$。这种“闭包—消费—闭包”的方式比枚举所有空转移绕圈更有限、更可靠。

空闭包怎样计算才不会陷在环里（补充）：闭包求的是“哪些状态能到达”，不是“有多少条空路径”。先把起点放进集合与待处理队列；取一个状态，只看它的 lambda 出边；尚未收录的后继才加入队列。例有空边 u→v、v→u、v→t，从 u 开始：集合 {u} → {u,v} → {u,v,t}；检查 v→u 时 u 已在集合中，不再入队，因此不会反复 u→v→u。t 没有新后继，结束。三个状态都有有限路径见证，绕环一百次也不会增加新状态。

在模拟输入时，对每个字符都另建后继集合，而不是把新后继随意加回旧集合继续消费同一字符。否则一轮读 a 可能沿两条 a 边前进，相当于把一个输入字符用了两遍。正确顺序是：旧集合取一次字符转移 → 合并 → 空闭包 → 将它作为下一轮的旧集合。

p.147 的另外一项原式为 $\delta^{\ast}(q_1,a)=\{q_0,q_1,q_2\}$，可完整核算：从 q1 先空走 q2→q0，再消费 a 到 q1，最后可停在 q1，或继续空走到 q2、q0。因此三个状态都可达。以 q2 为终点的见证走了四条边，标签依次 λ、λ、a、λ；擦去空标签后恰为 a。这解释页上“length of a walk ... is 4”为何不矛盾。

非空交集才是接受条件（p.148–150）

p.148 回到六状态机器：aa可到q4、q5，其中q5属于F，接受；无需q4也为终态。p.149 ab可达q2、q3、q0，其中q0终态，接受。p.150 abaa先绕ab回到q0，再读aa到q4/q5，所以接受。

拒绝实例与语言表达式（p.151–153）

p.151 aba最终只能到q1，集合与F无交，拒绝；p.152 归纳得到 $L(M)=\{ab\}^{\ast}\{aa\}\cup\{ab\}^{\ast}$：可重复若干轮ab后停q0，或在其后读aa结束于q5。p.153 正式写

不是要求可达集合包含于F，也不是要求所有终态都可达。零轮ab产生空串，也符合q0初态双圈。

用选择描述并集（p.154–156）【新】

p.154 以多条标签同为w的路径示意“其中一个终点在F即可”。p.155 原图从q0读a分到q1或q4；上支q1读a到q2，再读a到终态q3；下支q4读a到终态q5、q5读a回q4。无其他边，所以语言为 $\{a^3\}\cup\{a^{2n}:n\ge1\}$。aa沿下支接受，aaa沿上支接受，aaaa沿下支接受；单a和五个a都没有成功分支。

p.156 用文法 $S\to aSb\mid\lambda$ 说明规则选择让描述简洁。注意这是“非确定选择”思想的跨模型例子，不是声称该文法的语言可以由NFA识别；$a^nb^n$ 的有限自动机限制已在p.58预告。

p.155 还把游戏程序与 TSP 列为“算法某阶段需要作选择”的例子。这里的教学作用是说明为什么允许多种候选决策能缩短描述，不是说普通计算机能免费同时搜索所有分支。p.156 也只说非确定性帮助简洁描述复杂语言；计算能力是否增加，要在下一部分用任意机器的转换证明判断。

猜起点和选择一种条件（p.157–158）

题面（lec2.pdf · More Examples · p.157–158）

p.157 All strings that contain the substring 0101.

p.158 All strings containing exactly 4 0s or an even number of 1s. (8 states)

p.157 NFA初态s在0、1上自环，同时读0还可进匹配链s→u1→u2→u3→f，链标签依次0101；唯一终态f在0、1上自环。其他未画转移为空。输入00101可先在s跳过第一个0，再沿链读0101接受；另一条过早启动失败不影响结果。这里“猜”只是同时允许所有候选起点，并不需要知道未来。

p.158 原图8态：一个新初态经两条lambda边分到上方五态计数链和下方两态奇偶机。上支读0从计数0到1、2、3、4，所有五态读1自环，仅4终态；4再读0无后继。下支初态E终态，读0自环、读1切到O；O读0自环、读1回E。两个双圈分别是上支4和下支E（新初态不画双圈但lambda可达E）。算一遍：000011上支恰有4个0而成功，下支有2个1也成功；0000011上支失败，但下支仍成功；00001只有1个1，下支失败，但上支成功。若000001，则两支皆失败。OR用分支并集，而AND通常需要同步记两种信息。

考试角度：（A 级：HW01-2025T1-题目.pdf Q4，考的是四状态并语言NFA。）见附录 A1。

考试角度：（A 级：期中练习-含解答-学期待核.pdf Q2(2a–b)，对应相距两位相同的NFA；扫描卷题面经视觉读取，练习卷不冒称正式考卷。）见附录 A2。

本讲核心考点

• 接受是存在一条完整成功运行，拒绝要排除全部成功运行（p.87、95；C 级）。
• lambda边不消费输入，路径边数可大于串长（p.107–118、147；C 级）。
• 单步转移、空闭包、扩展转移的对象不同（p.135–147；C 级，p.140记号需辨析）。
• 可达集合与终态集合非空相交即可接受（p.148–154；C 级）。
• NFA可用分支表达并集及模式起点选择（p.155–158；C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

A1 作业/往年题演练（非讲义内容）：四状态并语言NFA

题面块（HW01-2025T1-题目.pdf（本地课件） · Q4 · p.1）：

p.1 Find an nfa with four states for $L=\{a^n:n\geq0\}\cup\{b^n a:n\geq1\}$. (20%)

用四态s、A、B、F，初态s，终态{s,A,F}。全部边：s— a →A，A— a →A；s— b →B，B— b →B，B— a →F；其余无边。s终态接受λ，A分支只读正数个a；B分支至少读一个b再读唯一末尾a至F，F无后继，所以不能再接字符。每条接受路径恰落在两类之一，任一目标串都能走对应路径。a、aaa、ba、bbba接受；b、aba、baa拒绝。虽这张部分转移图没有真正分叉，仍是合法NFA；不需为了名称人为制造非确定边。

回到正文：四状态并语言NFA

A2 作业/往年题演练（非讲义内容）：相距两位相同的NFA

题面块（期中练习-含解答-学期待核.pdf（本地课件） · Q2(2) · p.2；公式重排）：

p.2 NFAs: Let $\Sigma:=\{a,b\}$ and define $B_n:=\{w\in\Sigma^{\star}:\exists i:w_i=w_{i+n}\}$, the language of all words over Σ.

p.2 (a) Give an NFA for each of B0. (≤ 3 states)

p.2 (b) Give an NFA for each of B2. (≤ 9 states)

指标要求两位置均存在。B0中任意非空串选任一位置即可，λ没有i，因此B0=Σ正闭包。两态s初始不接受、f接受，s读a/b到f，f读a/b自环。

B2要找到隔一个字符的两个相同符号。六态s,A1,A2,B1,B2,f；初态s，唯一终态f。s对a/b自环以跳过前缀，并额外a→A1、b→B1；A1读a/b到A2，B1读a/b到B2；A2读a到f，B2读b到f；f对a/b自环。未列无边。三字符aba存在首尾a，接受；abb首尾不同且没有别的相距2位置，拒绝；aa只有2格，拒绝B2。不能把相距2误成中间隔两个字符。

回到正文：相距两位相同的NFA

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

• 原件：lec2.pdf（本地课件），PDF p.75–158。

• 本次复核：2026-10-13；逐页读取 lec2.pdf 文字，核对主要机器图与图片题例，补全转移表及主线证明。p.53 原图在 PDF 渲染中缺失部分图元，正文已提供明确标为补充的完整构造。