本文主要是介绍【计算理论】【《计算理论导引（原书第3版）》笔记】第二章：上下文无关文法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- @[toc]
- 2.1|上下文无关文法概述
- 上下文无关文法的形式化定义
- 乔姆斯基范式
- 定理
- 证明
文章目录
- @[toc]
- 2.1|上下文无关文法概述
- 上下文无关文法的形式化定义
- 乔姆斯基范式
- 定理
- 证明
个人主页：丷从心
系列专栏：计算理论
2.1|上下文无关文法概述
上下文无关文法的形式化定义
- 上下文无关文法是一个 4 4 4元组 ( V , Σ , R , S ) (V , \Sigma , R , S) (V,Σ,R,S)，且
- V V V是一个有穷集合，称为变元集
- Σ \Sigma Σ是一个与 V V V不相交的有穷集合，称为终结符集
- R R R是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成
- S ∈ V S \in V S∈V是起始变元
乔姆斯基范式
- 称一个上下文无关文法为乔姆斯基范式，如果它的每一个规则具有如下形式
A → B C A → a A \rightarrow BC \\ A \rightarrow a A→BCA→a
- 其中， a a a是任意的终结符， A A A、 B B B和 C C C是任意的变元，且 B B B和 C C C不能是起始变元，此外允许规则 S → ε S \rightarrow \varepsilon S→ε，其中 S S S是起始变元
定理
- 任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生
证明
- 首先，添加一个新的起始变元 S 0 S_{0} S0和规则 S 0 → S S_{0} \rightarrow S S0→S，其中 S S S是原来的起始变元
- 这样可以保证起始变元不会出现在规则的右边
- 第二阶段，考虑所有的 ε \varepsilon ε规则
- 删除 ε \varepsilon ε规则 A → ε A \rightarrow \varepsilon A→ε，这里 A A A不是起始变元，然后对在规则右边出现的每一个 A A A，删除这个 A A A后得到一条新的规则
- 第三阶段，处理所有的单一规则
- 删除单一规则 A → B A \rightarrow B A→B，然后只要有一条规则 B → u B \rightarrow u B→u，就要添加规则 A → u A \rightarrow u A→u，除非 A → u A \rightarrow u A→u是已在前面被删除的单一规则
- 最后，把所有留下的规则转换成适当的形式
- 把每一条规则 A → u 1 u 2 ⋯ u k A \rightarrow u_{1} u_{2} \cdots u_{k} A→u1u2⋯uk替换成规则 A → u 1 A 1 A \rightarrow u_{1} A_{1} A→u1A1， A 1 → u 2 A 2 A_{1} \rightarrow u_{2} A_{2} A1→u2A2， ⋯ \cdots ⋯， A k − 2 → u k − 1 u k A_{k - 2} \rightarrow u_{k - 1} u_{k} Ak−2→uk−1uk，其中 k ≥ 3 k \geq 3 k≥3，每一个 u i u_{i} ui是一个变元或终结符， A i A_{i} Ai是新的变元，用新变元 U i U_{i} Ui替换终结符 u i u_{i} ui，并增加规则 U i → u i U_{i} \rightarrow u_{i} Ui→ui
这篇关于【计算理论】【《计算理论导引（原书第3版）》笔记】第二章：上下文无关文法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
