CSCI3130 L03 Part 3 正则文法

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核本讲：L03 Part 3 正则文法 · 原件 L03-正则表达式-资料包.pdf（本地课件） p.55–101 定位：用变量与状态对应，连接生成式描述和识别式描述。前后：上一份 L03-P2-表达式与自动机.md · 下一份 L03-P4-结尾小测.md

p.55 Outline，进入正则文法。

先找出文法中的变量（p.56–58）【新】

p.58 Grammars with at most one variable at the right side of a production

p.56 回顾 $G=(V,T,S,P)$ ：变量、终结符、开始变量、产生式。p.57 的语言只收最终完全由终结符构成的串，中途句型不是自动成为语言成员。p.58 定义线性文法：每条右侧最多一个变量，零个也允许。 $S\to aSb$ 仍然线性，因为右侧只有一个 S；线性并不表示只能增长一个终结符，也不表示变量必须靠边。

线性、非线性与右线性（p.59–61）

p.59 的 $S\to A,A\to aB\mid\lambda,B\to Ab$ ，每轮 $A\Rightarrow aB\Rightarrow aAb$ 在 A 两旁各加一个字母，结束时 A 消去。因此产生 $a^nb^n$ ；每条规则线性，但混用了变量左右两侧，不是正则文法。p.60 的 $S\to SS\mid\lambda\mid aSb\mid bSa$ 含 SS 两个变量，所以非线性；讲义说明它生成 a、b 数量相等的串。

p.61 右线性统一要求 $A\to xB$ 或 $A\to x$ ，x 为任意有限终结符串，也可空。变量如出现必须在最右边。例 $S\to abS\mid a$ 每轮添 ab，最后添 a，得到 $(ab)^na$ 。

左线性与正则的范围（p.62–64）

p.63 A regular grammar is either right-linear or left-linear grammar

p.62 左线性统一要求 $A\to Bx$ 或 $A\to x$ 。例 $S\to Aab,A\to Aab\mid B,B\to a$ ：初始已经加一个 ab，循环可以继续加 ab，最终左端变量变 a。p.63 的 either 指整个文法统一选左或右，不能每条随意选。p.64 因而区分“正则一定线性”和“线性未必正则”；p.59 正是反例。判断时先逐条找变量数，再检查所有规则的方向一致性。

文法形式和语言性质要分别作答（补充）：看见不符合右线性的规则，只能直接说“这份文法不是右线性”；还不能断言它生成的语言非正则。自取文法 $S\to aSb\mid\lambda$ 的语言确实非正则，但这个更强结论需要独立证明。另一个自取例 $S\to SS\mid a\mid\lambda$ 是非线性 CFG，却恰好生成 $a^{\ast}$ ，语言正则：所有叶子只能是 a 或空；任意 n 个 a 又能通过分出 n 个 S 再各自产生 a 得到。原题若问 grammar，就检查规则；若问 language，就检查生成集合是否存在某种等价有限自动机。

两个例子与两个包含方向（p.65–67）

p.65 第一文法的语言由 $(ab)^{\ast}a$ 描述；第二个由 $aab(ab)^{\ast}$ 描述。第二个至少含一次 ab，是因为 S 的第一步不能省；a 单独不属于第二语言。p.66 宣布正则文法与正则语言对应，p.67 首先证明任一正则文法的语言都能由有限自动机接受。

从右线性文法造 NFA（p.68–70）

p.68 说明反方向还要证明每个正则语言都有正则文法。p.69–70 当前先做文法到自动机：变量可看成“还没生成的后缀所处的阶段”，每展开一条产生式就沿边读出那段终结符。正确性要保证整个推导读出的串与路径标签完全相同，不能只让两边看起来相似。

为变量建状态（p.71–73）

题面（本讲 · p.71；公式按讲义重排）

p.71 Grammar G is right-linear

$S\to aA\mid B,\quad A\to aaB,\quad B\to bB\mid a$ .

p.72 建 S、A、B 三个变量状态及新终态 $V_F$ ，初态 S。p.73 对 $S\to aA$ 加 S 读 a 到 A 的边。此时只能表示这一条规则，机器尚不完整，不能提前把 A 当终态。

空产生与多字母右侧（p.74–76）

p.74 把 $S\to B$ 译为空边：变量换了但没输出字母。p.75 的 $A\to aaB$ 用两条 a 边和一个新中间状态实现；一条普通 NFA 边不能读两个字母。p.76 的 $B\to bB$ 译成 B 的 b 自环。每条多字母规则使用专属中间点，避免不同规则在半路交叉导致多出路径。

结束推导与路径验算（p.77–79）

p.77 的 $B\to a$ 没有剩余变量，所以由 B 沿 a 边到 $V_F$ 。p.78 的推导

S\Rightarrow aA\Rightarrow aaaB\Rightarrow aaabB\Rightarrow aaaba

逐段输出 a、aa、b、a，总串 aaaba，路径也按这四段到终态。p.79 从 S 到 B 只有经 A 输出 aaa，或空边输出空串；之后循环输出若干 b，最后输出 a。故 RE 为 $aaab^{\ast}a+b^{\ast}a$ 。这里最后一个 a 必不可少；停在 B 只表示还能继续推导，不能当成生成完成。

一般化的连边规则（p.80–82）

p.80 一般产生式为 $V_i\to a_1\cdots a_mV_j$ 或 $V_i\to a_1\cdots a_m$ 。p.81 每个变量建状态，并添加独立终态。p.82 第一种规则展开为从 $V_i$ 到 $V_j$ 的 m 条边；m=0 时用空边。完整推导中“已输出前缀＋尚存变量”对应“已读前缀＋当前状态”，这是逐步一致的不变量。

终结产生式与循环示例（p.83–85）

p.83 第二种规则的链终点改为 $V_F$ ；如果右侧为空串，就用空边到终态。

题面（本讲 · Example 3.15 · p.84；公式按讲义重排）

p.84 Construct an FA that accepts the language generated by the grammar

$V_0\to aV_1,\quad V_1\to abV_0\mid b$ .

图有 $V_0$ 读 a 到 $V_1$ ， $V_1$ 读 a 到新中间点再读 b 回 $V_0$ ，另一条 b 边直接到终态。一次完整回路输出 aab，最终退出输出 ab，故 $(aab)^{\ast}ab$ 。零圈的 ab 被接受；一圈的 aabab 是 aab 后接 ab。p.85 转入左线性，策略是先把输出反转成右线性，而不是直接套“变量在末尾”的连边法。

左线性转右线性需要反转终结符串（p.86–88）

p.86 把左规则写成 $A\to Bv$ 或 $A\to v$ ；p.87 改为 $A\to v^RB$ ；p.88 纯终结符规则改为 $A\to v^R$ 。不是把变量移到另一边就结束，v 内的字母顺序也要反转。

用 p.62 的原例，变换后 $S\to baA,A\to baA\mid B,B\to a$ 。原文法一步 $S\Rightarrow Aab\Rightarrow Bab\Rightarrow aab$ ；新文法 $S\Rightarrow baA\Rightarrow baB\Rightarrow baa$ ，结果 baa 正好是 aab 的反转。每增加一轮原来的 ab，反转后会在另一侧增加 ba，方向一致。

用反转封闭性结束证明（p.89–91）

p.89 新文法 G′ 右线性，故 $L(G')$ 正则；原语言是它的反转，也正则。所用事实的构造含义是把 NFA 的边全部反向，旧终态经新起点分叉进入，旧起点变终态。这样原先读 w 的路径倒着读就是 $w^R$ 。p.90–91 转到逆方向：已有 NFA 时，每个状态改成变量，就能建右线性文法。

NFA 的边变成产生式（p.92–94）

图（p.92）： $q_0$ 是初态； $q_0$ 读 a 到 $q_1$ ； $q_1$ 有 b 自环、读 a 到 $q_2$ ； $q_2$ 读 b 到唯一终态 $q_3$ ； $q_3$ 空转回 $q_1$ 。看什么：第一次到终态输出 $ab^{\ast}ab$ ，以后每次回去再来输出 $b^{\ast}ab$ 。

p.93 第一条边给 $q_0\to aq_1$ ；p.94 两条出边给 $q_1\to bq_1\mid aq_2$ 。状态名此时作为文法变量，不能把 q 的数字当作输出字母。

终态要能消掉变量（p.95–97）

p.95 加 $q_2\to bq_3$ ；p.96 空边给 $q_3\to q_1$ ，终态资格另给 $q_3\to\lambda$ 。这两条职责不同：前者允许继续接受更长串，后者让已有串正式结束。整体语言为 $ab^{\ast}ab(b^{\ast}ab)^{\ast}$ 。例如 $q_0\Rightarrow aq_1\Rightarrow aaq_2\Rightarrow aabq_3\Rightarrow aab$ 是零次 b 自环的最短串。

p.97 一般规则为状态边 $q\xrightarrow{a}p$ 变成 $q\to ap$ ；空边令 a 取空串，得到单位产生式。

四种表示的共同边界（p.98–100）

p.98 为每个终态加到空串的产生式，否则推导永远残留一个变量。p.99 从路径与推导逐步对应得到语言相等；p.100 收束 DFA、NFA、RE、RG 四种表示。换形式是为了让构造、证明或运算更容易，并不获得新的语言表达能力。

p.101 Questions 结束页；后面仍有实际小测，另见 Part 4。

考试角度：（C 级通识）常见考法是识别“右侧最多一个变量”与“统一靠右”的差别，或把多终结符规则展开成路径并处理终态消去。

考试角度：（A 级：HW02-2025T1-题目-更新.pdf Q4–Q5，考的是正则文法转换与奇偶文法。）见附录 A1。

考试角度：（A 级：期中练习-含解答-学期待核.pdf Q1(5,7,8)，对应正则文法与上下文无关性判断；扫描卷题面经视觉读取，练习卷不冒称正式考卷。）见附录 A2。

自检：将终态变量消去规则全部删掉会怎样？

追踪一次路径翻译后的句型末尾是否仍有变量。

展开推理与答案

每条边规则仍留下一个状态变量；没有终态到空串的规则，就无法完成全终结符串。即使运行路径已到接受状态，文法的句型仍未结束。要靠终态消去规则把机器的“可以在这里接受”翻译成文法的“可以在这里结束”。

将本讲四种表示串起来自检（p.100–101）

对 p.92–96 原机，先读 a 到 q1，在 q1 读任意多个 b，再读 a 到 q2、b 到终态 q3；q3 可以空转回 q1 重复后一段。因此完整语言为 $ab^{\ast}ab(b^{\ast}ab)^{\ast}$ 。对应右线性规则是

\begin{aligned} q_0&\to aq_1,\\ q_1&\to bq_1\mid aq_2,\\ q_2&\to bq_3,\\ q_3&\to q_1\mid\lambda. \end{aligned}

这里 q3→q1 模拟的是机器的空转移，q3→λ 模拟的是“在终态停止生成”，两者不能互相替代。例如 aab 走 q0→q1→q2→q3 接受；aabaab 可在 q3 空转回 q1 后继续读 aab 吗？剩余 aab 第一位 a 已使 q1→q2，下一位 a 无边，所以拒绝。正确的双轮短串是 aabab：首轮 aab，返回 q1 后读 ab。做这类完整跑串，才能检查 RE、NFA 和文法三份答案是否确实一致。DFA 可通过子集构造得到，故 p.100 所列 DFA、NFA、RE、正则文法描述同一类语言；这不声称每份表示大小相同。

本讲核心考点

线性、右线性、左线性的区别（p.58–65，C 级）。
右线性文法转 NFA（p.70–84，C 级）。
左线性借助反转处理（p.85–89，C 级）。
NFA 转文法时保留空边及终态消去（p.92–99，C 级）。

附录

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

A1 作业/往年题演练（非讲义内容）：正则文法转换与奇偶文法

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

p.1 (20pts) Construct a DFA that accepts the language generated by the grammar:

原规则为S→aT或bS或A；T→bS或aB；A→ab或aB；B→bA或aa。

先构造NFA：变量作状态，新增终态F；S—λ→A，S— a →T，S— b →S，T— b →S，T— a →B，A— a →B，并用A— a →C— b →F表示ab，用B— a →D— a →F表示aa，另B— b →A。C、D为新中间态。初态λ闭包为{S,A}；任何后继含S时都补A。可达子集的完整DFA为：

编号/子集	a	b	接受
0={S,A} 初态	1	0	否
1={B,C,T}	2	3	否
2={B,D}	4	5	否
3={S,A,F}	1	0	是
4={D,F}	6	7	是
5={A}	8	7	否
6={F}	7	7	是
7=空集	7	7	否
8={B,C}	9	10	否
9={D}	6	7	否
10={A,F}	8	7	是

例如ab：0→1→3接受，对应S⇒A⇒ab；aaa：0→1→2→4接受，对应S⇒A⇒aB⇒aaa；aaaa：0→1→2→4→6接受，对应S⇒aT⇒aaB⇒aaaa。子集同时保留不同分支，不能只跟一条NFA分支下结论。

题面块（同文件 · Q5 · p.1；公式按原件重排）：

p.1 (20pts) Find regular grammars for the following languages on a, b:

p.1 1) $\{\omega:n_a(\omega)\text{ and }n_b(\omega)\text{ are both even}\}$

p.1 2) $\{\omega:n_a(\omega)+3n_b(\omega)\text{ is odd}\}$

1）用变量E00、E10、E01、E11表示a/b计数模2，开始E00。每个Eij读a写规则Eij→aE(1−i)j，读b写Eij→bEi(1−j)，仅E00另有λ规则。即E00→aE10或bE01或λ；E10→aE00或bE11；E01→aE11或bE00；E11→aE01或bE10。aabb依次E00→aE10→aaE00→aabE01→aabbE00→aabb，λ也接受。

2）模2下3与1相同，所求等价于总长度奇数。开始E，规则E→aO或bO；O→aE或bE或λ。每个字符切换奇偶，只有奇态可结束。bab长度3生成；ab长度2不可结束。两组均为右线性文法，每个状态不变量对应计数条件。

回到正文：正则文法转换与奇偶文法

A2 作业/往年题演练（非讲义内容）：正则文法与上下文无关性判断

题面块（期中练习-含解答-学期待核.pdf（本地课件） · Q1(5,7,8) · p.1；公式按原图重排）：

p.1 5. A regular language must be context-free.

p.1 7. The grammar $G_1=(\{S\},\{a,b\},S,\{S\to aSb\mid\varepsilon\})$ is a regular grammar.

p.1 8. The grammar $G_2=(\{S\},\{a,b\},S,\{S\to aS\mid bS\mid b\})$ generates a regular language.

依次True、False、True。5：右线性文法本来就是CFG的特例。7：aSb把变量夹在两边终结符中，不是左线性或右线性规则；不能说这一条“不线性”：它右侧只有一个变量，所以确实是线性规则；不满足的是左线性或右线性的边端限制。8：规则右线性，任意前缀a/b后以b结束，语言为 $(a+b)^{\star}b$ 。如abb可由S⇒aS⇒abS⇒abb，λ和a不可生成。这里判断具体文法形式与语言类分别处理，不把它们混为同一问题。

回到正文：正则文法与上下文无关性判断

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.55–101。
本次独立学习修订：逐页核对本讲 PDF 文本，视觉核对 p.25、31、36–38、42、44–45、49–50、53–54、102–104 的图和题面；原图以边表和逐步计算展开，未发布原件截图。