08正则表达式与正则语言new

《08正则表达式与正则语言new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、形式语言与自动机FormalLanguagesandAutomataTheory第七章下推自动机教师：胡春明、赵永望http://act.buaa.edu.cn/zhaoyw/course/flat_2012.html第七章下推自动机下推自动机（PDA）下推自动机的构造PDA两种接受语言方式的等价确定的下推自动机（DPDA）PDA与CFG等价2一、下推自动机（PDA）文法及机器：有穷状态自动机(FA)--------正则语言(RL)下推自动机(PDA)--------上下文无关语言(CFL)例：构

2、造与给定右正则文法等价的FA。下推自动机（PDA）文法及机器：有穷状态自动机(FA)--------正则语言(RL)下推自动机(PDA)--------上下文无关语言(CFL)PDA提出的思路：对于CFG，当它是GNF的时候，派生总是从左往右进行，而且右边变量后缀的长度是不定的，想用有穷状态来表示这些后缀不一定总是可能的。按照最左派生来分析句子的情况下，可以考虑用栈来保存Aa,AaAA…A12mPDA装置模型为何称下推自动机？三个基本结构PDA的动作存放输入符号串的输入带。在有穷状态控制器的控

3、制下根据它的当前状态、栈顶符号、以及输入符号作出相应的动存放文法符号的栈。作，在有的时候，不需要考虑输入符号。有穷状态控制器。PDA装置执行过程举例格雷巴赫范式：S2

4、0SA

5、1SBA0B1接受串：110020011S1SB11SBB110SABB1100SAABB11002AABB…110020011SASAAASBBBBBSBBBBBBB下推自动机（PDA）定义7-1：以终态方式接受语言的下推自动机M=(Q,,,,q,Z,F)和00以空栈方式接受语言的下推自动机M=(

6、Q,,,,q,Z,Φ)，其中00Q:状态的非空有穷集合；:输入字母表；:栈字母表；q:初始状态,（q∈Q）；00Z:起始栈底符号，（Z∈）；00F:终止状态集合，FQ;:状态转移函数，从Q({})到2Q*的映射。对于(q,a,Z)∈Q1、(q,a,Z)={(p,),(p,),…,(p,)}1122mm2、(q,ε,Z)={(p,),(p,),…,(p,)}1122mm下推自动机（PDA）其中，1、(q,a,Z)={(p,),(p,),

7、…,(p,)}:1122mm在状态q下，栈顶符号为Z，读入字符a时，M可选择将状态变为p（i=1,2,…,m,），并将栈顶符号Z弹出，将中的符号从ii右到左依此压入栈，然后，将读头向右移动一个字符，指向输入串的下一个字符。约定：1）的最左边符号被置于栈的最高位置；最右符号在最低位置上。i2）在一个动作中不允许同时选择状态p和符号串,ij。ij下推自动机（PDA）2、(q,ε,Z)={(p,),(p,),…,(p,)}1122mmM进行一次空移动：状态为q,栈顶符号为Z时，虽未对任

8、何输入字符进行扫描，也可选择将状态变为pi（i=1,2,…,m）,将栈顶符号Z弹出，将i中的符号从右到左依此压入栈，输入头不向前移动。约定：1）最左边符号被置于栈的最高位置；最右符号在最低位置上。i2）在一个动作中不允许同时选择状态p和符号串,ij。ij下推自动机（PDA）约定-按以下方式规定PDA中符号：英文字母较前面的小写字母，如a，b，c，…，表示输入符号；英文字母较后面的大写字母，如x，y，z，…，表示输入符号串;英文字母表的大写字母，如X,Y,Z,…,表示堆栈中符号;西腊字母，

9、，，…，表示堆栈中符号串。下推自动机（PDA）下推自动机多种转移动作举例：1、非空动作（有输入符号）：(q1,0,R)={(q1,BR)}-弹出栈顶符号R，新符号BR压入栈(q1,c,R)={(q2,R)}-改变控制器状态；(q1,0,B)={(q1,)}-弹栈。2、空动作（称为动作-没有输入符号）：(q2,,R)={(q2,)}-弹栈。下推自动机（PDA）PDA的两个基本概念：1、瞬时描述；2、PDA接受的句子方式下推自动机（PDA）定义7-2：设PDAM=(Q,,,,

10、q,Z,F)，00(q,w,)∈(Q,∑*,*)称为M的一个瞬时描述(instantaneousdescription,ID),q是控制器的当前状态w是当前尚未处理的输入字符串。M在状态q下，正注视输入字符串w的首字符，栈中符号串为，的最左符号为栈顶符号，最右符号为栈底符号。下推自动机（PDA）PDA的瞬时转移描述：(1)如果（p,）∈（q,a,Z）,表示当前M在状态q，栈顶为Z，读入a时(a∈∑)，选择进入状态p，用替换栈顶Z，读头指向w的首字符，记为：（q