[!note] CFG 几乎每年都会考察，常见题型包括：

• 根据 Grammar 判断生成的 Language。

• 写出某个字符串的 derivation（推导）或 parse tree（语法树）。

• 判断 grammar 是否 ambiguous（二义的）。

• 构造满足要求的 CFG。

• Chomsky Normal Form（计算理论-CH07-CNF乔姆斯基范式）的转换。

• 利用 CFG 描述括号匹配、回文、相同数量字符等语言。

上下文无关文法 (CFG) 基础与真题通关笔记

本笔记专为准备大阪大学工学研究科（情报工学）“计算理论”考试的考生设计。CFG（Context-Free Grammar）是历年真题中的高频必考点，考察重点高度稳定。本笔记将带你从零基础夯实概念，直至熟练攻克真题。

学习路线图与核心考点

在学习了语言（Language）、有穷自动机（DFA/NFA）、正则表达式（RE）之后，引入 CFG 是为了解决正则语言无法描述具有“匹配、嵌套或计数关系”（如 $a^n b^n$、括号配对）的语言这一局限性。

大阪大学的核心考察重点包括：

1. 产生式推导：根据文法判断字符串是否能被生成（Derivation）。

2. 最左推导 (LMD) 与 最右推导 (RMD) 的书写。

3. 推导树 (Derivation Tree / Parse Tree) 的绘制。

4. 文法二义性 (Ambiguity) 的判断与证明。

5. 满足特定要求的 CFG 构造。

6. 乔姆斯基范式 (CNF) 的转换（进阶考点）。计算理论-CH07-CNF乔姆斯基范式

7. CYK 算法 的应用（进阶考点）。计算理论-CH08-CYK-算法

第一部分：初识 CFG —— 从“读”到“造”

1. 哲学观的转变

• DFA/NFA：是一个 “读字符串” 的判定机器。你给它一个字符串，它一步步读取字符，最后告诉你“接受”或“拒绝”。

• CFG：是一个 “造字符串” 的规则生成系统。它从一个起始符号开始，根据既定规则不断替换，直到吐出一个只包含终结符的字符串。

2. 规则直观演示

设有规则系统：

1. $S \to aSb$

2. $S \to \epsilon$ （其中 $\epsilon$ 表示空串，即长度为 0 的字符串）

我们可以通过如下的“改写”步骤生成字符串：

$S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aaaSbbb \Rightarrow aaa\epsilon bbb = aaabbb$

起承转合：为了规范这种“造词”系统，并进行精确的数学分析，我们需要给出 CFG 的形式化定义。

第二部分：CFG 的形式化定义（四元组）

⚠️ 纠错说明：在一些非正式资料中，有时会把 CFG 误称为“五元组”，但在列出定义时却只给出四个元素。在计算理论的学术规范中，CFG 严格定义为四元组（4-tuple）。

形式上，一个上下文无关文法 $G$ 是一个四元组：

$G = (V, \Sigma, R, S)$

其中：

• $V$：变量集合 (Variables)，又称非终结符 (Non-terminals)。通常用大写字母表示（如 $S, A, B$）。它们是推导过程中的占位符，可以被继续替换。

• $\Sigma$：终结符集合 (Terminals)。通常用小写字母或数字、符号表示（如 $a, b, 0, 1, +, *$）。它们是语言的基石，一旦生成，不能再被替换。

• $R$：规则/产生式集合 (Rules / Productions)。每一条规则的形式为：

  $A \to \gamma \quad (\text{其中 } A \in V, \gamma \in (V \cup \Sigma)^*)$

  意为：“可以将变量 $A$ 替换为符号串 $\gamma$”。

• $S$：开始符号 (Start Symbol)，且 $S \in V$。它是推导的起点。

示例解析

在产生式 $S \to aSb$ 中：

• Variable 是 $S$

• Terminal 是 $a, b$

第三部分：核心操作 —— 重写（Rewrite）与推导（Derivation）

理解“重写”是学好 CFG 的第一步，许多初学者在此处容易产生两个致命的误区。

💡 误区纠正一：重写 (Rewrite) 是全局替换（Ctrl+H）吗？

答：不是！ 在标准的 CFG 单步推导中，每一次重写只能应用一条规则，替换字符串中的某一个非终结符（Variable）。

如果当前的句型为 $SS$，且有规则 $S \to aSb$：

• 合法单步推导：$SS \Rightarrow aSbS$ 或者是 $SS \Rightarrow SaSb$。

• 非法推导：$SS \Rightarrow aSbaSb$ （不允许在一步内同时替换两个 $S$）。

💡 误区纠正二：只要被规则推导出来的串，都属于该文法的语言（Language）吗？

答：绝对不是！ 我们要严格区分以下两个概念：

1. 句型 (Sentential Form)：推导过程中的中间字符串，可能包含 Variable（如 $aSb$, $aaB$）。它们只是中间状态，不属于该文法生成的语言。

2. 句子 (Word/String)：完全由 Terminal（终结符）构成的最终字符串。只有当一个串不包含任何 Variable 时，它才真正属于该文法生成的语言 $L(G)$。

我们可以把 Variable 看作“未完成的待办事项”，把 Terminal 看作“已完成的具体动作”。

字符串	是否还含有 Variable	是否属于 Language $L(G)$	说明
$S$	有 ($S$)	❌ 否	初始状态
$aAB$	有 ($A, B$)	❌ 否	中间句型
$aaB$	有 ($B$)	❌ 否	中间句型
$aab$	没有	是	最终句子

✍️ 手写笔记例题纠错与深度解析

在手写笔记中，分析文法 $S \to 1S \mid 0$ 时，曾将中间过程 $15$ (即 $1S$)、$115$、$1115$ 当作了生成的字符串。

【正确推导示范】 已知文法：

$S \to 1S \mid 0$

我们来推导前 4 个真正属于该语言的字符串：

1. 直接使用结束规则：$S \Rightarrow 0$

2. 递归一次后结束：$S \Rightarrow 1S \Rightarrow 10$

3. 递归两次后结束：$S \Rightarrow 1S \Rightarrow 11S \Rightarrow 110$

4. 递归三次后结束：$S \Rightarrow 1S \Rightarrow 11S \Rightarrow 111S \Rightarrow 1110$

规律总结： 每次使用 $S \to 1S$，就会在头部累加一个 $1$；最后必须且只能使用一次 $S \to 0$ 来消除占位符 $S$，从而结束递归。 因此，该文法生成的语言写为数学形式：

$L(G) = \{1^n 0 \mid n \ge 0\}$

第四部分：推导的两种流派 —— 最左推导与最右推导

当一个句型中同时出现多个 Variable 时，我们可以选择不同的替换顺序。这就衍生出了两种规范推导方式。

1. 核心定义

• 最左推导 (Leftmost Derivation, LMD)：在推导的每一步中，只选择当前句型中最左边的 Variable 进行替换。

• 最右推导 (Rightmost Derivation, RMD)：在推导的每一步中，只选择当前句型中最右边的 Variable 进行替换。

2. 经典例题剖析

【题目】 设 CFG 为：

S \to AB$$$$A \to aA \mid a$$$$B \to bB \mid b

请分别写出生成字符串 $aabb$ 的最左推导与最右推导。

❌ 常见推导错误分析

在手写笔记尝试中，曾写出过：$aaAB \Rightarrow aaaAB$。

• 错误原因：CFG 的规则中没有“$aaA \to aaaA$”这样带有上下文环境的规则（那是上下文相关文法）。我们只能利用 $A \to aA$。

• 改正方案：只能对其中的 $A$ 进行替换，$aaAB \Rightarrow aa(aA)B = aaaAB$。

🟢 最左推导 (LMD) 过程

每一步都在下方画线的非终结符上应用产生式：

$\underline{S} \Rightarrow \underline{A}B \Rightarrow a\underline{A}B \Rightarrow aa\underline{B} \Rightarrow aab\underline{B} \Rightarrow aabb$

(解析：优先替换最左侧的 $A$，直到 $A$ 完全转化为终结符后，才开始处理 $B$)

🟢 最最右推导 (RMD) 过程

每一步都在下方画线的非终结符上应用产生式：

$\underline{S} \Rightarrow A\underline{B} \Rightarrow A b\underline{B} \Rightarrow \underline{A}bb \Rightarrow a\underline{A}bb \Rightarrow aabb$

(解析：优先替换最右侧的 $B$，直到 $B$ 完全转换为终结符后，才回头处理 $A$)

第五部分：推导树 (Derivation Tree / Parse Tree)

1. 推导树的哲学

对于同一个文法，最左推导和最右推导的“展开顺序”虽然不同，但它们生成的语法层次结构（推导树）是完全相同的。 推导树并不关心谁先展开、谁后展开，它只关心谁是谁的子节点。

2. 绘制规范

• 根节点：必须是开始符号 $S$。

• 分支节点：必须是变量 (Variable)。

• 叶子节点：可以使终结符 (Terminal) 或 $\epsilon$。

• 读取规则：从左到右读所有叶子节点，即得到最终的 Terminal 字符串。

针对上一节推导 $aabb$ 的推导树，其结构如下：

       S
      / \
     A   B
    / \ / \
   a  A b  B
      |    |
      a    b

叶子节点从左到右读：$a - a - b - b \Rightarrow aabb$。

第六部分：上下文无关语言（CFL）与正则语言的区别

为什么有穷自动机（DFA/NFA）描述不了 $L = \{a^n b^n \mid n \ge 0\}$？

• 正则语言的局限：DFA 只有有限个状态，没有外部记忆。当它读取了 $n$ 个 $a$ 后，它无法“记住”精确的 $n$ 值，从而无法匹配后续相同数量的 $b$。

• CFG 的优势：利用产生式的递归嵌套性（如 $S \to aSb$），CFG 可以在向外层扩展时，天然保证左右两边的字符对称增加。

第七部分：重难点冲刺 —— 二义性文法 (Ambiguous Grammar)

这是大阪大学几乎每年必考的难点和核心考点。

1. 什么是二义性？

如果对于文法生成的同一个最终字符串，存在两棵不同的推导树（或等价地，存在两个不同的最左推导 / 两个不同的最右推导），则称该文法是 二义性文法 (Ambiguous Grammar)。

⚠️ 核心避坑指南：

• 很多同学误以为“一个符号有两条推导规则就是二义性”。错！ 比如 $S \to a \mid b$ 绝对不是二义性文法。

• 二义性的判定焦点在：最终输出的句子是否有歧义（即同一个句子是否有两种不同的理解/剖析方式）。

2. 字符的属性澄清

在分析二义性题目时，常常会遇到算术表达式文法：

$E \to E + E \mid E * E \mid (E) \mid a$

请注意，这里的 $+$、$*$、$($、$)$ 并不是任何运算指令，它们只是纯粹的 Terminal（终结符），就和普通的字符 $a, b$ 一样。

3. 经典案例演练

案例一：无运算优先级带来的二义性（算术表达式）

对于上述文法 $E$，目标字符串为：$a + a * a$。

• 理解一（先乘后加）：对应树结构中，将 $*$ 放在更深的层级：

        E
       /|\
      E + E
      |  /|\
      a E * E
        |   |
        a   a

  该树对应的语义是：$a + (a * a)$。

• 理解二（先加后乘）：对应树结构中，将 $+$ 放在更深的层级：

        E
       /|\
      E * E
     /|\  |
    E + E a
    |   |
    a   a

  该树对应的语义是：$(a + a) * a$。

由于同一个字符串 $a + a * a$ 拥有两棵完全不同的推导树，该文法具有二义性。

案例二：自拼接产生的二义性（手写笔记原题）

【题目】 证明文法 $S \to SS \mid a$ 是二义性文法。

【证明】 我们选取目标字符串 $aaa$。尝试为其画出推导树。

• 推导树一（偏右组合）：

        S
       / \
      S   S
      |  / \
      a S   S
        |   |
        a   a

  最左推导过程：$S \Rightarrow \underline{S}S \Rightarrow a\underline{S} \Rightarrow a\underline{S}S \Rightarrow aa\underline{S} \Rightarrow aaa$

• 推导树二（偏左组合）：

        S
       / \
      S   S
     / \  |
    S   S a
    |   |
    a   a

  最左推导过程：$S \Rightarrow \underline{S}S \Rightarrow \underline{S}SS \Rightarrow a\underline{S}S \Rightarrow aa\underline{S} \Rightarrow aaa$

由于针对字符串 $aaa$ 存在两棵结构不同的推导树，因此该文法是 Ambiguous Grammar。

💡 考场绝招：如何快速在考试中寻找引发二义性的字符串？

通常有以下三种高概率特征，看到它们要高度怀疑二义性：

1. 自拼接规则 (Self-concatenation)： 如 $S \to SS$。这种规则极易导致分组歧义。只要把三个或以上的终结符连在一起（如 $aaa$），就能分出 $(S)(SS)$ 和 $(SS)(S)$ 两种结构。

2. 缺乏优先级的运算符规则： 如 $E \to E + E \mid E * E$。由于文法中没有限定 $+$ 和 $*$ 的高低层级，对混合运算串（如 $a+a*a$）必然产生歧义。

3. 混合的递归方向： 如 $S \to aS \mid Sa \mid a$。对于字符串 $aaa$，我们既可以先在左边加 $a$，也可以先在右边加 $a$，容易产生不同形态的细长树。

第八部分：真题模拟与通关演练

为了检验学习成果，请独立完成以下两道极具大阪大学代表性的练习题，并核对解析。

练习题 1：二义性判断

【题目】 判断下面两个文法 $A$ 与 $B$ 是否是二义性文法（Ambiguous）。如果是，请给出证明；如果不是，请简要说明理由。

• 文法 A：$S \to aSa \mid a$

• 文法 B：$S \to SS \mid a$

【文法 A 解析】

• 结论：Unambiguous（无二义性）。

• 分析： 文法 $A$ 只能生成奇数长度的、完全由 $a$ 组成的对称字符串（即 $a$, $aaa$, $aaaaa$ …）。 对于任意合法长度为 $2n+1$ 的字符串 $a^{2n+1}$，它的推导树有且只有一种：每一次展开都必须对称地在两边套上一个 $a$，直到最中心的一步使用 $S \to a$ 结束。 例如字符串 $aaa$ 的唯一推导树为：

      S
     /|\
    a S a
      |
      a

  无法画出第二棵不同的树，故文法 A 是无二义性的。

【文法 B 解析】

• 结论：Ambiguous（有二义性）。

• 分析： 如第七部分“案例二”中所证，字符串 $aaa$ 能够产生两棵不同的推导树，因此它是二义性的。

练习题 2：括号序列文法设计（真题变式）

【题目】 设 $\Sigma = \{(, )\}$。请构造一个满足要求的 CFG，使其生成的语言为所有合法的括号配对序列（即每一个左括号都有右括号与之配对且顺序正确，包括空串 $\epsilon$）。

【参考答案与思路】

这是一个经典的文法设计问题。我们需要考虑合法的括号序列是如何构成的：

1. 基础情况：空串 $\epsilon$ 是合法的。

2. 嵌套情况：如果 $S$ 是合法的，那么将它外面套上一对括号 $(S)$ 也是合法的。

3. 拼接情况：如果两个括号序列 $S$ 和 $S$ 分别都是合法的，那么把它们连在一起 $SS$ 同样也是合法的。

由此，我们可以写出产生式规则：

$S \to SS \mid (S) \mid \epsilon$

🔍 验证推导：生成字符串 ()()

最左推导过程：

$\underline{S} \Rightarrow \underline{S}S \Rightarrow (\underline{S})S \Rightarrow (\epsilon)S \Rightarrow ()\underline{S} \Rightarrow ()( \underline{S} ) \Rightarrow ()(\epsilon) \Rightarrow ()()$

推导树结构：

       S
      / \
     S   S
    /|\ /|\
   ( S ) ( S )
     |     |
     ε     ε

该文法完美符合要求（注意：该文法由于有 $S \to SS$，它也是一个二义性文法。比如对 ()()() 存在不同的划分）。