CSCI3130 T02 · Part 3 奇偶状态
课程：CSCI3130 · 2025T1 本讲：第3部分 / 共4部分 · T02-2025T1.pdf（本地课件） p.9–11 定位：用状态保存a的奇偶性，并理解原图四状态为何可压成两个。 前后：上一份 文法构造 · 下一份 分块语言NFA 承接：#L02-01 DFA、#L02-02 接受条件
状态保存余数而非完整计数（p.9–11）【已会】
p.9为Problem 3导航，p.10题面，p.11同页脚8/10显示状态图。
题面块（T02 · Problem 3 · PDF p.10；字母表公式按讲义重排）：
p.10 For , construct dfa’s that accept the sets consisting of all strings with an odd number of a’s.
图（p.11）：初态q0；终态q1、q3。全部状态均有b自环；a边为q0→q1、q1→q2、q2→q3、q3→q2。看什么：读到b不改a数量；从q2/q3开始，a永远切换偶/奇。q0与q2对任何后缀的接受行为相同，q1与q3也相同。
合并为E、O两态：E初始非终态，O终态，a使E/O互换，b保持原态。归纳不变量是“读过的a数为偶时在E，为奇时在O”，读完自然恰好接受奇数个a的串。
| 状态 | a | b | 接受 |
|---|---|---|---|
| E | O | E | 否 |
| O | E | O | 是 |
算一遍：baba按E→E→O→O→E，含两个a，拒绝；babaa末尾再读a到O，接受。空串留在E，0是偶数所以拒绝。原四态图同样正确，只非最小；不能把“非最小”说成“错误”。
原四态转移表：
| 状态 | a | b | 是否终态 |
|---|---|---|---|
| q0（初态） | q1 | q0 | 否 |
| q1 | q2 | q1 | 是 |
| q2 | q3 | q2 | 否 |
| q3 | q2 | q3 | 是 |
这张表保留原图全部信息；前面的 E/O 表是等价简化，而不是原图只有两个状态。
状态记住前缀性质，证明也按前缀推进（补充）
令 E 表示“到目前为止读到偶数个 a”，O 表示“奇数个 a”。空前缀有0个 a，所以初态是 E；添加 a 使计数加1，从 E 切换到 O 或从 O 切换到 E；添加 b 不改变计数，因此留在原状态。这三句话构成对输入长度的归纳证明，解释了为什么任意长串都符合状态含义，而不仅是表中的几个例子。
两状态还是必要的：前缀 λ 和 a 分别可达 E 与 O，且不再添加任何后缀时，前者必须拒绝、后者必须接受。如果把它们合并，同一状态就需要同时拒绝与接受。因此原图中表示相同奇偶性的状态可合并，但两个奇偶类别不能再合并。这里使用的是后缀 λ，而非“看上去状态不同”的直觉。
自检：读完 bbab 时为什么不是回到偶数态？
b 是保持计数，还是把计数清零？
展开推理与答案
b 只保持计数，不清零。唯一一个 a 使 E→O，最后的 b 仍留在 O，所以接受。若写成每逢 b 都回初态，就会把已读前缀的奇偶信息丢掉。
本讲核心考点
- b不改变a计数的奇偶性，a切换状态（p.10–11，C 级）。
- 初态拒绝空串；读完整串才查看终态（p.11，C 级）。
附录
两状态构造、全部转移和不变量证明已在正文完成。
来源与证据
历史版本考试证据（本次未重新读取全部试卷）：读了 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：无
-
原件：T02-2025T1.pdf（本地课件），PDF p.9–11；图已目视。
-
本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。视觉复核物理页5、11、14–15。