资源描述：
《Formal Languages and Automata Theory--第六章--课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、FormalLanguagesandAutomataTheory6 上下文无关文法与下推自动机语言｛aibi
2、i>0}是不能被有穷自动机所接受的。要接受这个语言，机器需要记录某一a的有限次数，有限状态机的约束不允许自动机“记住”输入串中a的个数。因此我们需要定义一个新型自动机，它由一个下推栈加上一个有限自动机组成，称为下推自动机（PDA）。6.1下推自动机(1)定义：下推自动机（pushdownautomation)是一个七元组（Q，，，，q0，z,F）,其中Q是一有穷状态集，为一有穷字母表，为一有一有穷下推集，q0为开始状态，z为下推字符,
3、FQ是终止状态集，是从Q（｛｝）（P｛｝）到Q（P｛｝）的转移函数。一个PDA有两个字符集：输入字符串它由输入字符串组成，有一个栈字符集P，它的元素存在栈中。A表示以A为栈顶元素的栈，空栈被表示为。PDA的计算开始于状态q0，输入在输入带上且栈为空。PDA的当前状态、输入符号和栈顶符号决定自动机的转换。转换函数列出所有给定状态、符号和栈顶元素的所有可能的转换。（qi，a,A)={[qj,B],[qk,C]}表示当前状态为qi，输入符号为a，栈顶符号为A时的两种可能的转换。6.1下推自动机(2)[qj,B]（qi，a
4、，A)newstatecurrentstacktopnewstacktopcurrentinputsymbolcurrentstate表示i)状态由qi换为qiii)处理字符a,输入带向前移动iii）栈顶A退栈iv）B进栈。6.1下推自动机(3)一个下推自动也可由状态转换图表示，弧上的符号表示输入符号和栈操作。转换函[qj,B]（qi，a，A)表示如下：aA/Bqiqj符号/表示B代替A可以出现在输入字符和栈顶位置，分别三种转换函数。（1）[qi,]（qi，，A)（输入位置是）A/ A出栈qi6.1下推自动机(4)（2）[qi,A]
5、（qi，，)（输入位置是）/A（A压栈，不改变输入状态）qi（3）[qj,]（qi，a，)a/(等价于有限自动机，转换由状态和输入符号决定）qiqj一个PDA可表示为一个三元组[qi,,]，qi是机器状态，为未处理的输入串,为栈顶。[qi,,]├[qj,v,]表示[qj,v,]由[qi,,]经一步转换而得。6.1下推自动机(5)例1：构造一个PDA接受语言｛aibi
6、i>=0}M:Q=[q0,q1]a/AbA/bA/={a,b}={A}F={q0,q1}(q0,a,)={[q0,A]}(q0
7、,b,A)={[q1,]}(q1,b,A)={[q1,]}[q0,aabb,]├[q0,abb,A]├[q0,bb,AA]├[q0,b,A]├[q0,,]q0q16.1下推自动机(6)定义：设M＝（Q，，，，q0，F）为一PDA，字符串被PDA接受，如果[q0,,]├*[qi,,],qiF（终态的集合）例2：PDA M接受语言｛cR
8、{a,b}*}M:Q=[q0,q1]={a,b,c}={A,B}F={q1}(q0,a,)={[q0,A]}b/BbB/(q0,b,)={[q0,B]}a/AaA/
9、(q0,c,)={[q1,]}q0c/q1(q1,a,A)={[q1,]}(q1,b,B)={[q1,]}6.1下推自动机(7)例3：PDA M接受语言｛ai
10、i>=0aibi
11、i>=0}a/AbA/q0bA/q1/q2A/6.1下推自动机(8)例4:含有相同个数的0和1的所有的0,1串。思想：用栈记录0和1个数的差。当1比0多时，栈中全部为A，且A的个数等于1比0多的个数；当0比1多时，栈中全部为B，且B的个数等于0比1多的个数。M=({q,p},{0,1},{A,B,Z},,q,Z,{p})，其中(q,,Z
12、)={(p,)}接受，读完字符串后栈中没有A或B，转到终止状态(q,1,Z)={(q,A)}在前面0和1个数相等的时候又读到1，则在栈中压入1个A(q,0,Z)={(q,B)}在前面0和1个数相等的时候又读到0，则在栈中压入1个B(q,1,A)={(q,AA)}在前面1比0个数多的时候又读到1，则在栈中再压入1个A(q,0,A)={(q,)}在前面1比0个数多的时候又读到0，则从栈中弹出1个A(q,1,B)={(q,)}在前面0比1个数多的时候又读到1，则从栈中弹出1个B(q,0,B)={(q,BB)}在前面0比1个数多的时候又读到
13、0，则在栈中压入1个B根据文法构造G：S1S0S
14、0S1S
15、构造语言的NPDA6.2下推自
