[计算理论基础] 上下文无关文法

上下文无关文法的定义

定义3.1：上下文无关文法

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

• $V$：有穷变元集
• $\Sigma$：有穷终结符集
• $R$：有穷规则集
• $S$：起始变元

定义：

• 一步生成：$uAv\Rightarrow uwv$，使用产生式 $A\to w$
• 任意步生成：$u \Rightarrow^* v = u \Rightarrow u_1 \Rightarrow ... \Rightarrow v$
• 文法的语言：$L(G)=\{w\in \Sigma^*|S\Rightarrow^* w\}$，称为上下文无关语言 ( CFL )。

设计 CFG：

• 合并：使用小的文法合成大的文法
• 正则：把 DFA 转换成 CFG
• 匹配：例如括号的匹配
• 递归：表达式文法

文法的歧义性

最左派生：每一步都替换最左边的变元
歧义地产生：有两个最左派生
歧义文法：文法歧义地产生某个串
固有歧义语言：只能用歧义文法产生，非确定下推自动机才能处理固有歧义语言

乔姆斯基范式 ( CNF )

CNF：只允许如下形式的规则

• $S\to \epsilon$
• $A\to BC$
• $A\to a$
  其中
• A，B，C 是任意变元
• B，C 不是初始变元
• a 是任一终结符
  产生的语法分析树最多有两个分叉。

---

定理3.6：任何 CFG 都有等价的 CNF。
思路：

1. 添加新的初始变元
   $S_0\to S$
2. 处理 $A\to \epsilon$ ( 只能由初始变元产生 )
   删除所有 $\epsilon$ 规则如果 $A$ 不是初始变元
3. 处理 $A\to B$ ( 右边不能只有一个变元 )
   若有 $B\to u$ 添加 $A\to u$，除非其已经被删除
4. 处理 $A\to u_1u_2...u_k$ ( 右边不能多于两个符号 )
   将其变为：$A\to u_1A_1, A_1\to u_2A_2...$
5. 处理 $A\to a_ia_j,A\to a_iB,A\to Ba_i$ ( 不是两个变元 )
   对于每个终结符 $a_i$ 引入 $U_i\to a_i$

下推自动机

一般说 PDA 指的是非确定性 PDA，可以描述有固有歧义的语言。

定义3.8：PDA $M = (Q,\Sigma, \Gamma, \delta, q_0, F)$

• $Q$：有穷状态集
• $\Sigma$：输入字母表
• $\Gamma$：栈字母表
• $\delta$：$Q\times \Sigma_\epsilon \times \Gamma_\epsilon \to P(Q\times \Gamma_\epsilon)$
• $q_0\in Q$：初始状态
• $F\subseteq Q$：终结状态

PDA 与 CFG 等价性

定理3.12：一个语言是 CFL 当且仅当存在 PDA 识别这个语言

---

引理3.13：如果一个语言是 CFL，则存在 PDA 识别这个语言
思路：

• PDA 在堆栈中模拟派生
• 让栈顶终结符与输入匹配
• 栈顶是变元，就模拟派生
• 栈顶是终结符就进行匹配
  证明：略

---

引理3.15：如果一个语言被 PDA 识别，则这个语言是 CFL
思路：用文法派生 PDA 接受的串

上下文无关语言的泵引理

定理3.19：设 A 是上下文无关语言，则存在常数 p 使得若 $s\in A, |s|\geq p$，则$s=uvxyz$. 同时满足下面条件：

1. 任个 $i\geq 0, uv^ixy^iz\in A$
2. $|vy|>0$
3. $|vxy|\leq p$

思路：由于变元的数量有限，串足够长时，语法分析树从树根到树叶中会有重复变元，将重复的变元进行替换产生新的串并对其进行判定确定是否为语言中的串从而确定语言是否为上下文无关语言。

---

定理：

1. 正则语言都是上下文无关的
2. CFL 对并、连接星号运算封闭
3. CFL 对交、补不封闭

---

• ← Previous Post
• Next Post →