ch4.1

CFL

上下文无关语言（CFL）：
CFL = PDA = NFA + Stack () = NPDA

NPDA/PDA

NPDA/PDA（非确定性/确定性下推自动机） 由七元组定义：

• ：有限状态集合

• ：有限输入字母表

• ：有限栈字母表

• ：状态转移函数，形式为 （即：从当前状态、输入符号（或空字符𝜖）及栈顶符号，转换到一组可能的新状态，并修改栈内容）

• ：初始状态

• ：栈初始符号

• ：终止状态集合

不是正则语言不能被DFA接受，但可以被NPDA接受：例如

Instantaneous Description

描述接受的过程：

PDA 接受一个字符串的方式有两种等价的方法：终态接受 和 空栈接受。终态接受是指 PDA 读取完字符串后，最终进入一个特定的终止状态；空栈接受则是 PDA 读取完字符串后，栈变为空，无需特定的终止状态。这两种方式虽然不同，但它们可以等价转换，因此都能正确描述 PDA 所能识别的语言。

练习

见ch4-1的PDF

PDA 与 CFG 的等价性

给定任意上下文无关文法（CFG），，我们可以构造一个等价的下推自动机（PDA），该自动机通过空栈接受字符串，其形式为：
对于任意非终结符 有：

对于任意终结符 ，有：

不会考察等价证明，但会考构造过程，如下面例题：

给出一个CFG：，构造等价的 PDA

给定任意下推自动机（PDA），其形式为：，我们可以构造一个等价的上下文无关文法（CFG），其形式为：
其中，非终结符集合 定义为：
（注： 表示从 到 状态，出栈 ）

利用上述规则：

CFL性质

判断是上下文无关语言，可通过构造上下文无关文法证明，也可以通过下面的一些性质证明。

闭包性质

给定两个CFL： 和 ，以下仍为CFL（图片为CFG构造）：








例如 :

给定两个CFL： 和 ，以下可能不是CFL：



反证法：利用上条性质


反证法：利用上条性质，，若一定是CFL，那么的补集一定是CFL，但的补集不一定是CFL，所以矛盾。

😎 给定一个CFL 和一个RL ， 是CFL。

证明习题

习题一
习题二

无限语言问题

给定一个上下文无关文法（CFG），判断该上下文无关语言（CFL）是否是无限的（无法枚举所有字符串）。

算法：

1. 移除无用的非终结符（useless non-terminals）。

2. 移除单元产生式（unit productions）和 ε 产生式（epsilon productions）。

3. 为剩余的非终结符创建依赖图（dependency graph）。

4. 检查该图是否存在环（cycle）。如果存在环，则该语言是无限的。

CFL 泵引理

为什么不是CFL

乔姆斯基范式 CNF

在上下文无关文法（CFG, Context-Free Grammar）中，我们可以将文法转换为多种标准形式，其中 乔姆斯基范式（Chomsky Normal Form, CNF） 是一种重要的标准形式。

一个 CFG 在 CNF 中，当且仅当它的所有产生式规则符合以下三种形式之一：

• ， ，

• 都是非终结符， 是终结符

• 不能是起始符号

• 只有当语言中包含空串 时，才允许起始符号 产生

CNF 的 parse tree 是二叉树形式

推导过程

1. 假设 是一个 不包含空串 的 CFL，且它的 CFG 已经转换为 CFN。

2. 假设（即非终结符的数量为 ），并定义 。

3. 由于文法在 CNF 中，每个非终结符只能产生两个非终结符（或者一个终结符），因此解析树必须是二叉树。叶子节点的数量等于字符串 的长度 （因为每个叶子节点代表一个终结符）。

4. 最长路径：从根（起始符号 ）到叶子节点的最长非终结符链，表示为：
   其中 （起始符号），是某个非终结符， 是一个终结符

5. 当字符串长度 时，最长路径的深度至少为 。由于非终结符的数量是有限的（只有 个），但最长路径 至少为 ，根据鸽笼原理，某些非终结符必须重复出现。

这个结论可以用于证明某些长字符串在 CFL 中一定可以拆分为可重复的部分

设 可表示为 ，其中 是由 推导生成的。对于任意 仍属于该 CFL。

Pumping Lemma for CFL

给定一个 上下文无关语言（CFL），存在一个常数 使得：对于任意满足 的字符串 ，满足以下条件：

1. （即 和 至少有一个非空）

3. 对于所有 ，

练习

---

• ← Previous Post
• Next Post →

---