形式语言与自动机7教学讲解教案.pdf

《形式语言与自动机7教学讲解教案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、FL&A第七讲下推自动机FL&A下推自动机下推自动机的基本概念下推自动机的语言：两种定义两种定义的等价性FL&A下推自动机的基本概念下推自动机（pushdownautomaton）是带有一个堆栈的有限状态自动机.FiniteInputstateAccept/rejectcontrolStackFL&A下推自动机的基本概念形式定义一个下推自动机PDA是一个七元组P=(Q,,,,q,Z,F).00有限状态集有限输入符号集有限堆栈符号集转移函数q0Q一个开始状态Z0一个开始堆栈符号FQ终态集合:Q()

2、2Q*FL&A下推自动机的基本概念举例所接受语言为L=0n1nn1的一个PDAP=({q,q,q},{0,1},{X,Z},,q,Z,{q})0120002其中，转移函数定义如下(q,0,Z)={(q,XZ)},(q,0,X)={(q,XX)},000000(q,1,X)={(q,)},(q,1,X)={(q,)}0111(q,,Z)={(q,Z)}1020对其余的参数值，(q,a,Y)=0,Z/XZ000,X/XX1,X/εStartq0q1q21,X/εε,/Z0Z0FL&A下推自动机的基本概念举例上述PDA如何

3、接受输入字符串？例如，00001111.X00001111XXXZ当前状态:q0q0q0q0q00stack0,Z/XZ000,X/XX1,X/εStartq0q1q21,X/εε,/Z0Z0FL&A下推自动机的基本概念举例上述PDA如何接受输入字符串？例如，00001111.00001111XXXZ当前状态:q10stack0,Z/XZ000,X/XX1,X/εStartq0q1q21,X/εε,/Z0Z0FL&A下推自动机的基本概念举例上述PDA如何接受输入字符串？例如，00001111.00001111XXZ当前状态:q10stack0,Z/X

4、Z000,X/XX1,X/εStartq0q1q21,X/εε,/Z0Z0FL&A下推自动机的基本概念举例上述PDA如何接受输入字符串？例如，00001111.00001111XZ当前状态:q10stack0,Z/XZ000,X/XX1,X/εStartq0q1q21,X/εε,/Z0Z0FL&A下推自动机的基本概念举例上述PDA如何接受输入字符串？例如，00001111.00001111Z当前状态:q10stack0,Z/XZ000,X/XX1,X/εStartq0q1q21,X/εε,/Z0Z0FL&A下推自动机的基本概念举例上述PDA如何接受

5、输入字符串？例如，00001111.00001111Z当前状态:q20stack0,Z/XZ000,X/XX1,X/εStartq0q1q21,X/εε,/Z0Z0FL&A下推自动机的语言：两种定义用ID（instantaneousdescriptions）表达当前格局PDA的当前格局用三元组（q,w,）表示，称为ID，其中q为当前状态，w为剩余的输入串，为当前栈中的内容.设PDAP=(Q,,,,q,Z,F)，定义ID推导关00系├（在不至于混淆时用├表示）为P（q,aw,X）├（p,w,）iff(p,)(q,a,X)，其中p

6、,qQ，a，w*，X，,*.上述ID推导关系的自反传递闭包├*（或├*）定义为P基础对任意IDI,I├*I.归纳对任意IDI,J,K,如果I├K,K├*J,则I├*J.FL&A下推自动机的语言：两种定义结论设PDAP=(Q,,,,q,Z,F)，如果00（q,x,）├*（p,y,），则对任何w*和*，（q,xw,）├*（p,yw,）.证明思路：归纳于（q,x,）├*（p,y,）的步数.举例下图PDA接受输入串000111的ID推导过程.（q0,000111,Z0）├*（q0,111,XXX

7、Z0）├*（q1,,Z0）├*（q2,,Z0）0,Z/XZ000,X/XX1,X/εStartq0q1q21,X/εε,/Z0Z0FL&A下推自动机的语言：两种定义终态接受的定义方法设PDAP=(Q,,,,q,Z,F)，00定义L(P)={w(q0,w,Z0)├*（q,,）},其中qF,*.空栈接受的定义方法设PDAP=(Q,,,,q,Z)，00定义N(P)={w(q,w,Z)├*（q,,）},其中qQ.00举例所接受语言为N(P)=0n1nn1的一个PDAP=({q,q},{0,1},{X,Z},,

8、q,Z)01000其中，转移函数定义如下(q,0,Z)={(q,XZ)},(