第二章

·上下文无关法

··替换规则

​ A->0A1

\(G_1\){A->B

​ B->#

用局部变化规律和初始条件描述一个过程

  • 派生：获取一个字符串的替换序列成为派生

  • 由CFG生成的语言是CFL

  • 上下文无关法是一个四元组(V,Σ,R,S)

    变元集，终结符集，规则集，起始变元

··设计上下文无关文法
···四步
···歧义性
  • 定义一种以固定次序替换变元的派生类型。如果在每一步 都是替换剩下的最左边的变元，则称这个派生是最左派生。
  • 如果字符串 𝑤 在上下文无关文法 G 中有两个或两个以上 不同的最左派生，则称在 G 中歧义地产生字符串 𝑤 。如 果文法 G 歧义地产生某个字符串，则称 G 是歧义的。
··乔姆斯基范式

规则如下：

​ A->BC

​ A->a

*BC不能是起始变元，允许S->𝜀（S是起始变元）

~~任一 CFL 都可以用乔姆斯基范式的 CFG 产生。

~~=>(ppt_24)

  1. 加头(添加新的起始变元\(S_0\)保证起始变元不出现在右端)

  2. 去尾(删除除了\(S_0\)->𝜀的所有𝜀规则)

    *在上一步中补充可能出现的情况

  3. 删除单一规则(删掉A->B)

  4. 把所有的规则变成A->BC形式

    image-20231009103421030

·下推自动机

··概念PDA（形式化定义）

​ 下推自动机是一个 6 元组 𝑄, 𝛴, Γ, 𝛿, 𝑞0, 𝐹，这里 𝑄, 𝛴, Γ 和 𝐹 都是有穷集合，并且

  1. 𝑄 是状态集。

  2. 𝛴 是输入字母表。

  3. Γ 是栈字母表。

  4. 𝛿：𝑄 × 𝛴𝜀 × Γ𝜀 → 𝒫 （𝑄 × Γ𝜀） 是转移函数。

  5. 𝑞0 ∈ 𝑄 是起始状态。

  6. 𝐹 ⊆ 𝑄 是接受状态集。

  • 栈的作用在于可以保存无限信息容量，有推入和弹出操作

  • 例如， {\(0^𝑛\) \(1^𝑛\) |𝑛 ≥ 0}DFA没有存储功能不能记下n的数量，但PDA可以每读一个0，就将0下推，直到读入1，每读一个1，就将0弹出，0被清空刚好读完串，即可接受这个输入

  • 接受过程：

    𝑀 = 𝑄, 𝛴, Γ, 𝛿, 𝑞0, 𝐹 的计算如下：

    接收输入 𝑤 = 𝑤1𝑤2 ⋯ 𝑤𝑚， 𝑤𝑖 ∈ 𝛴𝜀

    存在状态序列 𝑟0，𝑟1，⋯，𝑟𝑚 ∈ 𝑄

    存在字符串序列 𝑠0，𝑠1，⋯ ，𝑠𝑚 ∈\(Γ^∗\) ，满足下列3个条件：

    （1）𝑟0 = 𝑞0 且 𝑠0 = 𝜀(初始状态)

    （2） (𝑟_𝑖+1, 𝑏)∈ 𝛿(𝑟_𝑖, 𝑤_𝑖+1, 𝑎)，因为PDA允许非确定性其中 𝑠𝑖 = 𝑎𝑡 ，𝑠𝑖+1 = 𝑏𝑡 ， 这里 𝑎，𝑏 ∈ Γ𝜀 和 𝑡 ∈\(Γ ^∗\) ，0 ≤ 𝑖 ≤ 𝑚 − 1， 注：𝑀 在每一步都完全按照当时的状态，栈顶符号和下一个输入符号发生状态转移。

    （3）𝑟_𝑚 ∈ 𝐹

    𝑠𝑖 是 𝑀 接受分支中的栈内容序列。

  • 相当于有栈的NFA

··{\(0^𝑛\) \(1^𝑛\) |𝑛 ≥ 0}例子

目标：输入读完，栈恰好为空

令 𝑀1 = {𝑄, 𝛴, Γ, 𝛿, 𝑞1, 𝐹 }，其中 𝑄 = 𝑞1, 𝑞2,𝑞3,𝑞4 𝛴 = {0, 1} Γ = {0, $} 𝐹 = {𝑞1, 𝑞2} 𝛿 由下表给出，表中空白项表示 ∅ 。

image-20231009112549324

未完待续