形式语言学ch7.pdf

第7章下推自动机 PDA描述CFL，所以它应该与CFG等价。 PDA应该包含FA 的各个元素，或者包含那些可以取代 FA 的各个元素的功能的元素。 PDA按照最左派生的派生顺序，处理处于当前句型最左 边的变量，因此，需要采用栈作为其存储机构。 按照FA 的“习惯”，PDA用终态接受语言。 模拟GNF 的派生PDA用空栈接受语言。 第7章下推自动机 主要内容 PDA 的基本概念。 PDA 的构造举例。 用终态接受语言和用空栈接受语言的等价性。 PDA是CFL 的接受器。 重点 PDA 的基本定义及其构造，PDA是CFL的等价描述。 难点 根据PDA构造CFG。 1 文法的乔姆斯基体系 G是2型文法 如果对于∀α→β∈P ，α→β均具有形式 A→w A→wB 其中A ，B ∈V ，w ∈T+ 。则称G 为3型文法(type 3 grammar)， 也 可 称 为 正则文法 ( regular grammar ,RG)或者正规文法。L(G) 叫做3型语言 (type 3 language)，也可称为正则语言或者正规 语言(regular language ,RL)。 有穷状态自动机的物理模型 有穷控制器处于有穷状态中的第一个，带头注视到 一个字母ai 时，可以发生状态的转变，且带头右移 一格。 带头 有穷控制器 2 有穷状态自动机 有穷状态自动机(finite automaton,FA) M=(Q ，∑，δ，q ，F) 0 Q—— 状态的非空有穷集合。∀q ∈Q，q 称为M 的一个状态 (state) 。 ∑——输入字母表(Input alphabet)。输入字符串都是∑上的 字符串。 q0——q0 ∈Q，是M 的开始状态(initial state)，也可叫做初始状 态或者启动状态。 有穷状态自动机 δ——状态转移函数(transition function)，有时候又叫做 状态转换函数或者移动函数。δ：Q ×∑→Q，对∀(q， a) ∈Q ×∑，δ(q，a)=p表示：M在状态q读入字符a，将 状态变成p ，并将读头向右移动一个带方格而指向输入字 符串的下一个字符。 F——F⊆Q，是M 的终止状态(final state)集合。∀q ∈F ，q 称为M 的终止状态，又称为接受状态(accept state)。 3 格雷巴赫范式 格雷巴赫范式文法(Greibach normal form ,GNF)简称为 Greibach文法，或Greibach范式。 A→a α * 其中，A ∈V ，a ∈T，α∈V 。 在GNF 中，有如下两种形式的产生式 A→a A→aA A …A (m ≥1) 1 2 m 7.1 下推自动机基本定义 PDA的物理模型 输入带：存放输入符号串 有穷状态控制器 存放文法符号 4 7.1 基本定义 PDA应该含有三个基本结构 存放输入