形式语言学_ch7_下推自动机

《形式语言学_ch7_下推自动机》由会员分享，可在线阅读，更多相关《形式语言学_ch7_下推自动机（51页珍藏版）》请在金锄头文库上搜索。

1、形式语言学形式语言学 Introduction to Formal Languages 第7章下推自动机 PDA描述CFL，所以它应该与CFG等价。 PDA应该包含FA的各个元素，或者包含那些可以取代FA的各个元素的功能的元素。 PDA按照最左派生的派生顺序，处理处于当前句型最左边的变量，因此，需要采用栈作为其存储机构。 按照FA的“习惯”，PDA用终态接受语言。 模拟GNF的派生PDA用空栈接受语言。 第7章下推自动机 主要内容 PDA的基本概念。 PDA的构造举例。 用终态接受语言和用空栈接受语言的等价性。 PDA是CFL的接受器。 重点 PDA的基本定义及其构造，PDA是CFL的等价描述

2、。 难点 根据PDA构造CFG。 文法的乔姆斯基体系 G是2型文法 如果对于 P， 均具有形式 Aw AwB 其中A，BV，wT+。则称G为3型文法(type 3 grammar)， 也 可 称 为 正 则 文 法 ( regular grammar ,RG)或者正规文法。L(G)叫做3型语言(type 3 language)，也可称为正则语言或者正规语言(regular language ,RL)。 有穷状态自动机的物理模型 有穷控制器处于有穷状态中的第一个，带头注视到 一个字母ai 时，可以发生状态的转变，且带头右移 一格。 有穷控制器 带头 有穷状态自动机 有穷状态自动机(finite

3、automaton,FA) M=(Q，q0，F) Q状态的非空有穷集合。qQ，q称为M的一个状态(state)。 输入字母表(Input alphabet)。输入字符串都是上的字符串。 q0q0Q，是M的开始状态(initial state)，也可叫做初始状态或者启动状态。 有穷状态自动机 状态转移函数(transition function)，有时候又叫做状态转换函数或者移动函数。：QQ，对(q，a)Q，(q，a)=p表示：M在状态q读入字符a，将状态变成p，并将读头向右移动一个带方格而指向输入字符串的下一个字符。 FFQ，是M的终止状态(final state)集合。qF，q称为M的终止状

4、态，又称为接受状态(accept state)。 格雷巴赫范式 格雷巴赫范式文法(Greibach normal form ,GNF)简称为Greibach文法，或Greibach范式。 Aa 其中，AV，aT，V* 。 在GNF中，有如下两种形式的产生式 Aa AaA1A2Am (m1) 7.1 下推自动机基本定义 PDA的物理模型的物理模型 输入带：存放输入符号串 有穷状态控制器 存放文法符号 7.1 基本定义 PDA应该含有三个基本结构 存放输入符号串的输入带。 存放文法符号的栈。 有穷状态控制器。 PDA的动作 在有穷状态控制器的控制下根据它的当前状态、栈顶 符号、以及输入符号作出相应

5、的动作，在有的时候， 不需要考虑输入符号。 7.1 基本定义 下推自动机(pushdown automaton，PDA) M= (Q，q0，Z0，F) Q状态的非空有穷集合。qQ，q称为M的一个状态(state)； 输入字母表(input alphabet)。要求M的输入字符串都是上的字符串； 栈符号表(stack alphabet)。A，叫做一个栈符号； 7.1 基本定义 Z0Z0叫做开始符号(start symbol)，是M启动时候栈内唯一的一个符号。所以，习惯地称其为栈底符号； q0q0Q，是M的开始状态(initial state)，也可叫做初始状态或者启动状态； FFQ，是M的终止状

6、态(final state)集合，简称为终态集。qF，q称为M的终止状态，也可称为接受状态(accept state)，简称为终态。 7.1 基本定义 状态转移函数(transition function)，有时候又叫做状态转换函数或者移动函数。 ：Q() *2Q(q，a，Z)=(p1，1)，(p2，2)，(pm，m) 表示M在状态q，栈顶符号为Z时，读入字符a，对于i=1，2，m，可以选择地将状态变成pi，并将栈顶符号Z弹出，将i中的符号从右到左依次压入栈，然后将读头向右移动一个带方格而指向输入字符串的下一个字符。 7.1 基本定义 (q，Z)=(p1，1)，(p2，2)，(pm，m) 表示

7、M进行一次-移动(空移动)，即M在状态q，栈顶符号为Z时，无论输入符号是什么，对于i=1，2，m，可以选择地将状态变成pi，并将栈顶符号Z弹出，将i中的符号从右到左依次压入栈，读头不移动。 7.1 基本定义 符号使用约定 英文字母表较为前面的小写字母，如a，b，c，表示输入符号； 英文字母表较为后面的小写字母，如x，y，z，表示输入字符串； 英文字母表的大写字母，表示栈符号； 希腊字母，表示栈符号串。 7.1 基本定义 即时描述(instantaneous description，ID) (q，w，)(Q，*，*)称为M的一个即时描述。它表示M处于状态q，w是当前还未处理的输入字符串，而且M正

8、注视着w的首字符，栈中的符号串为，的最左符号为栈顶符号，最右符号为栈底的符号，较左的符号在栈的较上面，较右的符号在栈的较下面。 7.1 基本定义 如果(p，)(q，a，Z)，a，则 (q，aw，Z)M(p，w，) 表示M做一次非空移动，从ID(q，aw，Z)变成ID(p，w，)。 如果(p，)(q，Z)，则 (q，w，Z)M(p，w，) 表示M做一次空移动，从ID(q，aw，Z)变成ID(p，w， ) 。 7.1 基本定义 Mn是M 的n次幂 (q1，w1，1)Mn(qn，wn，n) M*是M 的克林闭包 (q，w，)M*(p，x，) M+是M 的正闭包 (q，w，)M+(p，x，) 7.1

9、基本定义 M接受的语言 M用终态接受的语言 L(M)=w | (q0，w，Z0)*(p，)且 pF M用空栈接受的语言 N(M) =w | (q0，w，Z0)*(p，) 7.1 基本定义 例 7-1 考虑接受语言L=w2wT | w0,1*的PDA的设计。 解法1： 先设计产生L的CFG G1： G1：S2|0S0|1S1 再将此文法转化成GNF： G2：S2|0SA|1SB A0 B1 7.1 基本定义 句子0102010的最左派生和我们希望相应的PDA M的动作。 派生 M应该完成的动作 S0SA 从q0启动，读入0，将S弹出栈，将SA压入栈，状态不变 01SBA 在状态q0，读入1，将S

10、弹出栈，将SB压入栈，状态不变 010SABA 在状态q0，读入0，将S弹出栈，将SA压入栈，状态不变 0102ABA 在状态q0，读入2，将S弹出栈，将压入栈，状态不变 01020BA 在状态q0，读入0，将A弹出栈，将压入栈，状态不变 010201A 在状态q0，读入1，将B弹出栈，将压入栈，状态不变 0102010 在状态q0，读入0，将A弹出栈，将压入栈，状态不变 7.1 基本定义 M1=(q0，0，1，2，S，A，B，1，q0，S，)。其中： 1(q0，0，S)=(q0，SA) 1(q0，1，S)=(q0，SB) 1(q0，2，S)=(q0，) 1(q0，0，A)=(q0，) 1(q

11、0，1，B)=(q0，) 此时有：N(M1)=L。 7.1 基本定义 M2=(q0,q1,0,1,2,S,A,B,Z0,2,q0,Z0,q1) 2(q0，0，Z0)=(q0，SAZ0) 2(q0，1，Z0)=(q0，SBZ0) 2(q0，2，Z0)=(q1，) 2(q0，0，S)=(q0，SA) 2(q0，1，S)=(q0，SB) 2(q0，2，S)=(q0，) 2(q0，0，A)=(q0，) 2(q0，1，B)=(q0，) 2(q0，Z0)=(q1，) 此时有：N(M2)=L(M2)=L。 增加终止状态q1和栈底符号 Z0只是为了实现终态接受。 7.1 基本定义 解法2： 注意到L=w2wT

12、|w0,1*，所以PDA M3 的工作可以分成两大阶段。 在读到字符2之前，为“记载”阶段：每读到一个符号就在栈中做一次相应的记载。 在读到2以后，再读到字符时，就应该进入“匹配”阶段：由于栈的“先进后出”特性正好与wT相对应，所以，用栈顶符号逐一地与输入字符匹配。 7.1 基本定义 M3=(q0，q1，q2，qf，qt，0，1，2， A，B， Z0，3，q0，Z0，qf) q0为开始状态 q1为记录状态 q2为匹配状态 qf为终止状态 qt陷阱状态 7.1 基本定义 3(q0，0，Z0)=(q1，AZ0) 3(q0，1，Z0)=(q1，BZ0) 3(q0，2，Z0)=(qf，) 3(q1，0

13、，A)=(q1，AA) 3(q1，1，A)=(q1，BA) 3(q1，0，B)=(q1，AB) 3(q1，1，B)=(q1，BB) q0为开始状态 q1为记录状态 q2为匹配状态 qf为终止状态 qt陷阱状态 7.1 基本定义 3(q1，2，A)=(q2，A) 3(q1，2，B)=(q2，B) 3(q2，0，A)=(q2，) 3(q2，0，B)=(qt，) 3(q2，1，B)=(q2，) 3(q2，1，A)=(qt，) 3(q2，Z0)=(qf，) 此时有：N(M3)=L(M3)=L。 q0为开始状态 q1为记录状态 q2为匹配状态 qf为终止状态 qt陷阱状态 7.1 基本定义 不追求让PD

14、A同时用终止状态和空栈接受同样的语言，还可以删除状态qf。这样我们可以得到PDA M4 。 M4=(q0，q1，q2 ，0，1，2， A，B， Z0，4，q0，Z0，) 4(q0，0，Z0)=(q1，AZ0) 4(q0，1，Z0)=(q1，BZ0) 4(q0，2，Z0)=(q2，) q0为开始状态 q1为记录状态 q2为匹配状态 7.1 基本定义 4(q1，0，A)=(q1，AA) 4(q1，1，A)=(q1，BA) 4(q1，0，B)=(q1，AB) 4(q1，1，B)=(q1，BB) 4(q1，2，A)=(q2，A) 4(q1，2，B)=(q2，B) 4(q2，0，A)=(q2，) 4(q2，1，B)=(q2，) q0为开始状态 q1为记录状态 q2为匹配状态 7.1 基本定义 确定的(deterministic)PDA (q，a，Z)Q，|(q，a，Z)|+|(q，Z)|1 PDA在每一个状态q和一个栈顶符号下的动作都是惟一的。 关键 对于(q，Z)Q，M此时如果有非空移动，就不能有空移动。 每一种情况下的移动都是唯一的。 7.1 基本定义 例 7-2 构造接受L=wwT|w0,1*的PDA。 差异 (q0，0，A)=(q0，AA)，(q1，) 0是w中的0或者是wT的首字符0； (q0，1，B)=(q0，BB)， (q1，) 1是w中的1或者是