Context-Free Languages
Context-Free Language(上下文无关语言,CFL)恰好是Pushdown Automaton(下推自动机,PDA)能够接受的语言,且严格包含全部Regular Language(正则语言)。
The Chomsky Hierarchy
| 语言类别 | 识别装置 |
|---|---|
| Regular Language | Finite Automaton(有限自动机) |
| CFL | PDA |
| Context-Sensitive Language(上下文有关语言) | Linear-Bounded Automaton(线性有界自动机) |
| 无限制文法生成的语言(unrestricted) | Turing Machine(图灵机) |

Context-Free Grammars(上下文无关文法,CFG)
From Regular Expressions(正则表达式) to Grammars
CFG :通过递归替换规则描述 String(字符串) 的结构。
例如, Regular Expression 表示:先写一个 ,中间写任意多个 或任意多个 ,最后写一个 。用新符号表示尚未确定的部分,可以写成:
其中 表示完整 String, 表示中间部分, 分别生成全为 、全为 的 String。竖线是多个规则的简写,例如 表示 与 两条规则。
展开例子:如何生成 aaab?
最后使用 ,删去尚未展开的 。得到只含 的 String 后,生成过程完成。
“上下文无关”指规则的适用性与被替换符号左右两侧的内容无关。 只要有规则 ,任何 都可以变成 。例如, 出现在 aaAb 或 bAa 中时,均可应用同一条规则。
Definition and Derivations
CFG 是四元组:
- :有限的符号集合,包含文法中使用的全部符号。
- : Terminal(终结符) 集合,最终 String 由这些符号组成。
- : Nonterminal(非终结符) 集合,用于表示尚待展开的结构。
- :开始符号。
- :有限的 Production Rule(产生式) 集合;每条规则形如 ,左边恰好是一个 Nonterminal,右边可以是任意有限 String,包括空串 。
一步推导 表示在 中选定一个 Nonterminal 的出现位置,并按某条 Production Rule 替换一次:
是 的自反、 Transitive Closure(传递闭包),表示 零步或有限多步推导 。文法明确时省略下标 。
称为从 到 的一次推导,长度为 ,即应用规则的次数。中间串可以同时包含 Terminal 与 Nonterminal;从 可达的中间串称为句型。需要区分树结构时,还应记录每一步替换的是哪一个出现位置。
文法生成的语言为:
若存在 CFG 使 ,则 是 CFL 。
判断 ,只需找到一条从 到Terminal串 的有限推导。 某些其他选择可能无法结束。含有 Nonterminal 的中间串不属于 。
Examples
- Equal Counts in Two Blocks
生成:
每次应用 ,就在两端分别添加一个 与一个 ;最后用 结束。因此产生的 String 数量匹配,且所有 位于所有 之前。
反过来,任意 都可通过 次 ,再接一次 得到。这个语言是 CFL,同时它已被证明为 Nonregular Language(非正则语言)。
- Balanced Parentheses
生成所有正确配对的括号串。三条规则分别表示空串、两个合法括号串的连接,以及在合法括号串外添加一对括号。
判断一个括号串是否合法,需要同时满足:
- 左括号与右括号总数相同。
- 任意 Prefix(前缀) 中的左括号数不少于右括号数。
例如,(())() 合法,)( 虽然两类括号总数相同,仍不合法。
展开说明:为什么文法恰好生成全部合法括号串?
空串合法;连接两个合法串、在合法串外加一对括号,都保持上述两个条件,所以文法不会生成非法串。
对任意非空合法串,从第一个左括号开始,找到与它匹配的右括号,可以唯一分解成 ,其中 均为更短的合法括号串。按长度归纳,它们都能由 生成,于是:
空串由 生成,因此没有遗漏。
- Equal Numbers of a and b
这个文法生成:
其中 表示 中 的数量。 这里只约束数量,允许任意排列 ,例如 abba、baab、abab 均属于该语言。
展开完整证明:两个包含方向与首尾相同的情况
方向一:文法生成的String都有相同数量的 。
对推导步数作强归纳。一步得到的 Terminal 串只能是 ,结论成立。更长推导的第一条规则有三种可能:
- :两个子推导分别得到 。它们各自使用更少的步数,故均有相同数量的 ,连接后也相同。
- :内部串 的两类字符数量相同,再添加一个 和一个 ,仍相同。
- :同理。
方向二:两类字符数量相同的String都能生成。
对 作强归纳。 时直接使用 。非空串的首尾有四种组合。
若 ,则 中的 数量相同,由归纳假设 ,所以:
同理,使用 。
若 ,则 中的 比 多两个。需要将 切成 ,使 中都恰好多一个 。这一切分一定存在:从左到右扫描 ,记录 Prefix 的
从 走到 ,每步变化 ,因此必然经过 。在第一次到达 的位置切开,得到 ,且两段的差值均为 。于是 与 各自都有相同数量的 ,长度也都小于 。由归纳假设:
若 ,交换 ,采用相同论证。
两个方向合起来即得结论。
- Arithmetic Expressions
算术表达式可由以下文法生成,其中 是开始符号, 作为一个 Terminal 表示标识符:
分别表示表达式、项和因子。这个分层安排使得:加法组合各个项;乘法位于项的内部;括号允许把整个表达式作为一个因子。
因此,id+id*id 的结构是 ;(id+id)*id 则由括号显式改变分组。递归规则 与 还规定了同级运算的左结合方式。
展开推导:生成 id+id*id
From Finite Automata to Grammars
所有Regular Language都是CFL。 可以直接把 Deterministic Finite Automaton(确定性有限自动机,DFA) 的一次识别过程改写成文法的生成过程。
设 DFA 为 。先重命名状态,使 ,再构造:
状态成为Nonterminal;读入一个字符的转移,变为生成该字符并保留下一状态的规则;Final State(终态)允许结束生成。
展开证明:为什么 L(G)=L(M)?
若自动机在输入 上的运行是:
则对应文法推导:
当且仅当 时,可以再用 得到纯 Terminal 串 。
反过来,文法每次使用 都对应 DFA 的合法转移;唯一能消去最后一个状态符号的规则来自 Final State。因此文法生成 当且仅当自动机接受 。空串也被正确处理: 存在当且仅当 。
Example
自动机对应文法:
输入 aabbaba 对应状态序列 ,最后停在 Final State 。
展开与自动机运行逐步对应的推导
每一步中,左侧已生成的 Terminal 就是已读 Prefix,最右侧 Nonterminal 就是当前状态。

结合 为 CFL 且非正则,得到严格包含关系:
Parse Tree(分析树)
Structure and Yield(产出)
Parse Tree 把一次生成过程中的递归结构画成有序树。展开不同分支的先后次序可以变化,树仍可能相同。
对于文法 :
- 完整 String 的 Parse Tree 以 为根;讨论子树时,根也可以是其他符号。
- 内部节点标记 Nonterminal。若某节点标记 ,其孩子从左到右为 ,则对应规则 。
- 叶子标记 Terminal,或在 的情况下标记 。
- 从左到右连接全部叶子标记,得到树的 Yield ; 不贡献字符。

展开归纳定义:怎样严格构造一棵Parse Tree?
- 对每个 ,标记为 的单节点树是一棵 Parse Tree, Yield 为 。
- 若 ,以 为根、以一个 节点为孩子的树是一棵 Parse Tree, Yield 为 。
- 若已有 棵 Parse Tree ,根标记分别为 , Yield 分别为 ,且 ,则增加根 并按顺序连接这些子树,得到 Yield 为 的 Parse Tree。
- 只有通过以上规则有限次构造出的树,才属于 Parse Tree。
其中 可以是 Terminal 或 Nonterminal。 是专门表示空 Yield 的叶子标记,无需将它加入 Terminal 集合。
Similar Derivations
若两次推导使用相同的树结构,只改变不同分支的展开顺序,就称它们 相似 。
以括号文法 为例,以下两个推导都生成 (())(),也对应同一棵树:
两者都将根分成两个 :左子树生成 (()),右子树生成 ()。
展开形式化定义:一次交换与相似关系
假设某个句型中有两个不同位置的 Nonterminal:
并分别选择规则 、。先展开左边或先展开右边,可以得到:
若完整推导 除这两步的中间句型外完全相同,且 先展开左边的 ,就记 。这里交换的是两个独立位置;不能把展开父节点与展开其新生成孩子的步骤互换。
相似关系是 的自反、对称、Transitive Closure。 即允许做零次或有限次这样的交换,每次可以正向或反向交换。
因此,相似是 Equivalence Relation(等价关系);同一相似 Equivalence Class(等价类) 对应同一棵 Parse Tree。 本身只描述一次交换,通常不具有传递性。
三个推导:
有 、,但 ,因为最后这对推导需要两次交换。三者仍然相似。
另一条推导:
它额外使用了一次 和一次 ,树结构改变,因而与前三条不相似,尽管最终 String 相同。
Leftmost and Rightmost Derivations(最右推导)
Leftmost Derivation(最左推导) 每一步都展开当前句型中最左侧的 Nonterminal。一步 Leftmost Derivation 的形式为:
条件 保证 左侧已经没有 Nonterminal。
Rightmost Derivation 相应地每次展开最右侧的 Nonterminal。
固定一棵Parse Tree后,Leftmost Derivation与Rightmost Derivation各自唯一。 每一步展开的位置由方向确定,使用的规则由树确定。对同一个 Terminal 串,如果存在不同的 Parse Tree,就可能存在多条 Leftmost Derivation。
最左推导中的“最左”指最左侧的 Nonterminal 。例如在
id+T*F中应展开 ,前面的 Terminalid无需再展开。
Theorem
给定 与 ,以下四个命题等价:
证明思路:任意成功推导都可以记录成树;给定树后,按最左或最右顺序展开即可恢复推导。因此,为了证明一个串能生成,可以专注于 Leftmost Derivation,表达能力不会减少。
Ambiguity
如果存在某个 ,使它在同一个文法 中拥有两棵不同的 Parse Tree,就称 是 Ambiguous Grammar(歧义文法) 。
等价地,该 String 存在两条不同的 Leftmost Derivation,或两条不同的 Rightmost Derivation。
Ambiguous Arithmetic Expressions
考虑开始符号为 的文法:
同一个 String id+id*id 可以对应两种结构:
- 根使用 ,得到 。
- 根使用 ,得到 。
上面的括号用于说明树的分组含义;两棵树实际 Yield 的 String 都没有这些额外括号。因此,这个文法存在歧义。

展开两条Leftmost Derivation
以加法为根:
以乘法为根:
两次都始终展开最左侧 Nonterminal,第一步使用的规则已经不同,所以确实对应两棵树。
Ambiguous Parentheses Grammar
文法 本身也有歧义。最简单的例子是空串:
第二个推导可以选择每次消去最左侧的 ;两棵树分别使用一个、两个产生空串的子分支。
作为补充,可给出以下等价 Unambiguous Grammar(无歧义文法):
对非空合法括号串,第一个左括号的匹配位置唯一确定分解 ,再递归处理 ,就得到唯一的树结构。
文法歧义是某个表示的性质;Inherent Ambiguity(固有歧义)是语言的性质。 若一个 CFL 的所有 CFG 表示都存在歧义,称它具有 Inherent Ambiguity。一个具体文法有歧义,尚不能断言它的语言具有 Inherent Ambiguity。
Pushdown Automata
From Finite Automata to a Stack
Finite Automaton 只能通过有限个状态保存信息。处理回文串时,需要记住前半段并按相反顺序核对后半段;处理括号匹配时,需要保存尚未匹配的左括号。这些任务自然对应一个 Last In, First Out(后进先出,LIFO)的栈 。
PDA 在有限控制器之外增加一个栈。它从左向右读输入,可以读一个输入符号并操作栈,也可以暂时不读输入,只改变状态和栈。
栈允许使用任意有限的存储空间,但只能在栈顶操作。读取顺序与栈的存取方式共同决定了它的能力。

Formal Definition
采用六元组:
其中:
- :有限状态集;
- :输入 Alphabet(字母表);
- :栈 Alphabet,可以与输入 Alphabet 不同;
- :初始状态;
- : Final State 集;
- : 有限的 转换关系,满足
允许一次替换栈顶的一个有限String。 因此转换中的栈操作对象属于 ,长度可以为零、一个或多个符号;后面会把这种一般形式化成更受限制的 Simple PDA(简单 PDA)。
Transitions and Configurations(配置)
转换
表示:在状态 ,如果剩余输入以 开头、栈顶以 开头,就读掉 ,把栈顶的 替换成 ,进入 。
- 若 ,不消耗输入,读头保持不动。
- 若 ,不要求匹配任何栈符号,可以直接压入 ; 这也适用于非空栈,不能把它理解为“检查栈是否为空”。
- 若 ,弹出 。
- 若 ,栈保持不变。
例如, 读一个 并压入 ; 读一个 并弹出栈顶的 。
PDA 的 Configuration 写作
三个分量依次表示当前状态、 尚未读取的输入 、栈内容。本章始终约定 栈顶在左 :栈串 的栈顶是 ,栈底是 。
一次合法转换可以完整地写为:
其中 是保持不变的栈底部分。 是 的自反、 Transitive Closure,表示 零步或多步 计算。

Acceptance Conditions
初始栈为空。它接受 当且仅当
这要求某条有限计算同时满足: 输入读完、栈清空、进入Final State 。因此
一般 PDA 允许同一 Configuration 有多个可用转换。接受的含义是 存在一条成功的计算分支 ;某些分支卡住或无法接受,不妨碍其他分支接受。
Example
- Marked Palindromes
构造 PDA 接受
思路:读到 前将符号依次压栈;读到 后,逐个读输入并与栈顶配对弹出。 明确标出了前后两段的分界。
取
转换关系包含:
进入 后还需要继续读输入、清空栈,不能在刚读到 时就宣告接受。 时,输入 c 也在语言中。
展开例题:输入 abbcbba 的完整计算
压入的顺序是 ,弹出的顺序是 ,恰好核对 。若输入与栈顶不匹配,或输入读完后栈里仍有符号,这条分支不能接受。
- Even-Length Palindromes
对
沿用上例的两个状态和压栈、匹配转换,把分界转换改成
并取输入 Alphabet 。
在状态 ,机器可以继续读符号并压栈,也可以通过上述 转换切换到匹配阶段。这个选择相当于 非确定地猜测中点 。
猜得过早或过晚的分支会失败;输入确为偶数长度回文时,存在恰好在中点切换的分支。空串通过 接受。
- Equal Numbers of a and b
构造 PDA 接受
这里字符顺序任意。 栈保存已经读取的Prefix中尚未抵消的同类符号 :读到同类符号就压栈,读到异类符号就弹出一个;栈底保留标记 。
设 Prefix 为 ,用 、 分别表示其中的字符数量。令 ,则状态 下的栈始终满足
这个不变式同时给出了设计方法和正确性依据。
展开完整构造与输入 abbbabaa 的计算
取 ,,,。转换为
转换 (1) 放入栈底标记;(2)–(7) 更新数量差;(8) 在数量差为零时弹掉标记并进入 Final State。
不变式对空 Prefix 成立,每一种读入转换也保持它。因此读完整个输入后,栈只剩 当且仅当 数量相等。若尚有输入就提前使用 (8),由于 没有后续转换,这条分支不会接受。
Finite Automata as Pushdown Automata
任何 Finite Automaton 都可看成始终不使用栈的 PDA。将 Nondeterministic Finite Automaton(非确定性有限自动机,NFA) 的每条转换
替换为
其余状态、 Initial State(初态)、 Final State 保持一致,便得到相同语言。栈一直为空,所以接受条件与原 NFA 对齐。
这说明 PDA 至少能够接受所有 Regular Language;回文等例子展示了栈带来的额外能力。
Pushdown Automata and Context-Free Language
PDA 接受的语言恰好是CFL。 即
证明分为两个构造: CFG PDA:用栈模拟Leftmost Derivation;PDA CFG:用Nonterminal描述消去栈符号的计算片段。
Building a PDA from a CFG
给定 ,构造
栈 Alphabet 为 ,同时包含 Terminal 和 Nonterminal。 由三类转换组成:
- 初始化 :,把开始符号压栈。
- 展开Nonterminal :对每条规则 ,加入 。
- 匹配Terminal :对每个 ,加入 。
栈顶是 Nonterminal 时,选择一条生成规则展开;栈顶是 Terminal 时,必须与当前输入匹配。已匹配的 Prefix 不断被移除,下一次露出的 Nonterminal 就是当前句型的最左 Nonterminal。
Example
- A Grammar for Marked Palindromes
文法
生成 。对应 PDA 有一条初始化转换、三条展开转换、三条匹配转换,共七条。
展开七条转换、Leftmost Derivation与 abbcbba 的完整计算
文法的推导为
相应计算为
“展开一次文法规则”与“匹配一个 Terminal ”是两种不同操作,因此 PDA 的步数通常多于文法推导步数。
Correctness of the Construction
关键对应关系为:对 、,
这里 为空或以 Nonterminal 开头,表示已经把当前句型最前面的 Terminal 全部匹配完。取 ,并加上初始化一步,就得到 。
展开两个方向的证明
从推导到计算。 对 Leftmost Derivation 长度归纳。零步时 、,零步计算即可。
设最后一步为
其中 ,。由归纳假设,机器可以匹配 并到达栈 ;随后用对应转换把它改为 。
因为 、,其中 ,继续逐个匹配 ,便到达 。每一步都与最左展开及其新增 Terminal Prefix 对应。
从计算到推导。 设已经读掉输入 Prefix 、当前栈为 。维护不变式
初始化之后 、,成立。若转换展开栈顶 ,由于 全由 Terminal 组成,该转换恰好对应 Leftmost Derivation 的一步;若转换匹配栈顶 Terminal ,则“已读 Prefix ”变成 ,“剩余栈”去掉 ,两部分连接起来的句型保持不变。
因此整个计算保持不变式。到达 时已经读完 ,得到 。特别地,接受时栈也为空,故 。
Building a CFG from a PDA
反向构造先将一般 PDA 化为 Simple PDA,再把计算过程翻译成生成规则。
Simple Pushdown Automata
Simple PDA 要求:除 Initial State 发出的转换外,每条
均满足
也就是每步检查并替换 恰好一个栈顶符号 ,替换结果可以含零、一个或两个符号。 Initial State 需要例外,才能从空栈开始运行。
Converting to a Simple PDA
设原机为 。引入新的 Initial State 、唯一 Final State 、栈底标记 :
主计算中一直保留 ,使原来的“空栈”对应“仅剩 ”。只有原机已经到达 Final State 且栈清空时,才可移去 并到达 。 没有入边, 没有出边。
然后依次拆分一般栈操作: 先把一次弹出多个符号拆开,再把一次压入多个符号拆开,最后消除不检查栈顶的主计算转换。
展开三阶段构造与正确性要点
每次拆分都为该条原转换引入独立的新状态;这些状态只用于走完当前模拟,不能与其他转换的中间状态混用,也不设为 Final State。
第一阶段:将 拆成逐个弹栈。 对
引入 ,改为
先从左到右弹出前 个符号,最后一步读输入并完成替换。匹配失败会停在无法接受的中间状态;成功走完整段时,与原转换的效果相同。
第二阶段:将 拆成逐个压栈。 对
引入 ,改为
先放 ,最后放 ,使最终栈顶次序为 。这一阶段结束后有 、。
第三阶段:消除主计算中的 。 对 的每条
对所有 加入
它读取并原样保留旧栈顶 ,再将 放在前面。主计算中有栈底标记,所以总能取到某个 ;又因为前一阶段已使 ,现在有 。
最终得到
Meaning of the Nonterminals
记 。为每个 、 建立一个 Nonterminal
它表示这样一段输入:机器从状态 、栈顶为 开始,经过一段计算, 把 以及由它替换、压入的符号全部消去 ,到达状态 ,期间不读取或改变原先位于 下面的栈内容。
三个位置分别编码 起始状态、要消去的栈内容、结束状态 。它是文法的一个符号,内部的逗号和状态名只是命名方式。

当 ,该符号表示无需消去原有栈符号的计算片段;特别地, 可以直接生成空串。
新文法 的符号集为
Production Rules
生成规则分为四类。
1. 开始规则
是原 PDA 的 Initial State; 的初始化已经把机器带到状态 、栈为 。因此这条规则要求接下来的计算读完输入、清除 并到达 。
2. 替换为零或一个栈符号
若
则对每个 加入
先读 并用 替换 ,再完成“从 消去 到 ”的剩余任务。 时右侧不写任何输入符号。
若 ,配合第 4 类规则,立即弹栈的转换 可简写成 。
3. 替换为两个栈符号
若
则对所有 加入
先消去上面的 及其产生的符号,到达某个中间状态 ;随后才能处理下面的 。两个变量的连接顺序体现了栈的 LIFO 性质。必须枚举中间状态 ,因为它由具体计算决定。
4. 零步计算
Correctness of the Construction
核心命题为
这里讨论的是已经规范化的 ; 是一个栈符号或空串。
展开两个方向的证明与等价定理的收尾
生成规则对应计算。 对推导树归纳。规则 对应零步计算。第 2 类规则先执行一条 PDA 转换,再按归纳假设完成剩余计算。第 3 类规则先执行替换为 的转换,再依次完成两棵子树对应的计算:处理 时保留下面的 ,处理结束后再消去 。得到所需的整体计算。
计算对应生成规则。 对计算步数归纳。零步时必须有 、、,可用第 4 类规则。
若第一步把 替换为零或一个符号,余下计算直接对应第 2 类规则的一个子问题。若第一步将其替换为 ,考察此后 第一次将上方 对应的整段栈内容消去、露出 的时刻,记当时状态为 。栈只能从顶部操作,所以此前不会检查或改变 ;余下输入因此分成依次消去 、 的两段。对两段计算使用归纳假设,再用第 3 类规则连接,便得到整个输入的推导。
最后,由开始规则和上述命题,
两个方向均完成,得到 PDA 与 CFG 在语言表达能力上的等价性。
Example
Converting Individual Transitions
状态 、栈符号 上的六条转换:
展开六条转换对应的全部局部生成式
为简洁,写 代表 ,其余类同;此处先枚举原状态集中的中间状态 。直接弹栈的规则已合并生成空串的辅助变量。
由 (1) 得
由 (2) 得
由 (3) 得
转换后的状态是 ,所以右侧变量必须从 开始。课件第 65 页第一条右侧误写为 ,这里按转换定义修正。
由 (4)、(5) 得
由 (6) 得
这些规则可以通过产生输入的局部计算理解;完整文法的开始规则仍须由完整、确定的初始化与接受约定给出。
加入明确初始化与清栈阶段,完成 101 的计算和推导
初始化栈为 ;原六条转换运行到状态 并读完输入后,可以清空剩余栈接受。
增加 Initial State 、清栈状态 、唯一 Final State ,并加入
清栈阶段不读取输入, 也没有出边,所以提前清栈不会接受尚未读完的输入。新机仍按“输入读完、栈清空、进入 Final State ”接受。
输入 101 的计算是
对应文法以
开始,按扩大后的状态集生成各类规则。该计算所用的文法推导为
其中 来自原转换 (5), 来自新增的最后清栈转换。这个例子把“中间状态枚举”和“最终接受条件”连接起来。
Languages that are and are not Context-Free
怎样用已知语言构造新的 CFL,以及怎样证明一个语言超出了 CFL 的表达范围。
Closure Properties(封闭性)
CFL对并、连接、Kleene Star(星闭包)封闭。 给定两个文法 、,先重命名 Nonterminal,使它们彼此不冲突,也不与另一个文法的 Terminal 冲突;再引入新的开始符号 。
| 目标语言 | 保留的原规则 | 增加的规则 |
|---|---|---|
重命名很重要 :如果两个文法恰好都使用 Nonterminal ,直接合并规则可能使原本独立的推导相互混用,生成额外的 String。
展开三种构造的正确性说明
并集。 从 出发,第一步必须选择 或 ,之后只能沿对应文法推导。因此,生成的 String 恰好属于两个语言之一。
连接。 第一步得到 ;两个 Nonterminal 分别生成 、,最终得到 。反过来,任意这样的连接都能按此方式生成。
Kleene Star。 使用 共 次,再用 ,可得到 个 ,每一个独立生成 中的 String。 时直接生成空串。因此恰好覆盖零次或任意有限次连接。
结合基础语言 、 都是 CFL,也可再次说明: 所有Regular Language都是CFL。
Intersection with a Regular Language
CFL与Regular Language的交集仍是CFL。 设 ,其中 为 PDA;,其中 为 DFA。让一个新 PDA 同时记录两台机器的状态,并保留 的栈。

展开乘积构造与正确性说明
设
构造
对于 的转移 ,分两种情况:
-
若 ,两台机器读取同一个字符,加入
-
若 ,仅 PDA 执行空转移, DFA 保持原状态,加入
以上规则对每个 都加入。
新机器的第一状态分量和栈始终模拟 ;第二状态分量记录 读完同一输入 Prefix 后所在的状态。输入读完时,只有栈空且两个状态分量分别属于 才接受,因此
这个构造只需要一个栈。 若同时模拟两个一般 PDA,两者的栈信息无法直接塞进上述“有限状态乘积”中;不能据此推出两个 CFL 的交集 Closure Property。
Example
Equal Counts without Forbidden Substrings(子串)
证明以下语言是 CFL:
展开证明
拆成两个条件:
其中 已由前面的 CFG 或 PDA 构造证明为 CFL。包含禁止 Substring 的语言可由 Regular Expression 描述,取补集得到的 仍然正则。
由于 ,由交集定理可得 为 CFL。
“全局数量条件 + 正则局部限制”常适合用这一分解方法。
Parse-Tree Height and Yield Length
定义文法的 Fanout(最大分支数) 为所有 Production Rule 右部的最大长度:
无 Production Rule 时约定 ;空 Production Rule 右部长度为 。
本节的树高 按 根到叶子路径上的边数 计算。
引理:当 时,高度为 的Parse Tree,其Yield长度至多为 。 一个节点最多分出 条生成分支;层数有限时,能够产生的 Terminal 个数也有上界。空串叶子的 Yield 长度为 。
展开归纳证明
对树高归纳。先考虑 的情形。
当 时,根使用一个 Production Rule, Yield 长度至多等于该规则右部长度,故不超过 。高度为 的 Terminal 单节点树 Yield 长度为 。
若高度不超过 的每棵子树 Yield 长度都不超过 ,则高度为 的树至多包含 棵这样的子树, Yield 总长度至多
空 Production Rule 的 Yield 为空串,也满足上界。若所有规则右部都为空串,则该文法至多生成空串,不存在后续 Pumping Theorem(泵定理) 需要讨论的长 String;无规则的文法同样单独处理。
因此,若 ,任何 Yield 的 Parse Tree 都必须高于 。 String足够长,就会迫使Parse Tree的某条路径足够长。
A Pumping Theorem
设 为 CFG, Nonterminal 个数为
Pumping Theorem :任何满足
的 String 都存在分解
使得
其中 至少有一个非空 ,允许另一个为空;两部分必须使用 相同的重复次数 。 删除两部分, 得到原串, 同时各增加一份。

展开Pumping Theorem证明
第一步:选择一棵最小Parse Tree。 在所有根为 、 Yield 为 的 Parse Tree 中,选择 节点总数最少 的一棵 。
由 和前面的引理可知, 的高度大于 ,所以某条根到叶子的路径至少有 条边、 个节点。除最后的叶子外,路径上的节点均为 Nonterminal;由于文法只有 种 Nonterminal,其中至少两个节点带有相同标记 。
第二步:沿两个 划分Yield。 上方 的子树包住下方 的子树,于是可以写成
其中 ,且 。具体地, 是下方 子树的 Yield; 分别来自上方子树中位于下方子树左、右两侧的部分。
第三步:重复中间树段。 规则 可重复使用任意次,然后通过 结束:
因此所有泵出的 String 都属于 。
第四步:证明至少一侧非空。 若 ,可直接用下方 子树替换上方 子树。根标记相同、最终 Yield 仍为 ,但节点总数严格减少,与 的最小性矛盾。故 。
Using the Pumping Theorem
Pumping Theorem 给出 CFL 必须满足的性质。 用它证明一个语言不属于 CFL 时,要排除所有可能的合法分解。
量词顺序为:给定一个足够长的 , 存在 某种分解,使得 所有 泵次数都有效。反证时不能自己选一个方便破坏的分解就结束。
通常按以下步骤组织证明:
- 假设 是 CFL,存在生成它的文法 ,记 。
- 选择一个结构清楚的 ,使 。
- 考虑任意分解 ,只使用定理已经保证的 等条件。
- 对所有分解分类;每一种都找到某个 ,使 。
- 与 Pumping Theorem 矛盾,推出 不是 CFL。
找到一种可以泵的分解,或者没有成功构造反例,都不足以证明语言属于 CFL。要证明属于 CFL,通常应给出文法、 PDA,或使用已证明的 Closure Property。
Example
- Three Equal Blocks
证明
不是 CFL。
展开完整反证:覆盖所有分解
假设 ,取整数 ,令
由 Pumping Theorem,存在分解 ,满足 ,且对每个 都有 。下面无论分解如何,都取 。
情况一: 合起来出现了 三种符号。 两个 Substring 要覆盖三种符号,至少有一个 Substring 包含两种或更多符号。由于它是 的连续 Substring,内部符号顺序只能从 到 再到 ;但将这个混合 Substring 重复两次时,第一份末尾的较后符号会出现在第二份开头的较前符号之前。例如,重复 ,其中 ,会在中间形成 。
因此 ,更不属于 。
情况二: 合起来只出现一种或两种符号。 至少一种符号完全不在 中,其数量在泵之后仍为 ;由于 ,至少另一种符号的数量严格增加。因此泵出的 String 不再满足三种符号数量相等,仍不属于 。
两种情况覆盖所有分解,均与 Pumping Theorem 矛盾,所以 不是 CFL。
- Prime-Length Strings
证明
不是 CFL。
展开证明:明确选择泵次数
假设 。取大于泵阈值 的素数 ,令 。任意满足 Pumping Theorem 条件的分解 都有
泵 次后 String 的长度为 。取
则
由于 、,这个长度是合数。因此泵出的 String 不属于 ,与 Pumping Theorem 矛盾。
这个取法也覆盖 的情况,无需额外分类。
- Equal Counts in Arbitrary Order
证明
不是 CFL。
展开证明:用Regular Language筛出已知反例
假设 是 CFL。由于 是 Regular Language,由“ CFL 与 Regular Language 的交集封闭”可知
也应为 CFL。然而
右边已证明不属于 CFL,矛盾。
交上 Regular Language 的作用,是把任意排列限制成三段有序块,使原语言中的数量条件变成已知的三段等长问题。
Nonclosure under Intersection and Complementation
CFL对一般交集与补集都不封闭。
展开交集不封闭的反例
令
两者分别只要求一对相邻符号数量相等,可由 CFL 的连接 Closure Property 证明均为 CFL。
但同时满足两者的 String 必须有三段等长:
该语言不属于 CFL,所以 CFL 对交集不封闭。
展开补集不封闭的证明
固定共同 Alphabet ,所有补集都相对于 。
若 CFL 对补集封闭,那么对于任意两个 CFL ,结合并集 Closure Property 与德摩根律,
也应属于 CFL。但前面的反例已经证明交集不封闭,矛盾。因此补集同样不封闭。
这里的“不封闭”表示 存在反例 ;某两个 CFL 的交集或某一个 CFL 的补集仍可能恰好是 CFL。
Choosing a Proof Method
- 证明语言属于 CFL :优先寻找递归生成结构写 CFG,或寻找能由一个栈保存的信息写 PDA;条件可拆分时,再使用并、连接、 Kleene Star 及“与 Regular Language 取交”。
- 证明语言不属于 CFL :可直接使用 Pumping Theorem,或先与一个 Regular Language 取交,转化为已知非 CFL。
- 使用Pumping Theorem时 :保证选择的原串属于目标语言,排除所有合法分解,并明确指出泵之后破坏的是字符顺序、数量关系还是长度性质。
- 使用Closure Property时 :先确认每个操作数的语言类别;两个 CFL 的交集没有一般保证。