CSCI3130 L05 Part 1 上下文无关文法

课程：CSCI3130 Formal Languages and Automata Theory · 资料包，学期待核 本讲：L05 Part 1 上下文无关文法 · 原件 L05-上下文无关文法-资料包.pdf（本地课件） p.1–38 定位：先用规则生成配对结构，再区分句型、推导顺序和推导树。 前后：下一份 L05-P2-解析与歧义.md

p.1 标题页；p.2 Outline。

本讲导航

1. P1 上下文无关文法：p.1–38。
2. P2 解析与歧义：p.39–79。
3. P3 程序语言：p.80–90。

为什么离开有限状态（p.3–5）【新】

p.3 展示正则语言不能覆盖等量计数和任意深度的镜像匹配；p.4 把它们放进更大的上下文无关语言类。p.5 给两种对应描述：CFG 从规则生成，PDA 用栈识别。栈允许后进先出地保存未匹配的信息；这里先学文法，具体自动机后面再定义。

上下文无关指左侧不依赖邻居（p.6–8）

p.7 We say that the grammar is context-free since this substitution can take place regardless of where A is.

p.6 回顾正则文法。p.7 放宽为 $A\to x$，左侧必须单个变量，右侧 x 可以是任意变量和终结符串。无论 A 左右是什么，都可用同一规则替换，所以叫上下文无关。p.8 定义 $L(G)=\{w\in T^{\ast}:S\Rightarrow^{\ast}w\}$。正则、线性文法都属于 CFG，但 CFG 允许右侧多个变量，不再必须线性。

四元组的每个位置（p.7–8）：$V$ 是可替换的变量集合，$T$ 是最终输出的终结符集合，二者不相交；$S\in V$ 是开始变量；$P$ 是有限产生式集合。$\Rightarrow$ 表示恰好应用一次规则，$\Rightarrow^{\ast}$ 表示零次或多次；只要还留变量，就只是句型，不能算已经生成的语言成员。

例如有 $A\to aAb$，在 xAy 中允许变成 xaAby，在 BAA 中也能选任意一个 A 展开；规则的适用性不检查 A 的邻居。这正是“上下文无关”的含义，不是说整串结构没有关系。p.6 的右线性 $S\to abS\mid a$ 和左线性 $S\to Aab,A\to Aab\mid B,B\to a$ 都满足左侧单变量，因此都是 CFG。

成对增加两个边界（p.9–11）

p.9 语言为 CFL 当且仅当存在 CFG 恰好生成它；“能生成几个成员”还不够。p.10 的 $S\to aSb\mid\lambda$ 每轮左添 a、右添 b：$S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$。p.11 再绕一轮得到 aaabbb。每次产生式替换的对象只有中间 S，已经输出的 a、b 不再被改动。

等量串与偶数回文（p.12–14）

p.12 得 $\{a^nb^n:n\ge0\}$；讲义的括号图只表示“所有左括号后接所有右括号”的完全嵌套形状，还不是任意平衡括号串。p.13 用 $S\to aSa\mid bSb\mid\lambda$，每步添相同两端：$S\Rightarrow aSa\Rightarrow abSba\Rightarrow abba$。p.14 加第三层 a 得 abaaba。每轮加2个字符，从空串出发，所以仅偶数长度回文。

线性 CFG 的输出可以很复杂（p.15–17）

p.15 回文文法生成 $ww^R$，在至少两个字母的字母表上非正则。

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

p.16 A context-free grammar: G

$S\to abB,\quad A\to aaBb\mid\lambda,\quad B\to bbAa$.

p.16 推导为 $S\Rightarrow abB\Rightarrow abbbAa\Rightarrow abbbaaBba\Rightarrow abbbaabbAaba\Rightarrow abbbaabbaba$。p.17 总结 $ab(bbaa)^nbba(ba)^n$。看 B 的完整回路：$B\Rightarrow bbAa\Rightarrow bbaaBba$，左添 bbaa、右添 ba；最后 $B\Rightarrow bbAa\Rightarrow bba$。因此 n 轮恰得该形式，前面固定 ab 不参加计数。全部规则右侧至多一个变量，所以线性；左右同时输出说明它并非正则文法。

把不等拆成两种严格大小（p.18–20）

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

p.18 The language $L=\{a^nb^m:n\ne m\}$ is context-free.

先让 $S_1\to aS_1b\mid\lambda$ 生成等量核心。$A\to aA\mid a$ 生成至少一个额外 a，$B\to bB\mid b$ 生成至少一个额外 b；用 $S\to AS_1\mid S_1B$ 分别覆盖 n>m 与 n<m。A、B 的最短输出不能空，否则会误加入 n=m。

p.19–20 换成 $S\to aSb\mid SS\mid\lambda$：除嵌套外，SS 允许连接两个平衡块。p.19 $S\Rightarrow SS\Rightarrow aSbS\Rightarrow abS\Rightarrow ab$；p.20 在最后的 S 再生成 ab，得到 abab。前一个单变量嵌套文法生成不了 abab，这说明增加 SS 扩大了语言。

平衡括号与推导顺序（p.21–23）

p.21 两条条件必须一起满足：总数 $n_a(w)=n_b(w)$；每个前缀 v 都有 $n_a(v)\ge n_b(v)$。总数相等只表示最终账目平衡，前缀条件禁止在还没有左括号时先关闭。ab、aabb、abab 均满足；ba 虽总数相等却违反首前缀。

p.22 文法 $S\to AB,A\to aaA\mid\lambda,B\to Bb\mid\lambda$ 在 AB 句型中有两个可展开位置。p.23 最左推导总先改最左变量，最右推导总先改最右变量：

两者完成同一棵树的不同访问顺序，不能据此断言歧义。

平衡前缀为什么足以找递归结构（补充）：将 a 记为加1、b 记为减1。对任意非空合法括号串，首字符必为 a，否则第一个前缀已为负。沿前缀计数走，第一次回到0的位置必为某个 b；于是串可唯一按这个首次回零点拆成 $a u b v$。u 本身平衡，因为外层 a 提供的那一层扣掉后，内部计数仍不负且最终回零；v 也平衡，因为前一块已经完整结账。

因此原文法可先用 $S\to SS$，左边 S 用 $aSb$ 包住 u，右边 S 生成 v。例 aabbab 的计数为1、2、1、0、1、0，首次回零在第4位，所以 u=ab、v=ab；它来自“一个嵌套块 aabb”接“一个块 ab”。这个分解补上任意平衡串都能生成的理由；仅数总 a、b 相同会误收 ba，前缀条件才保证能按这种结构递归。

把替换关系画成树（p.24–26）【新】

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

p.24 $S\to aAB,\quad A\to bBb,\quad B\to A\mid\lambda$.

讲义对 abbbb 的最左推导为 $S\Rightarrow aAB\Rightarrow abBbB\Rightarrow abAbB\Rightarrow abbBbbB\Rightarrow abbbbB\Rightarrow abbbb$。最右推导先消最右 B，再把 A 内部 B 扩成 A：$S\Rightarrow aAB\Rightarrow aA\Rightarrow abBb\Rightarrow abAb\Rightarrow abbBbb\Rightarrow abbbb$。两个展开次序不同，但对应同一组选定规则。

p.25 推导树把一次 $A\to abABc$ 画成 A 的五个有序孩子 a、b、A、B、c。p.26 规定根 S，内部点为变量，叶子为终结符或空串，每个父子组合必须是一条规则；空串叶子不得有兄弟，因为产生式右侧是整个空串，不是“空串再加别的符号”。

从根逐步长出树（p.27–29）

p.27 根 S 先有 A、B 两孩子。p.28 左孩子 A 用 aaA 展开；p.29 右孩子 B 用 Bb 展开。此时叶子从左到右为 aaABb，仍有变量，是未完成句型。树的水平顺序不能任意交换；交换 A、B 会把所有 a、b 的相对顺序改掉。

完整树的 yield（p.30–32）

p.30 内部 A 变空串，p.31 内部 B 也变空串，全部叶子终结。p.32 从左到右读叶得 $aa\lambda\lambda b=aab$，这称为 yield。读树不是把每层从上到下串起来；父节点是结构标签，不是输出字符。

p.31–32 的完整树也可用下列缩进完整表示；同一层从左到右的顺序就是原图孩子顺序：

S
├─ A
│  ├─ a
│  ├─ a
│  └─ A
│     └─ λ
└─ B
   ├─ B
   │  └─ λ
   └─ b

忽略内部变量并按叶子从左到右读，正是 aaλλb。p.36 的另一棵完整树则为 S(a,A(b,B(λ),b),B(A(b,B(λ),b)))，括号内列有序孩子。它把四个 b 分到左右两个子树各两个，与 p.24 把四个 b 全放左边不同。

部分树仍可能有变量叶子（p.33–35）

p.33 的部分推导树允许根不是 S，允许叶子保留变量；每个已展开的父子关系仍须合法。p.34 仅 A 展开后，右边 B 没展开，树仍合法；p.35 yield=aaAB，属于句型而非终结串。只有根为 S 的部分树，其 yield 才能直接称为整份文法的可达句型。

树与推导的双向对应（p.36–38）

图（p.36）：左部分树输出 abBbB，右完整树输出 abbbb。看什么：右图先让左 A 内的 B 消空、右 B 变 A 再生成 bb；这是另一种分配四个 b 的树，和 p.24 那棵把四 b 都放在左 A 的树不同。仅知道最后字符相同，不能把两图当作相同结构。

p.37 定理说每个生成串有推导树，每棵完整树的 yield 都是生成串。从推导到树，每次替换给对应变量叶子添孩子；从树到推导，按最左未展开变量的顺序应用节点规则。p.38 再用 aab 示例说明最左与最右访问同一棵树，所以“不同一般推导”不自动构成歧义。

考试角度：（C 级 通识）常见考法是从树读 yield、给定串写最左/最右推导，或用前缀条件区分平衡括号与仅计数相等。

考试角度：（A 级：HW03-2025T1-题目.pdf Q2–Q3，考的是区间计数文法与推导树。）见附录 A1。

考试角度：（A 级：期中练习-含解答-学期待核.pdf Q5(1,3)；Final-Exam-2023T1-题目.pdf Q4；期末-2023T1-资料包.pdf Q4，对应最短推导、首尾约束与模5约束；扫描件视觉读取。）见附录 A2。

本讲核心考点

• CFG 左侧单变量、右侧任意串（p.7–9，C 级）。
• 嵌套、连接与平衡括号（p.10–21，C 级）。
• 最左/最右推导及 yield（p.22–38，C 级）。

附录

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

A1 作业/往年题演练（非讲义内容）：区间计数文法与推导树

题面块（HW03-2025T1-题目.pdf（本地课件） · Q2 · p.1；公式按原件重排）：

p.1 (20pts) Find context-free grammars for the following languages (with $n\geq0,m\geq0,k\geq0$):

p.1 1) $L=\{a^n b^m:2n\leq m\leq3n\}$.

p.1 2) $L=\{a^n b^m c^k:k\geq3\}$.

1）S→aSbb或aSbbb或λ。n次递归各加一个a、两个或三个b，因此m=2n+t，0≤t≤n。反过来目标m取t=m−2n次三b规则，其余用二b即可。n=2,m=5时S⇒aSbb⇒aaSbbbbb⇒aabbbbb；n=0只能m=0，λ正确。

2）S→ABC，A→aA或λ，B→bB或λ，C→cccD，D→cD或λ。独立控制前两段非负长度，C确保至少3个c。abcccc可取A一次a、B一次b、D一次c。每个规则都不打乱段序。

题面块（同文件 · Q3 · p.1）：

p.1 (20pts) Show a derivation tree for the string abbbb with the grammar:

规则S→aAB或λ，A→bBb，B→A或λ。选择根的右侧B取λ，让左A中的B再展开A，内层A中的B取λ：

S
├─ a
├─ A
│  ├─ b
│  ├─ B
│  │  └─ A
│  │     ├─ b
│  │     ├─ B
│  │     │  └─ λ
│  │     └─ b
│  └─ b
└─ B
   └─ λ

非空叶从左到右为a,b,b,b,b。对应最左推导S⇒aAB⇒abBbB⇒abAbB⇒abbBbbB⇒abbbbB⇒abbbb，逐步与树对应。λ叶不计一个输入字符。

回到正文：区间计数文法与推导树

A2 作业/往年题演练（非讲义内容）：最短推导、首尾约束与模5约束

题面块（期中练习-含解答-学期待核.pdf（本地课件） · Q5(1) · p.4–5）：

p.4 Give the shortest yield generated by the CFG over alphabet {0, 1} with start variable S:

规则S→AB或BA；A→S0或1；B→S1或0。

p.5 Also give a derivation tree for a shortest string.

S首次展开至少有A、B两变量，每个至少出一个终结符，故长度至少2；直接A→1、B→0达到2。最短串有10和01两条。10的树为S的有序孩子A、B，A叶1、B叶0；01的树为S的孩子B、A，B叶0、A叶1。原资料在“01”的文字下画A/B、1/0的树，实际叶序为10；不能照其标题误读树。

题面块（同文件 · Q5(3) · p.5；公式重排）：

p.5 Let $\Sigma=\{a,b\}$ and define $L=\{w\in\Sigma^{\star}:\operatorname{len}(w)\geq2\text{ and (w starts with a and ends with b)}\}$. Give a context–free grammar (CFG) that generates L.

取S→aMb，M→aM或bM或λ。两端固定保证长度至少2，M生成任意中间串。ab由M空，aaabb由M生成aab；反向任何符合首尾的串删去两端就是M可生成的中间串。

题面块（Final-Exam-2023T1-题目.pdf（本地课件） · Q4 · p.2；期末-2023T1-资料包.pdf（本地课件） 同页同题，视觉核对为重复题面）：

p.2 Prove that the language $L=\{a^n b^n:n\geq0\text{ and }n\text{ is not a multiple of }5\}$ is a context-free language.

取S→aTb或aaTbb或aaaTbbb或aaaaTbbbb；T→aaaaaTbbbbb或λ。S选余数r=1、2、3、4，T每次同加5，因此n=r+5k。反向任何非5倍数非负n都有这种表示。0是5的倍数，不能生成λ，符合题意。n=6走S⇒aTb⇒aaaaaaTbbbbbb⇒aaaaaabbbbbb。存在CFG即证明CFL。

回到正文：最短推导、首尾约束与模5约束

来源与证据

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

• 原件：L05-上下文无关文法-资料包.pdf（本地课件），PDF p.1–38。

• 本次独立学习修订：核对本讲90页的文本，视觉复核 p.36、58、76、78、81–82、84、88–90；补全原规则、程序示意、推导树结构和搜索候选。