CSCI3130 L11–L12 语言层级与文法 · Part 3 上下文有关语言

课程：CSCI3130 Formal Languages and Automata Theory 本讲：合讲第 3 部分 / 共 6 部分 · 原件 L11-L12-语言层级与文法-资料包.pdf（本地课件） p.69–71 定位：理解非收缩规则如何维持三段等量，并解释空间有界为何让成员问题可以判定。前后：上一份无约束文法 · 下一份乔姆斯基层级承接：#L10-12 线性有界自动机、#L11-08 上下文有关文法

不允许句型变短的规则（p.69–71）【已会】

p.69 and: $\lvert u\rvert\le\lvert v\rvert$ (noncontracting)

公式按讲义重排。产生式 u→v 仍能检查左侧的上下文，但替换后长度不能比替换前小；由于句型其余部分不变，一次推导也不能使整个句型变短。课件采用上下文有关文法的等价非收缩定义。补充（规范约定）：若需要生成空串，通常特许新开始符号的一条空规则，并要求该开始符号不出现在任何规则右侧；否则长度1的开始串不可能不减长地变成长度0。

题面（原件 · 三段等量文法 · p.70；公式按讲义重排）

p.70 The language $\{a^n b^n c^n\}$ is context-sensitive:

$S\to abc\mid aAbc$

$Ab\to bA$

$Ac\to Bbcc$

$bB\to Bb$

$aB\to aa\mid aaA$

第一条直接给出 n=1 的 abc；另一选择留下工作变量 A。A 向右越过所有 b，遇第一个 c 时把 Ac 改成 Bbcc：多出一个 b、一个 c，并让工作变量换成 B。B 向左穿过 b，遇 a 时替换 aB 为 aa，补一个 a 并结束；若换成 aaA，就补 a 后开始下一轮。

算一遍：

\begin{aligned} S&\Rightarrow aAbc\\ &\Rightarrow abAc\\ &\Rightarrow abBbcc\\ &\Rightarrow aBbbcc\\ &\Rightarrow aabbcc. \end{aligned}

第二步只交换 A、b；第三步 Ac 两字符换成 Bbcc 四字符，串长增加2；最后 aB 换 aa 长度不变，却让 a 的数量增加1，因为工作变量 B 消失。总结果是三种字符各2个。若在最后一步选 aaA，则得到 aaAbbcc，下一轮能生成三种字符各3个，逐步过程和一般不变量见附录 A1。这份规则没有空产生式，实际生成 n≥1 的三段等量串；空串须按前述规范另处理。

正文推导补全

从上一轮继续形式 aaAbbcc 开始，按原规则逐步得到：

\begin{aligned} aaAbbcc&\Rightarrow aabAbcc\\ &\Rightarrow aabbAcc\\ &\Rightarrow aabbBbccc\\ &\Rightarrow aabBbbccc\\ &\Rightarrow aaBbbbccc\\ &\Rightarrow aaabbbccc. \end{aligned}

一般进入新一轮时，句型为 n 个 a、A、n 个 b、n 个 c。A 越过 n 个 b 后到 c 前；Ac→Bbcc 增加一个 b 和一个 c。B 越回原来的 n 个 b 后紧贴 a 段；aB→aa 结束，或 aB→aaA 继续，均增加一个 a。因此每个终结符完成串都是三段等长，且每选择一次继续规则，就把 n 增加1。开始规则提供 n=1，任意选择有限轮后结束便生成每个 n≥2，故恰为所述语言的非空部分。

p.71 A language L is context sensitive if and only if L is accepted by a Linear-Bounded automaton

这是文法与机器的等价，不等于 LBA 与一般图灵机等价。非收缩文法要生成长度 n 的目标串，中途不必也不能超过 n 后再缩回，因此可用线性工作区保存当前句型并猜测下一条规则。反方向以带格变量和状态变量模拟 LBA 的局部变化，所有工作符号留在输入对应的线性空间内；接受后再将编码转成目标终结符。这里给的是两方向的构造思路，课件未列出通用转换的逐条产生式。

图（p.71）：上下文有关语言与递归语言的关系。元素：向 Recursive language 的箭头有绿色允许标志，反向箭头有红色禁止标志。看什么：每个 CSL 可判定，而递归语言不必是 CSL。原因不是 LBA 的每条实际运行都会停机，而是固定输入长度只有有限种配置，可以搜索完整配置图，查有无到终态的路径。

补充算例（数字为演示自取）：若固定工作区3格，带字母表2种，状态4个，读头3种位置，则配置至多4×3×2³=96个。记录访问过的配置，重复配置不再扩展，最多处理96个节点后即可确定有没有接受路径。通用判定机可以用更多空间存这些节点，因此这个证明不声称判定模拟本身也只用线性空间。

考试角度：（C 级通识）常见考法是检查非收缩条件、逐步导出 aabbcc，或说明“所有分支可能循环”为什么不妨碍用有限配置图判定语言。

从文法本身也能看出成员判定为何有限（补充）

给定长度 n 的目标串 w，非收缩规则使成功推导不可能先超过 n 再缩回来。所以只需搜索长度至多 n 的句型；若变量和终结符合起来有 g 种符号，这些候选至多 $\sum_{j=0}^{n}g^j$ 个。每个句型只展开一次，将匹配规则产生的新句型加入队列，超过 n 的候选直接丢弃；队列清空仍没有 w 就可拒绝。每次展开有限，候选总数有限，因此保证结束，即使某些规则互相循环。

这个解释依赖非收缩条件，不适用于上一部分 S→aBc→cAc→cd 那种中途超长再收缩的推导。它也不声称算法高效：有限候选仍可能指数多，保存全部已访问句型可能使用远多于线性的空间。证明可判定只需存在总停机算法，不要求它达到 LBA 的空间界。

自检：A→B、B→A 都不缩短，能据此说算法总会停吗？

区分原推导分支与带去重的搜索算法。

展开推理与答案

原推导可无限来回；判定算法将已访问句型去重，A/B 各处理一次后不再重复。停机性来自有限搜索空间加去重，而不是“每条非收缩规则都会严格增长”。

本讲核心考点

非收缩限制是每条规则右侧长度至少等于左侧（p.69，C 级）。
A 右移、B 左移的一轮让 a、b、c 各增加1（p.70，C 级）。
CSL 对应 LBA；有限配置图给出 CSL 可判定性（p.71，C 级）。

附录

A1 从二段计数同步增加到三段计数（p.70）

从上一轮继续形式 aaAbbcc 开始，按原规则逐步得到：

\begin{aligned} aaAbbcc&\Rightarrow aabAbcc\\ &\Rightarrow aabbAcc\\ &\Rightarrow aabbBbccc\\ &\Rightarrow aabBbbccc\\ &\Rightarrow aaBbbbccc\\ &\Rightarrow aaabbbccc. \end{aligned}

回到正文：三段等量文法

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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.69–71；页脚 Ch 11。
本次独立学习修订：核对合讲140页文本，视觉复核 p.38、60、70–71、83、94；补全正文证明并保留原页与补充构造的区分。