CSCI3130 L02 Part 1/4 Deterministic Finite Accepters

课程：CSCI3130 Formal Languages and Automata Theory · 2026T1（沿用既有原件版本标记）本讲：L02 Part 1/4 Deterministic Finite Accepters · 原件 lec2.pdf（本地课件） p.1–74 定位：从逐字符运行建立 DFA 的五元组与接受条件，学会把有限计数、后缀匹配和余数信息编码进状态。前后：上一份 L01-P2-语言与文法.md · 下一份 L02-P2-非确定有限自动机.md

整讲导航

Part 1 DFA：p.1–74。
Part 2 NFA：p.75–158。
Part 3 等价与确定化：p.159–201。
Part 4 状态最小化：p.202–207。

p.1 标题页，p.2 为四部分 Outline。

Deterministic Finite Accepters

从接受器到转移图（p.3–4）【新】

p.3 An abstract model of a digital computer

p.3 沿用输入、控制、存储与输出的抽象，接受器回答YES/NO，转换器输出符号串。本部分每读一个字符，当前状态按唯一规则改变；输入结束后才根据状态判定。

图（p.4）：只接受abba的六状态机器。元素：初态 $q_0$ ，唯一终态 $q_4$ ；顺序边 $q_0\xrightarrow{a}q_1\xrightarrow{b}q_2\xrightarrow{b}q_3\xrightarrow{a}q_4$ 。其余边为 $q_0\xrightarrow{b}q_5$ 、 $q_1\xrightarrow{a}q_5$ 、 $q_2\xrightarrow{a}q_5$ 、 $q_3\xrightarrow{b}q_5$ 、 $q_4\xrightarrow{a,b}q_5$ 、 $q_5\xrightarrow{a,b}q_5$ 。看什么： $q_5$ 是出错后无法挽回的陷阱；双圈只是接受标志，不能理解成读到它就停止读取剩余输入。

补充：读图之前先识别四种记号。 圆圈内 q 是内部状态名，不是输入字符；没有起点圆圈、直接指向 q0 的箭头标初态；双圈标允许在输入结束时接受的状态；有向边上的 a、b 是本次必须消费的字符。同一条边标 a,b，只是两条分别读 a 或 b、终点相同的规则的简写，不是一次读取字符串 ab。

第一台机器的状态有具体含义：q0 表示还没读任何字符；q1、q2、q3、q4 分别表示目前恰好读了 a、ab、abb、abba；q5 表示已读前缀不可能再补成“恰好 abba”。因此输入过短会停在前四个非终态，输入错误或过长会进入 q5。这给出覆盖所有输入的理由，而不只解释某几个例子。

abba的前两步（p.5–7）

题面（lec2.pdf · 第一台机器的输入演示 · p.5）

p.5 Input String

p.5 a b b a

p.5 未读输入，处于 $q_0$ ；p.6 开始读第一个a，按唯一a边到 $q_1$ ；p.7 再读b到 $q_2$ 。把一次运行写成“已读前缀、当前状态、剩余串”最不容易漏字符：读完ab时为 $(ab,q_2,ba)$ 。这三页页脚号不同，属于逐步演示，不能以“动画”名义抹掉中间步骤。

abba读完后为什么接受（p.8–10）

p.8 第三个字符b使 $q_2\to q_3$ ；p.9 最后a使 $q_3\to q_4$ ；p.10 标Input finished，并给accept。完整状态序列 $q_0,q_1,q_2,q_3,q_4$ 有5个状态，因为4个字符对应4次转移，初态也需记录。接受必须同时满足“输入耗尽”和“当前在F内”。

aba何时已经无法挽回（p.11–13）

题面（lec2.pdf · Rejection · p.11）

p.11 a b a

p.11 从 $q_0$ 开始；p.12 读a到 $q_1$ ；p.13 读b到 $q_2$ 。到这里，与前一个合法串abba的前缀相同，机器当然还不能判定最终结果；下一字符决定是否继续匹配。

aba的拒绝（p.14–15）

p.14 的第三个a把 $q_2$ 送进 $q_5$ ；p.15 输入耗尽，非终态，所以reject。它不是“少一个b所以停住”，DFA仍有明确的a转移，只是转到拒绝陷阱。

空串（p.16–17）

p.16 改用空串 $\lambda$ ；p.17 没读任何符号就已经输入结束，仍在 $q_0$ ，而它不是终态，因此拒绝。空串测试无需沿任何标着lambda的边，DFA没有这种输入转移。

第二台机器：先任意多个a（p.18–20）【新】

图（p.18）：三状态机器。元素：初态 $q_0$ ，唯一终态 $q_1$ ； $q_0$ 有a自环、b到 $q_1$ ； $q_1$ 遇a或b到 $q_2$ ； $q_2$ 在a、b上自环。看什么：在第一个b之前可以有任意多个a，但b后不能再有字符。

题面（lec2.pdf · Another Example · p.18）

p.18 a a b

p.18 从 $q_0$ 开始；p.19 读第一个a仍在 $q_0$ ；p.20 第二个a仍在 $q_0$ 。循环使机器能处理任意长的a段，而不必为每个长度增加状态。

aab的接受（p.21–22）

p.21 读b到 $q_1$ ，p.22 输入结束所以接受。

过早经过终态（p.23–24）

p.23 新输入为bab；p.24 首字符b也让机器到 $q_1$ ，但还剩ab，不能宣布接受。两次到达同一终态，接受结果仍可能不同，差别在是否还有输入。

陷阱状态（p.25–27）

p.25 继续读a， $q_1\to q_2$ ；p.26 最后的b保持 $q_2$ ；p.27 输入结束拒绝。进入陷阱后仍要按规则处理剩余字符，只是已不可能回到终态。这台机器接受的恰好是 $a^nb$ ，n可为0：单独b合法，空串不合法，bb不合法。

五元组的类型（p.28–30）【新】

p.28 Deterministic Finite Accepter (DFA) is defined by the 5-tuple

$M=(Q,\Sigma,\delta,q_0,F)$ 中Q为有限状态集， $\Sigma$ 为有限输入字母表， $\delta:Q\times\Sigma\to Q$ 是全函数， $q_0\in Q$ 是初态， $F\subseteq Q$ 是终态集。p.29 原例字母表为a、b；p.30 状态为 $q_0$ 至 $q_5$ 。不能把读头当前位置也自动算进Q，否则把外部输入位置当成无限内部记忆。

初态、终态与每一步（p.31–33）

p.31 单独指出 $q_0$ ，p.32 给 $F=\{q_4\}$ ，p.33 指出 $\delta$ 的参数是“状态+一个符号”。初态是一项状态，不是集合；F可以为空、一个或多个状态。全函数要求每一组状态与字符恰有一个后继；漏掉不想接受的分支不符合这里的完整DFA定义。

三条具体转移（p.34–36）

p.34 的 $\delta(q_0,a)=q_1$ 、p.35 的 $\delta(q_0,b)=q_5$ 使用相同当前状态而不同输入，结果不同。p.36 的 $\delta(q_2,b)=q_3$ 使用与前例相同的b但不同当前状态，也得不同结果。由此看出转移不是只由输入字符决定，更不是每个a永远去固定某个状态。

转移表与扩展函数（p.37–39）【新】

表（p.37）：第一台DFA完整转移表。

δ	a	b
q0	q1	q5
q1	q5	q2
q2	q5	q3
q3	q4	q5
q4	q5	q5
q5	q5	q5

p.38 将输入从单字符扩展为整个串： $\delta^{\ast}:Q\times\Sigma^{\ast}\to Q$ 。p.39 的 $\delta^{\ast}(q_0,ab)=q_2$ 表示查表两次：先查q0行a列得q1，再查q1行b列得q2。星号没有让机器获得新能力，只是将多次已有步骤缩写。

路径标签与状态结果（p.40–42）

p.40 输入abba得到q4；p.41 输入abbbaa，在读前缀abb后为q3，第四个b送到q5，后两个a仍在q5，最终结果q5。p.42 把此事表述成图论：从q到q′存在标签w的walk，当且仅当 $\delta^{\ast}(q,w)=q'$ 。这里要允许重复顶点，所以用walk，而不是L01的simple path。

递归展开怎么落到查表（p.43–45）

p.43 再将abbbaa路径与q5对应。p.44 定义 $\delta^{\ast}(q,\lambda)=q$ ，以及

\delta^{\ast}(q,w\sigma)=\delta(\delta^{\ast}(q,w),\sigma).

w是任意前缀， $\sigma$ 是最后一个字符；先处理w，再处理最后一格。p.45 计算ab： $\delta^{\ast}(q_0,ab)=\delta(\delta^{\ast}(q_0,a),b)=\delta(\delta(\delta^{\ast}(q_0,\lambda),a),b)=\delta(\delta(q_0,a),b)=\delta(q_1,b)=q_2$ 。基础情形负责终止递归，否则公式会无限往下展开。

终态集合改变语言（p.46–48）【新】

p.46 all input strings accepted by M

p.46 定义 $L(M)$ 收集所有被接受的输入；p.47 原机器只有q4终态，故只收abba。p.48 保持所有转移，却改F为 $\{q_0,q_2,q_4\}$ ，于是接受空串、ab、abba。图上双圈已逐一核读。接受语言由完整五元组共同决定，不能只看转移箭头形状。

接受条件与补语言（p.49–51）【新】

p.49 给 $L(M)=\{w\in\Sigma^{\ast}:\delta^{\ast}(q_0,w)\in F\}$ 。p.50 将最后条件改为不属于F，得到被拒绝的语言，也就是相对固定字母表的补集。对完整DFA，每个串恰好有一条完整运行，因此将终态改为 $Q-F$ 便能求补。

p.51 回到三状态 $a^nb$ 机器：任何数量的a保持q0，唯一b进入q1，再有任何字符就落q2。数几个不同n不是证明全部；正确性来自三个状态的语义始终保持。

固定前缀与禁止子串（p.52–53）【新】

p.52 all strings with prefix ab

p.52 初态q0读a到q1，q1读b到唯一终态q2，q2在a、b上自环；q0读b或q1读a到陷阱q3，q3在a、b上自环。前两字符一旦正确，后面不能破坏“前缀ab”这个历史事实。算一遍：abba走q0→q1→q2→q2→q2，接受；aab在第二个a落q3，拒绝。

p.53 all strings without substring 001

p.53 本机渲染只显示部分自环，完整节点与部分边未能显示，不能据文字标签声称核清原图终态。补充：由题意自行构造。用状态E、Z、ZZ分别记录末尾与模式001匹配了0、1、2个字符，另用D记已出现001；初态E，终态E、Z、ZZ。转移为E读0到Z、读1到E；Z读0到ZZ、读1到E；ZZ读0仍ZZ、读1到D；D读任意字符留D。0001经过E→Z→ZZ→ZZ→D，拒绝；000停ZZ，接受。状态记的是对未来匹配有用的最长后缀，不需存全部前缀。

正则性与首尾约束（p.54–56）【新】

p.54 A language L is regular iff there exists some DFA M such that L = L(M)

p.54 用“存在某台DFA”定义正则语言；p.55 列先前的语言为例。它们是否有无限多串不是决定因素：有限状态可以循环，所以无限语言也可能正则。

p.56 的 $L=\{awa:w\in\{a,b\}^{\ast}\}$ 要求至少两个字符，首尾均a。原图初态q0，终态只有q3；q0读a到q2、读b到q4；q2读a到q3、读b留q2；q3读a留q3、读b到q2；q4读任意字符自环。算一遍：a只到q2所以拒绝，aa到q3接受，aba走q0→q2→q2→q3接受。仅记“首字a且末字a”会错收长度1的a，原图用初始阶段避免此问题。

p.56 的转移表：这一页没有 q1，沿用原图 q0、q2、q3、q4 的编号。

状态	读 a	读 b	已读前缀含义
q0	q2	q4	尚未读取
q2	q3	q2	首位 a；尚未满足至少两位且末位 a
q3	q3	q2	首位 a、至少两位、末位 a；接受
q4	q4	q4	首位已经错误；永远拒绝

q2 同时容纳“只读了一个 a”和“首位是 a、当前末位是 b”的情况，因为这两种历史对所有后续串的接受要求完全相同：还需最终读到一个 a。状态合并的理由是未来行为相同，而非过去经历相同。

两份连接与能力边界（p.57–59）

题面（lec2.pdf · Example 2.6 · p.57）

p.57 The language $L=\{awa:w\in\{a,b\}^{\ast}\}$ is regular, how about $L^{2}$ ?

公式按讲义重排。 $L^2=\{aw_1aaw_2a:w_1,w_2\in\{a,b\}^{\ast}\}$ ，中间两份连接处必须出现aa；不是把一份里所有a、b次数都乘2。补充构造：先造两份p.56机器，将第一份终态用不消耗字符的选择接第二份初态；这是下一部分NFA允许的规则，再经Part3确定化得到DFA。为不提前假设结论，完整有限记忆的DFA构造见附录 A1。最短串aaaa可拆aa与aa，因此接受；aaa长度不足4，因此拒绝。

由 p.57 展开的完整确定构造：本题只问正则性，可以直接给一个有限、后继唯一的状态记录，不提前借用后面的 NFA 等价定理。记录 p 为第一份 p.56 机器的当前状态，T 为所有已经合法开始的第二份机器副本的当前状态集合。初始 $p=q_0,T=\varnothing$ 。读字符 c 时，先让 p 和 T 中每个状态各走一次 c；若更新后的第一份状态是 q3，再把 q0 加入 T，表示第一份恰好在本字符结束、第二份从下一个字符开始。

最终只要 T 含 q3，就有一个切分使左右两份都属于 L。p 只有四种值，T 至多有16种值，因此总共至多64种记录；每种记录对每个字符的更新唯一，这本身就是一台 DFA。

读完前缀	第一份状态 p	第二份状态集合 T	是否接受
空串	q0	∅	否
a	q2	∅	否
aa	q3	{q0}	否
aaa	q3	{q0,q2}	否
aaaa	q3	{q0,q2,q3}	是

新加入的 q0 不再消费刚才那个字符，否则会让第一份的末尾 a 与第二份的开头 a 共用同一位置，错收 aaa。每个合法切分都会启动一个副本，所以不漏收；只有某副本真正到 q3 才接受，所以不多收。附录保留相同构造供核验。

p.58 对比 $a^nb$ 与 $a^nb^n$ ：前者只需知道是否见过最后一个b，后者需要匹配无界数量，这里先预告不是正则，证明留到泵引理。p.59 总结任一时刻DFA只有一个当前状态，输入逐字符读取；不是同时处于所有状态。

接受总结与设计入口（p.60–62）

p.60 再强调必须读完所有字符；p.61 重列五元组；p.62 重列正则语言存在性定义。这三页没有新算法。设计时先写状态的中文含义，再决定初态、终态与每个字符的后继，最后检查每格都有且仅有一个值；否则图画得像自动机，也可能没满足形式定义。

有限计数、联合计数与长度上限（p.63–65）【新】

题面（lec2.pdf · More Examples，三页分别突出一题 · p.63–65）

p.63 All strings that contain exactly 4 "0"s.

p.64 All strings containing exactly 4 "0" s and at least 2 "1" s.

p.65 All strings of length at most five.

p.63 原图初态计数0，沿0逐次到1、2、3、4，只有4终态；每个计数态读1自环，再读第五个0进入非终陷阱D，D在0、1上自环。例如001001依次计到1、2、2、3、4、4，接受。

p.64 用15个格子 $(i,j)$ 记录0的数量 $i\in\{0,1,2,3,4\}$ 与截断的1计数 $j\in\{0,1,2\}$ ，另加统一陷阱；初态(0,0)，唯一终态(4,2)。读0向右，超过4到陷阱；读1向下，达到2后保持2。001001最终(4,2)，接受。之所以把“至少2”截断在2，是2、3、4个1对今后是否满足条件没有区别；“恰好4”则必须另识别超过4。

p.65 原图长度0至5共六个双圈态，初态长度0也接受；任意字符使长度加1，超过5进入自环陷阱。五字符01101到5接受，第六字符不论是什么都拒绝。

固定后缀、数值余数与包含模式（p.66–68）【新】

题面（lec2.pdf · More Examples · p.66–68）

p.66 All strings ending in "1101".

p.67 All strings whose binary interpretation is divisible by 5.

p.68 All strings that contain the substring 0101.

p.66 用匹配长度0、1、2、3、4表示末尾分别匹配空、1、11、110、1101。初态0，只有4终态；下表把原图箭头完整译成可复算的规则。读到1101后再读0不再符合后缀，因此不能在终态永久停留。

匹配长度	读0	读1
0	0	1
1	0	2
2	3	2
3	0	4
4	0	2

算1101：0→1→2→3→4，接受；再加0到0，拒绝。

p.67 记录前缀数值除5的余数r，初态和唯一终态是r=0。追加二进制位b使数值从x变 $2x+b$ ，所以后继余数 $(2r+b)\bmod5$ 。原图五态对应余数0、1、2、4、3的左右排列，而不是简单顺序0到4。算1010：余数0→1→2→0→0，最终0；数值为10，确实可被5整除。图的初态双圈也接受空串，这相当于采用空表示0的约定；若题意要求至少一位，则需另设非终初态。

表（p.67，由原图余数含义展开）：把每一格 $2r+b$ 先算出再取模5。

当前余数 r	读0后的算式及余数	读1后的算式及余数
0	0 mod 5 = 0	1 mod 5 = 1
1	2 mod 5 = 2	3 mod 5 = 3
2	4 mod 5 = 4	5 mod 5 = 0
3	6 mod 5 = 1	7 mod 5 = 2
4	8 mod 5 = 3	9 mod 5 = 4

初态与唯一终态是0。任意长输入仍只需这五个余数状态，因为能影响未来余数的只是旧余数，不是整个整数大小。

p.68 匹配0101的前缀长度0到4，转移依次为0:(0→1,1→0)、1:(0→1,1→2)、2:(0→3,1→0)、3:(0→1,1→4)、4:(0→4,1→4)。初态0、终态4。算00101：0→1→1→2→3→4接受。它与p.66不同：一旦包含，追加字符不会抹去历史上已出现的模式，因此终态是接受吸收态。

为什么 1101 后再读 1，要退到匹配长度 2？（补充解释 p.66）当前末尾加一位变成 11011。候选模式 1101 的前缀依次为空、1、11、110、1101。逐个检查哪些同时是 11011 的后缀：1 是，11 也是；110 与 1101 都不是，因而最长可保留的是 11，进入状态 2。不是“出错后全部清零”，因为最后两个 1 可以成为下一次匹配的开头。若再读 0、1，状态继续 2→3→4，正好识别尾部新出现的 1101。

这里的不变量是：状态 k 记录已读串的后缀中，能匹配目标模式前缀的最大长度。新字符只可能延长或缩短这个有效后缀。输入读尽时 k=4 等价于最后四位正是 1101，便完成正确性证明的接受部分。将“包含模式”的终态自环照搬过来会错收 11010，因为曾经匹配不代表现在仍以它结尾。

禁止模式（p.69）

题面（lec2.pdf · More Examples · p.69）

p.69 All strings that don’t contain the substring 110.

原图初态E，终态E、O、OO；D为非终陷阱。E读0留E、读1到O；O读0到E、读1到OO；OO读1留OO、读0到D；D在0、1上自环。E/O/OO记末尾连续1的相关长度，两个以上都合并成OO。110走E→O→OO→D拒绝；111停OO接受，因为尚没有紧接的0完成禁串。

计数模3（p.70–71）【新】

题面（lec2.pdf · Exercise 2.1.7 · p.70）

p.70 Find DFAs for the following languages on $\Sigma=\{a,b\}$

(a) $L=\{w:\lvert w\rvert\bmod3=0\}$

(b) $L=\{w:n_a(w)\bmod3>n_b(w)\bmod3\}$

公式按原题重排。p.70 用三个状态0、1、2记长度余数，初态兼唯一终态0；a、b都使状态按0→1→2→0循环。aba经过0→1→2→0接受，ab停2拒绝，空串在0接受。

p.71 的原图九态(i,j)分别记a数、b数模3，初态(0,0)，终态(1,0)、(2,0)、(2,1)。读a使第一坐标加1模3，读b使第二坐标加1模3。aab走(0,0)→(1,0)→(2,0)→(2,1)，满足2>1而接受；aaab到(0,1)，虽然a实际更多，余数却0<1，必须拒绝。要比较的是取模后的数，不能比较原始计数。

每个00后面立即有1（p.72）【新】

题面（lec2.pdf · Exercise 2.1.9(a) · p.72）

p.72 Every 00 is followed immediately by a 1.

原图初态λ，终态λ、0、001；00为非终待兑现状态，另有陷阱D。边为λ读1自环、读0到0；0读1到λ、读0到00；00读1到001、读0到D；001读1到λ、读0到0；D在0、1上自环。出现00后下一位必须1，而且不能就此输入结束。

算一遍：0010走λ→0→00→001→0，接受；00100最后到00，虽然没出现第三个0，也因末尾义务未兑现而拒绝。0001在第三位已到D，最后1不能补救，因为最前面的00后面紧接的是0。重叠出现同样受约束。

p.72 的全部原例也可以在笔记里逐步核对：101 走 λ→λ→0→λ，接受；0010 走 λ→0→00→001→0，接受；0010011001 走 λ→0→00→001→0→00→001→λ→0→00→001，接受。0001 在第三位进入 D，拒绝；00100 在输入结束时停 00，拒绝。页中的“不属于”符号已在渲染图核对，不能照文字抽取结果把这两个反例误抄成成员。

首位结合奇偶、奇数位置限制（p.73–74）【新】

题面（lec2.pdf · More Examples · p.73）

p.73 All strings that start with 0 and have odd length or start with 1 and have even length.

p.73 All strings where every odd position is a 1.

p.74 第一幅图有非终初态s、终态A、非终态B。s读0到A、读1到B；A、B每读0或1互换。首个字符已经决定长度1时是否接受，此后每增加1个字符就翻转。0接受、01拒绝、10接受；空串留s拒绝。

第二幅图有初态兼终态E（下一位是奇数位置），终态O（下一位是偶数位置），非终陷阱D。E读1到O、读0到D；O读0或1都到E；D在0、1上自环。空串无违规位置，因此接受；1011经过E→O→E→O→E接受；100在第3位读0进入D，拒绝。位置从1开始，不能把“奇数位置为1”错误改成“1的总数为奇数”。

考试角度：（A 级：HW01-2025T1-题目.pdf Q3，考的是最小长度约束。）见附录 A2。

考试角度：（A 级：期中练习-含解答-学期待核.pdf Q2(1a–b)，对应位置奇偶DFA；扫描卷题面经视觉读取，练习卷不冒称正式考卷。）见附录 A3。

自检：余数机为何只记 r，不必保存整个二进制整数 x？

将 x 写成 5k+r，再追加一个二进制位 b。

展开推理与答案

追加后数值为 $2x+b=10k+2r+b$ 。其中 $10k$ 可被5整除，故新余数只由 $(2r+b)\bmod5$ 决定，旧商 k 对未来余数无影响。这证明压缩没有丢掉任务需要的信息；不是仅因五个状态画起来方便。

本讲核心考点

完整DFA五元组与读完输入后的接受条件（p.28–50；C 级）。
扩展转移函数的递归展开（p.38–45；C 级）。
有限计数、饱和计数和乘积状态（p.63–65；C 级）。
模式匹配必须保留可重叠的最长后缀（p.66、68–69；C 级）。
二进制余数更新与计数取模（p.67、70–71；C 级）。
尚未兑现的尾部义务必须拒绝（p.72；C 级）。

附录

A1 Example 2.6 的确定构造（p.57）

这里从原语言的题意推一个完整DFA，而不把后面的NFA等价定理当已证前提。先读第一个a，否则到陷阱。之后维护三个有限布尔/阶段信息：是否在第一个字符以后见到可作为第一份终点的a；上一位是否是这个候选终点a；是否已经见过第一份终点a紧接第二份起点a。最后还需记第二份起点之后是否至少再读了一个字符，以及当前末位是否为a。有限个布尔量的组合就是有限状态。

一种更精确、容易查表的实现是同时维护两份p.56机器状态的集合：第一份机器的单一当前状态p；第二份机器所有已启动副本的当前状态集合T，初始为 $p=q_0,T=\varnothing$ 。每读字符c，先令 $p'=\delta(p,c)$ ，并令 $T'=\{\delta(t,c):t\in T\}$ ；若 $p'=q_3$ ，再把第二份初态q0加入T′，表示第一份可以刚好在此结束，但第二份尚未读取任何字符。最终接受当且仅当T含q3。这个更新只有有限多个组合且每次后继唯一，因此本身就是DFA定义，不依赖NFA的物理解释。

算aaaa：初始 $(q_0,\varnothing)$ ；第1位后 $(q_2,\varnothing)$ ；第2位后 $(q_3,\{q_0\})$ ；第3位后 $(q_3,\{q_0,q_2\})$ ；第4位后 $(q_3,\{q_0,q_2,q_3\})$ ，第二份出现终态，接受。aaa仅到第三步，第二份集合无q3，拒绝。每一个可能的合法切分都在其第一份结束处启动副本，因此不会漏解；副本只有严格按第二份机器接受才贡献q3，因此也不会多收非法串。

回到正文：两份连接与能力边界（p.57–59）

A2 作业/往年题演练（非讲义内容）：最小长度约束

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

p.1 Show that the language $L=\{a^n:n\geq3\}$ is regular. (20%)

取字母表{a}，状态q0、q1、q2、q3，初态q0，唯一终态q3，a转移依次q0→q1→q2→q3→q3。状态分别表示读过0、1、2、至少3个a。因此当且仅当长度至少3时接受，存在DFA即证明正则。λ、a、aa拒绝，aaa、aaaa接受。若另规定更大字母表，须给非a字符加拒绝陷阱；原题单字母语言按{a}处理。

回到正文：最小长度约束

A3 作业/往年题演练（非讲义内容）：位置奇偶DFA

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

p.2 DFAs: Draw a Deterministic Finite Automaton consider the set of strings on {0, 1} defined by the requirements below:

p.2 (a) All strings that start with 0 and have odd length or start with 1 and have even length. (≤ 5 states)

p.2 (b) All strings where every odd position is a 1. (≤ 5 states)

(a)三态s、A、B，s初态非终态、A唯一终态；s读0到A、读1到B；A读0/1均到B，B读0/1均到A。首位初始化接受奇偶，之后每多一个字符就翻转是否满足条件。0接受、00拒绝、1拒绝、10接受，λ在s拒绝，因为无首位。

(b)三态E、O、D，E初态，E/O均终态，D拒绝陷阱。E表示已读偶数位，下一个为奇数位：读1到O、读0到D；O下一个为偶数位，读0/1都到E；D两符号自环。λ真空满足限制，所以E终态；10、101接受，100在第三位0落D拒绝。两题状态数均不超过5。

回到正文：位置奇偶DFA

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.1–74。
本次复核：2026-10-13；逐页读取 lec2.pdf 文字，核对主要机器图与图片题例，补全转移表及主线证明。p.53 原图在 PDF 渲染中缺失部分图元，正文已提供明确标为补充的完整构造。