CSCI3130 L11–L12 语言层级与文法 · Part 2 无约束文法

课程：CSCI3130 Formal Languages and Automata Theory 本讲：合讲第 2 部分 / 共 6 部分 · 原件 L11-L12-语言层级与文法-资料包.pdf（本地课件） p.66–68 定位：从只改写单个变量的 CFG，走到可以改写含上下文的字符串的文法，并解释它为何对应 RE。 前后：上一份 递归与可枚举语言 · 下一份 上下文有关语言 承接：#L01-50 产生式与推导、#L11-07 无约束文法

左侧不再被限制为单个变量（p.66–68）【已会】

图（p.66）：一般产生式的左右两侧。 元素：中间是 u→v，两侧均标为 String of variables and terminals。 看什么：左侧可以把变量及其附近的终结符作为一个整体匹配。

CFG 的规则形状是 A→某串，只要找到 A 就能使用。这里左侧若是 aB，就只能在相邻字符恰为 a、B 的位置使用，不能只看到 B 就改写。补充（定义约定）：标准无约束文法仍要求左侧非空且至少含一个变量；“无约束”解除的是正则、上下文无关、非收缩等限制，并非允许任意脱离推导语义的替换。右侧可为空，故可以缩短句型。

题面（原件 · 无约束文法算例 · p.67；公式按讲义重排）

p.67 Example unrestricted grammar: $S\to aBc$; $aB\to cA$; $Ac\to d$

从 S 开始只能先得到 aBc；其中相邻 aB 符合第二条，整段替换为 cA，剩余的末尾 c 保留，所以是 cAc；再把其中 Ac 换成 d，得到 cd。完整链为

cd 已全为终结符，所以属于生成语言。不能将第二步写成 acAc，那会把应被替换掉的 a 留下。此例没有其他可选规则，故唯一生成的终结符串就是 cd。注意“这份文法不是 CFG”不等于“它的语言不是 CFL”：单元素语言甚至是正则语言。

p.68 A language L is recursively enumerable if and only if L is generated by an unrestricted grammar

正向直觉是：有限次推导就像有限次计算，可按推导步数一层层尝试，找到目标串便接受。反向直觉是：机器的一步只改写读头附近的有限符号，可以用一般产生式模拟。两方向的构造见附录 A1。有等价的识别器，不代表存在总停机的成员算法；如果串不在语言里，穷尽推导的搜索可能一直找不到。

正文推导补全

讲义只给定理，以下补足证明构造。给定有限文法与输入 w，维护从 S 开始的推导树，每次枚举可用规则、可匹配位置。每个句型有限，规则有限，所以每个节点的后继有限；逐层展开保证任何有限推导最终被找到。若某句型等于 w 就接受；否则继续。若文法生成 w，存在有限证明，搜索必成功；若不生成，不会误接受。这给出 RE 识别器。

反方向，给定识别器 M，用复合变量编码带格，把原输入另存为不变轨道；每个复合变量记录“原字符、当前工作符号”，状态变量标记当前读头。文法先非确定生成任意候选输入及其相同的工作副本，再模拟 M。原机一步向右时，把形如 qA 的相邻编码改成 Bp；向左时，把形如 CqA 改成 pCB。其中 q、p 是状态，A 是读到的带符号，B 是写入符号，C 是左邻符号；复合变量的不变轨道始终不动。边界规则可添加空白工作格。

只有模拟进入接受状态，才允许进入清理阶段：从一端扫向另一端，删去工作符号、状态、空白边界，并将原输入轨道的字符变成真正终结符。此前所有输入字符都包在变量里，不能提前构成全终结符结果；因此无接受计算就没有可输出的终结符串。反之每个被接受输入都能按有限接受轨迹推导并清理，输出原输入。状态、符号和边界类型有限，规则模板展开成有限规则集，所以确实得到一份无约束文法。

这个证明用到了“可删清理符号”；下一部分的非收缩文法不能直接照搬这一点。

考试角度：（C 级 通识）常见考法是检查一条规则为何不是 CFG、逐次匹配左侧并写出推导，或解释文法类别与其特定生成语言类别不能混为一谈。

长度剪枝为什么在这里失去根据（补充）

CFG 清理后，如果句型已比目标串长且不会收缩，就可以安全剪掉；无约束文法允许缩短，这个理由不再成立。正文 S→aBc→cAc→cd 生成长度2的目标 cd，却必须经过长度3的句型；如果看到长度3就丢弃，唯一成功推导会被删掉。可用的公平策略是按推导步数逐层枚举：每层节点有限，即使中途句型很长，有限推导仍会在自己的那一层被访问。

展开一个句型时，还要枚举同一左侧在不同位置的匹配。自取句型 aBaB 与规则 aB→cA，替换左端得到 cAaB，替换右端得到 aBcA；它们是两种合法下一步，不是一次性把两个位置同时替换。规则替换的左、右上下文保持不动，只有选中的连续匹配段改变。每次有限长度、有限位置、有限规则，保证单层分支有限，却不保证无解时层数有限。

本讲核心考点

• 无约束文法允许一般含变量左侧，改写必须匹配连续整段（p.66–67，C 级）。
• 课件算例唯一生成 cd，但这份规则形式不是 CFG（p.67，C 级）。
• 无约束文法生成语言恰为 RE，不保证成员判定停机（p.68，C 级）。

附录

A1 无约束文法与 RE 的构造解释（p.68）

讲义只给定理，以下补足证明构造。给定有限文法与输入 w，维护从 S 开始的推导树，每次枚举可用规则、可匹配位置。每个句型有限，规则有限，所以每个节点的后继有限；逐层展开保证任何有限推导最终被找到。若某句型等于 w 就接受；否则继续。若文法生成 w，存在有限证明，搜索必成功；若不生成，不会误接受。这给出 RE 识别器。

反方向，给定识别器 M，用复合变量编码带格，把原输入另存为不变轨道；每个复合变量记录“原字符、当前工作符号”，状态变量标记当前读头。文法先非确定生成任意候选输入及其相同的工作副本，再模拟 M。原机一步向右时，把形如 qA 的相邻编码改成 Bp；向左时，把形如 CqA 改成 pCB。其中 q、p 是状态，A 是读到的带符号，B 是写入符号，C 是左邻符号；复合变量的不变轨道始终不动。边界规则可添加空白工作格。

只有模拟进入接受状态，才允许进入清理阶段：从一端扫向另一端，删去工作符号、状态、空白边界，并将原输入轨道的字符变成真正终结符。此前所有输入字符都包在变量里，不能提前构成全终结符结果；因此无接受计算就没有可输出的终结符串。反之每个被接受输入都能按有限接受轨迹推导并清理，输出原输入。状态、符号和边界类型有限，规则模板展开成有限规则集，所以确实得到一份无约束文法。

这个证明用到了“可删清理符号”；下一部分的非收缩文法不能直接照搬这一点。

回到正文：文法与 RE

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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：无

• 原件：L11-L12-语言层级与文法-资料包.pdf（本地课件），PDF p.66–68；页脚 Ch 11。

• 本次独立学习修订：核对合讲140页文本，视觉复核 p.38、60、70–71、83、94；补全正文证明并保留原页与补充构造的区分。