CSCI3130 L03 Part 4 结尾小测

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核本讲：L03 Part 4 结尾小测 · 原件 L03-正则表达式-资料包.pdf（本地课件） p.102–104 定位：保留 Outline 后的两道原讲义构造题，并把图翻成可逐步验证的文法。前后：上一份 L03-P3-正则文法.md

两个正则文法构造题（p.102–104）

题面（本讲 · Short Quiz 14 · p.102；图片，视觉读取；公式按原题重排）

p.102 14. Find regular grammars for the following languages on $\{a,b\}$ .

(a) $L=\{w:n_a(w)\text{ is even},n_b(w)\ge4\}$ .

(b) $L=\{w:n_a(w)\text{ and }n_b(w)\text{ are both even}\}$ .

p.103 的图为第(a)问同时记两件事：a 的奇偶；b 个数在0、1、2、3、至少4这五档。两种乘五档共十状态，编号 $q_{2j}$ 表示 a 偶、b 在 j 档， $q_{2j+1}$ 表示 a 奇、b 在 j 档。读 a 切换同档的上下点；读 b 前进一档，到第4档后不再增加。初态 $q_0$ ，唯一终态 $q_8$ 。逐边翻成文法：

\begin{aligned} q_0&\to aq_1\mid bq_2,&q_1&\to aq_0\mid bq_3,\\ q_2&\to aq_3\mid bq_4,&q_3&\to aq_2\mid bq_5,\\ q_4&\to aq_5\mid bq_6,&q_5&\to aq_4\mid bq_7,\\ q_6&\to aq_7\mid bq_8,&q_7&\to aq_6\mid bq_9,\\ q_8&\to aq_9\mid bq_8\mid\lambda,&q_9&\to aq_8\mid bq_9. \end{aligned}

只有 $q_8$ 可消成空串，强制两个条件同时满足。例如四个 b 走 $q_0,q_2,q_4,q_6,q_8$ 后消去，生成 bbbb；三个 b 只到 $q_6$ ，无法结束。再在四 b 后添一个 a 到 $q_9$ ，仍不能结束；添第二个 a 回 $q_8$ ，可以结束。这检查了计数截断与奇偶两个边界。

p.104 的第(b)问不需截断计数，只保留两个奇偶位。初态兼终态 EE，表示 a 偶、b 偶。a 切第一位、b 切第二位，得

\begin{aligned} EE&\to aOE\mid bEO\mid\lambda,\\ OE&\to aEE\mid bOO,\\ EO&\to aOO\mid bEE,\\ OO&\to aEO\mid bOE. \end{aligned}

以 abab 验算： $EE\Rightarrow aOE\Rightarrow abOO\Rightarrow abaEO\Rightarrow ababEE\Rightarrow abab$ 。空串也由初始 EE 直接消去，符合两个计数都为零且为偶数；不能为了“至少读一个字母”去掉它，因为题目没有这个限制。每步状态准确记录前缀的两个奇偶位，故所有结束推导恰好满足要求，且任何满足要求的串都能沿自己的逐字符轨迹生成。

考试角度：（C 级通识）常见考法是将独立的有限记忆相乘，再把接受状态翻译成空产生式；不应为已经不再重要的精确大计数无限添状态。

不背十条状态名：先写更新规则（补充）

第(a)题可以先用有意义的坐标 $(i,j)$ 设计，i 是 a 数模2，j 是 b 数与4的较小者。读 a 更新为 $(1-i,j)$ ；读 b 更新为 $(i,\min(j+1,4))$ 。只有 $(0,4)$ 能结束。然后再用正文的编号 $q_{2j+i}$ 给坐标改名，十条文法规则只是这两条更新的展开，不必十行分别猜。

跟踪自取串 babbba： $(0,0)\to(0,1)\to(1,1)\to(1,2)\to(1,3)\to(1,4)\to(0,4)$ ，所以可结束；同一轨迹删最后 a 时停在 $(1,4)$ ，b 虽够四个，a 的奇偶仍不合格。它也说明不能“先数完所有 a 再数 b”：原串的字符顺序是任意的，两种记忆须同步更新。

自检：第五个 b 要进入拒绝陷阱吗？

原条件是至少四个，还是恰好四个？

展开推理与答案

不需要。第四个以后的 b 仍留在第4档，因为至少四个已经满足，未来也不会被更多 b 破坏。若题目改为恰好四个，才需第五个 b 的拒绝陷阱；这时状态设计已经是另一题。

从图到规则的逐串核验（p.103–104）

(a) 的 q0、q2、q4、q6、q8 依次表示已见 0、1、2、3、至少4个 b 且 a 偶数；下排 q1、q3、q5、q7、q9 是相同 b 计数且 a 奇数。a 总是在同一列上下切换；b 向右移一列，到最后一列就留在本行。因而唯一允许停下的是 q8，而不是 q9。bbbb 的轨迹 q0→q2→q4→q6→q8 接受，abbbb 到 q9 拒绝，abbbba 最后回 q8 接受。

(b) 的 EE 同时是初态、终态，所以必须有 EE→λ；每读一个 a 翻转第一奇偶位，每读一个 b 翻转第二位。abba 的状态依次 EE、OE、OO、OE、EE，故接受；ab 停 OO，拒绝。空串两种计数都为0，所以也接受。

本讲核心考点

奇偶与饱和计数的乘积状态（p.102–103，C 级）。
双奇偶文法的完整推导（p.104，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：无

原件：L03-正则表达式-资料包.pdf（本地课件），PDF p.102–104。
本次独立学习修订：逐页核对本讲 PDF 文本，视觉核对 p.25、31、36–38、42、44–45、49–50、53–54、102–104 的图和题面；原图以边表和逐步计算展开，未发布原件截图。