【计算理论】【《计算理论导引（原书第3版）》笔记】第二章：上下文无关文法

2023-12-24 17:28:18

文章目录

因上努力

个人主页：丷从心

系列专栏：计算理论

果上随缘

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→u1?u2??uk?替换成规则 A → u 1 A 1 A \rightarrow u_{1} A_{1} A→u1?A1?， A 1 → u 2 A 2 A_{1} \rightarrow u_{2} A_{2} A1?→u2?A2?， ? \cdots ?， A k ? 2 → u k ? 1 u k A_{k - 2} \rightarrow u_{k - 1} u_{k} Ak?2?→uk?1?uk?，其中 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?

文章来源:https://blog.csdn.net/from__2023_11_28/article/details/135183810
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。