形式语言与自动机课件——Chomsky范式和Greibach范式.ppt

fall 2001 §4.3 Chomsky范式和Greibach范式 Chomsky范式定义： 2型文法G＝（N，T，P，S），若生成式形式都是A→BC和A→a，A、B、C∈N，a∈T，则G是Chomsky范式。若ε∈L（G），则S→ε是P的一个生成式，但S不能在任何其它生成式的右边。 每个上下文无关文法都具有等效的CNF（定理4.3.1） CNF 的构成步骤 1. 用算法1、2、3、4消除ε生成式、无用符号、单生成式 2. 对生成式A→D1D2…Dn n≥2 若Di∈T，则引入新生成式Bi→Di，Bi是新非终结符 若Di∈N，则令Bi＝Di，从而将原生成式变化为 A→B1B2…Bn n≥2 当n2 时，再将其变为 A→B1C1，C1→B2C2，C2→B3C3，…，Cn－1→Bn－1Bn Ci是新引入的非终结符。 定理证明――自学 Greibach范式 Greibach范式 (GNF)定义： 2型文法G＝（N，T，P，S），若生成式的形式都是A→aβ，A∈N，a∈T，β∈N*，且G不含ε生成式，则称G为Greibach范式，记为GNF。 任何2型文法都具有等效的GNF（定理4.3.2） GNF 的构成步骤 1. 将2型文法变换为CNF。（A→a，A→BC形式） 2.将非终结符排序,再进行代换。 对形如Ai→Ajβ（ji）的生成式进行代换，直至使 Ai→Alβ（li）。 3.消左递归。 对最高的An→Anγ进行变换，使An生成式变为终结符开头。 4.回代。 将An生成式回代入An－1生成式，使其右部首符为终结符， 将An－1生成式回代入An－2生成式，使其右部首符为终结符 … 5. 最后将消直接左递归时引入的A1’、 A2’、…An’生成式右部进行代换。使其首符变为终结符。 §4.4 下推自动机（PDA） 主要内容 PDA的基本概念。 PDA的构造举例。 用终态接受语言和用空栈接受语言的等价性。 PDA是上下文无关语言的接收器。 重点 PDA的基本定义及其构造 PDA与上下文无关语言等价 难点 根据PDA构造上下文无关文法。 下推自动机的结构 扩充办法：引入一个下推栈 ①? 足够简单 ②? 可解决许多有意义的问题， 如识别有效的程序 下推自动机PDA（Push Down Automaton） 由一条输入带,一个有限状态控制器和一个下推栈组成 PDA的动作 在有限状态控制器的控制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动作。有时，不需要考虑输入符号（空转移）。 栈：后进先出表 对栈的操作（压入、弹出）均在栈顶进行。 下推自动机的定义 NPDA的形式定义： 七元组 M＝（Q，T，Γ，δ，q0，z0，F） 其中：Q：有限控制器的状态集合 T：有限输入字母表 Γ：有限下推栈字母表 δ： Q ×（T∪ε）× Γ → Q×Γ* 当前状态 当前输入 当前栈顶符号 有限子集 q0：初始状态，q0∈Q z0：下推栈的起始符号，z0∈Γ F： 终态集合，F ? Q 下推自动机的转换函数 转换函数δ(q，a，Z)＝{ (p，α) } q、p∈Q，a∈T，Z∈Γ，α∈Γ* 表示在状态q，输入字符a，且栈顶符Z时，转入状态p，栈顶符Z由α代替，同时读头右移一格。 约定： ????? α的最左符号放在栈顶。 ????? α＝ε表示下推栈的顶符被弹出 如 δ（q，a，Z）＝{ (p，ε) } ????? δ（q，ε，Z）＝{ (p，α) } 称为ε转换。 即不考虑当前输入字符，读头不移动，但控制器状态可以改变且栈顶符可以调整。 下推自动机的格局 格局：用于描述PDA的瞬时工作状况 PDA格局 (q, ω, α) 其中 ω∈Γ*，α∈Γ* q — 当前状态 ω— 待输入串 (ω＝ε时，表示输入字符已读完) α— 下推栈中的内容 (α＝ε时表示栈已弹空) δ(q，a，Z ) ＝{ (p，r) }用格局可表示为 (q, aω,Zα) ├ (p, ω,rα) 对PDA而言， 初始格局为（q0，ω，z0） 终止格局为（q，ε，α） q∈F，α∈Γ* 下推自动机接受的语言 两种接受方式 终态接受： L(M)={ ω∣(q0 ，ω，z0)├* (q，ε，α) ，