第三章3自动机.ppt

《第三章3自动机.ppt》由会员分享，可在线阅读，更多相关《第三章3自动机.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、形式语言概述文法推断句法分析自动机理论3.5 形式语言和自动机形式语言和自动机3.5.1 形式语言概述形式语言概述一、基本概念一、基本概念1、字母表、字母表：与所研究的问题有关的符号集合。例：V1=A,B,C,D,V2=a,b,c,d2、句子、句子(链链)：由字母表中的符号所组成的有限长度的符号串。3、句子、句子(链链)的长度的长度：所包含的符号数目。例:|a3b3c3|=94、语言、语言：由字母表中的符号组成的句子集合，用L表示。例：字母表V=a,bL1=ab,aab,abab有限语言L2=anbm|n,m=0,1,2.无限语言5、文法、文法：在一种语言中，构成句子所必须遵循的规则的集合，用

2、G表示。L(G)表示由文法G构成的语言。6、V*:由字母表V中的符号组成的所有句子的集合，包括空句子在内。例：V*,01,0017、V:不包括空句子在内的句子集合，即VV*()8、VT:终止符，不能再分割的最简基元的集合，用小写字母表示。VT=a,b,c9、VN:非终止符，由基元组成的子模式和句子的集合。用大写字母表示。VN=A,B,CVT，VN的关系：VTVN=(空集)VTVN=V（全部字母表）10、产生式、产生式(再写规则再写规则)P：存在于终止符和非终止符间的关系式。例：，VN，VN,VT.11、文法的数学定义、文法的数学定义：它是一个四元式，由四个参数构成。G=VN,VT,P,S 二二

3、.短语结构文法短语结构文法1.0型文法（无限制）型文法（无限制）设文法G=(VN,VT,P,S)VN：非终止符，用大写字母表示VT：终止符，用小写字符表示P：产生式S：起始符产生式P：，其中V+，V*，无任何限制(V+不包括空格,V*包括空格)例：0型文法G=(VN,VT,P,S)VN=S,A,BVP=a,b,cP:SaAbcAbbAAcBbccbBBbaBaaAaB(空格)SAa bcabAcabBbccaBbbccbbcc此文法可以产生：X=anbn+2cn+2n0X|n=0=bbcc由0型文法产生的语言称为0型语言。2.1型文法（上下文有关文法）型文法（上下文有关文法）设文法G=(VN,

4、VT,P,S)产生式P：1A212其中AVN，V+,1,2V*|1A2|12|,或|A|B|由上下文有关文法构成的语言称为上下文有关语言，用L(G1)表示，G1：上下文有关文法例：G=(VN,VT,P,S)VN=S,B,CVT=a,b,cP:SaSBCCBBCSabCbBbbbCbccCcc1S21aSBC2,bBbb对于SaSBC1=,2=,A=S,B=aSBC,并且|S|0解：G=(VN,VT,P,S)VT=(0,1)P:S0BB0BB1SB0VN=(S,B)四种文法的关系四种文法的关系:包含关系：限制不严格的文法必然包含限制严格的文法。3型2型1型0型三三.图象描述语言（图象描述语言（P

5、DL）1970年，Show提出图像描述语言任何图象都可用头尾来表示定义了四种二元连接算子1.a+b2.axb3.ab4.a*btha头与b尾相连hhta尾与b尾相连,形成两个头htta头与b头相连，形成一头二尾a头连b头,a尾连b尾，形成一头一尾hhttht基元bababab头头尾尾一元算子一个基元的头或尾可以与另一基元的头或尾相连而成为模式串，并可设置一些较复杂的联结关系和进行各种运算。例：文法G=(VN,VT,P,S)VT=,(),+,-,x,*,VN=S,A,B,CP:SASBA(b+(C+c)B(d+(a+(d)*C),C(b+c)*a)htbhtbab c dL(G)=(b+(b+c

6、)*a)+c);(d+(a+(d)*(b+c)*a)bcaaddbbccaCBSdb+导出过程da+c*aSAb+c+Cb+c*a3.5.2文法推断根据已知L(G)样本集导出未知文法G的过程。(一)基本定义：1.若在产生式中至少有一个产生式存在以下形式：AiiAii此文法G=(VN,VT,P,S)是循环文法或不确定，由它产生的语言L(Gt)为无限的。2.若文法G为不循环的，则必为确定的，且L(G)为有限的。样本集推断算法GtSt=(x1,x2 xt)导师(二)有限状态文法推断状态图表示方法，文法可以用图来表示例：G=(VN,VT,P,S)VN=S,A,B,CVT=0,1P:S0AA0AB0B0

7、BS1BA1BC0CS1CA1C1T：附加状态此文法可以产生的字符串x1=00n1,x2=0n+110m+1,x3=10n+1,x4=10n1ASCBT0000111110例：已知S+=(01，100，111，0010)VT=0，1x1=01,S0Z1,Z11x2=100,S1Z2,Z20Z3,Z30 x3=111,S1Z4,Z41Z5,Z51x4=0010,S0Z6,Z60Z7,Z71Z8,Z80VN=S,Z1,Z2,.Z8推断出的文法为：Gc=(VN,VT,Pc,S)VN=S,Z1,Z2,.Z8,VT=0，1PL:S0Z1,Z11,S1Z2,Z20Z3,Z30,S1Z4Z41Z5,Z51,

8、S0Z6,Z60Z7,Z71Z8,Z80,状态图：显然对任一有限取样都可用此法推断出规范文法，方法简单，适用计算机运算。缺点是非终止符太多，产生式也多。SZ1Z2Z3Z4Z5Z6Z7Z8T000000111111二.导出文法（简化规范文法）设：Gc为规范文法，非终止符集合VN=S,Z1,Z2,.Zn,把VN分成r个子集:VND=Bj,B1,B2.BrSBj,ZiBj这些子集满足：B Bj jBBk k=,=,jkjkB Bj j =V=VN N 定义导出文法GD=(VND,VT,PD,Bs)是由规范文法Gc产生的文法，导出规则如下：VT相同VND=(Bs,B1,B2,Br)Bs为起始符，Bs=

9、SPD定义:a.若ZZ在Pc中，则PD中有BiBj,ZaBi,ZBjb.若Za在Pc中，则PD中有Bia,ZaBirj=s例：S+=(01，100，111，0010)规范文法Gc=(VNC,VT,Pc,S)VNC=S,Z1,Z2,Z8对VNC分割为：VND=(S),(Z1,Z6,Z7),(Z2,Z3,Z8),(Z4,Z5)=Bs,B1,B2,B3对于S0Z1SBS,Z1B1PD中有BS0B1对于Z11Z1B1PD中有B11同理：BS1B2，B20B2,B20,BS1B3，B31B3，B31BS0B1，B10B1，B11B2，B20把相同的产生式合并后有：Pc：BS0B1，BS1B2，BS1Bs

10、,B11，B10B1，B11B2，B20B2,B20,B31B3，B31状态图导出文法等效规范文法L(GC)=L(GD)这种方法由于分割方式不同会导出不同的文法而分割方式又无系统理论作指导，而靠经验和试探。B5B3B2B1T00111111003.5.3句法分析一.用句法分析作模式识别设给定训练样本为M类即：1,2,M每类有N个样本，如1的训练样本为：S=(X1,X2,XN)T由这些样本可以推断出1类的文法G1,同样方法可推断出2类的文法G2,.M类的文法GM.对待识别句子X进行句法分析，若X属于由文法Gi构成的语言L(Gi)，则xi类。框图如下：XLG1 G1XLG2 G2XLGM GMx判

11、决Xi句法分析过程识别结果待识别句子二句法分析的主要方法1参考匹配法：2状态图法：适用于有限状态文法例：G=(VN,VT,P,S)VT=（0,1）VN=（S,A,B,C）P:S1A,S0B,S1C,A0A,A0 B0,C0C,C0,C1BX样本链码X1 XLG2 xX样本链码X2 X样本链码XN 判决XiXXiSCBAT1100010由状态图可以知道此文法可以识别的句子X1=10n+1,X2=00,X3=10n10,X4=10n+1未知句子：由状态图可知x1=10010(可以识别)x2=10110(不可以识别)00状态图3.5.4 自动机理论自动机理论引言：x当给出某类文法后，可根据它设计一种

12、相应的称为自动机的硬件模型。它由控制装置、输入带和某些类型的存储器组成，这种硬件模型是一种识别器称自动机。不同的自动机可以识别不同的文法形成的语言。0型文法：图灵机识别上下文有关型：线性约束自动机上下文无关型：下推自动机有限状态型：有限状态自动机识别器XLG G一、有限状态自动机有限状态自动机可以识别由有限状态文法所构成的语言1、基本定义：五元式M系统M=(,Q,q0,F)其中：输入符号的有限集合Q：状态的有限集合：状态转换函数是Q到Q的一种映射q0：初始状态 q0 Q F：终止状态集合2、有限自动机的结构转换函数：(q,a)=p表示有限控制器处于q状态，而输入头读入符号a，则有限控制器转换到

13、下一状态p。输入带0110输入头有限状态控制器Qq0 q1.F3、自动机识别输入字符串的方式L(M)=x|(q0,x)在F中(q,x)拒识，停机4、自动机的状态转换图:表示自动机识别过程例：M=(,Q,q0,F)Q q0,q1,q2,q30,1F=q0(q0,0)=q2,(q0,1)=q1,(q1,0)=q3,(q1,1)=q0,(q2,0)=q0,(q2,1)=q3,(q3,0)=q1,(q3,1)=q2q0q1q2q311110000输入：x=110101q0q1q0 q2 q3 q1 q0F X可以识别(q0,110101)=q0 例：已知自动机状态转换图如下 x1=aab 可以识别 x

14、2=abb 不可以识别可以识别的语言：L(G)=anbqB状态，只有出没有进，为不可到达状态 q状态，只有进没有出，为陷阱110110abbaabq0qAqBq a,b4、不确定的有限状态自动机即：(q,a)=q1,q2,qk当输入a时，下一个状态可 能为多个状态之一。例：M=(,Q,q0,F)Q q0,q1,q2,q3,q40,1F=q2，q4(q0,0)=q0,q3,(q0,1)=q0,q1(q1,0)=(在q1不会输入0)(q1,1)=q2(q2,0)=q2,(q2,1)=q2,(q3,0)=q4,(q3,1)=(q4,0)=q4,(q4,1)=q4状态转换图输入字串：010110 q0

15、 q0 q0 q0 q0q3 q1 q3 q1 q2 q2Fq0q3q1000，10，1110，1q4q2010110 输入字符串X=010110可以被自动机识别，但在识别过程中，对不确定状态需要进行试探。5、构造一个有限自动机定理1：设G=(VN,VT,P,S)为有限状态文法，一定存在一个有限状态自动机M=(,Q,S,F)使L(G)=L(M).已知有限状态文法G=(VN,VT,P,S)由有限状态文法构造有限自动机的步骤：VTQ VNTq0=S若P中有S，则F=(S,T),否则F=T若P中有Ba，则(B,a)=T,BVN,aVT若P中有BaC，则(B,a)=(C),B,CVN,aVT对VT中所

16、有的终止符a，都有(T,a)=,aVT例：有限状态文法G=(VN,VT,P,S)VN=S,BVT=0,1P:S0B,B0B/1S/0(B0B,B1S,B0)构造有限自动机M=(,Q,q0,F)VT 0,1Q VNT S,B，T q0=S P中无S F=T S0B,(S,0)=B,B0B,(B,0)=B,B1S,(B,1)=S,B0,(B,0)=T,P中无S1x,xVN,(S,1)=对VT=0,1有(T,0)=(T,1)构造的自动机M为M=(,Q,q0,F)，0,1,Q=S,B,T,q0=S,F=T:(s,0)=B (s,1)=(B,0)=B,T (B,1)=S (T,0)=(T,1)=设x=0

17、0100，可以识别可以证明：L(M)=L(G)010TSB06.由有限自动机M构造有限状态文法定理2：已知有限自动机M，则有一个有限状态文法G，使L(G)=L(M)。已知M=(,Q,q0,F)，构造G=(VN,VT,P,S)的步骤如下：VT VNQ Sq0 对于(B,a)=C,若B,CQ,a,则P中有BaC.若CF,则还有产生式Ba例：已知有限自动机M=(,Q,q0,F)，Q q0,q1,q2 0,1 F=q2(q0,0)=q2,(q0,1)=q1,(q1,0)=q2,(q1,1)=q0(q2,0)=q2，(q2,1)=q1构造G=(VN,VT,P,S)如下：VT 0,1VN=Q=q0,q1,

18、q2S=q0(q0,0)=q2,有q00q2,q2F有q00 (q0,1)=q1,有q01q1,(q1,0)=q2,有q10q2,q2F有q10 (q1,1)=q0,有q11q0,(q2,0)=q2,有q20q2,q2F有q20 (q2,1)=q1,有q21q1,有限状态文法为：G=(VN,VT,P,S)VT0,1VN=q0,q1,q2S=q0P:q00q2,q01q1,q00 q10q2,q11q0,q10 q20q2,q21q1,q20l状态图输入x1100由自动机M：(q0,1100)q2，q2F1100可以接受由有限文法G：q01q111q0110q21100L(M)=L(G)q0q1

19、q2111111000000000q1q0q2 T有限自动机有限状态文法二.下推自动机（PDA）可以识别由上下文无关文法构成的语言下推自动机结构：七元式MP=(,Q,q0,Z0,F,)其中,Q,q0,F同有限自动机:转换函数 :推下符号的有限集合 Z0:推下存贮器的起始符例如：(qi,b,Z)=(qj,)qi：目前状态，b：输入符号，Z：下推存储器的内容qj：下一状态，：下推存储器的下一状输入带只读头有限状态器Q读写头下推存储器（堆栈型）bBZ0识别输入字串X的方式终止状态方式空堆栈识别方式例：不确定的下推自动机MP=(q0),(a,b,c,d),(S,A,B,C,D),q0,S,)即：Q=(

20、q0),=(a,b,c,d),=(S,A,B,C,D),Z0=(S),F=()(q0,c,S)=(q0,DAB),(q0,C)(q0,a,D)=(q0,),(q0,b,B)=(q0,)(q0,d,C)=(q0,),(q0,a,A)=(q0,AB),(q0,CB)输入xcaadbb(q0,S)(q0,DAB)(q0,AB)(q0,CBB)(q0,BB)(q0,B)(q0,C)(q0,ABB)(q0,)堆栈变空，X=caadbb可以接受，这种不确定的下推自动机在识别过程中需试探进行。caadbda不通不通b三、图灵机：可以识别0型文法所产生的语言1、结构2、定义：一个图灵机T是一个六元式T=(,Q

21、,q0,F)其中：Q：状态集合 B,B空 =-B,q0起始状态，q0 QF:终止状态 控制装置读写头输入带图灵机是最复杂的自动机。它的一个构型用三元式（q,i）表示qQ,(-B)*映射的使用(q,Ai)=(P,X,R)在Ai处插入X后右移(q,Ai)=(P,X,L)在Ai处插入X后左移3、图灵机T所接受的语言例：T=(,Q,q0,F)(0,1),Q=(q0,q1,q5),=(0,1,B,X,Y),F=(q5)(q0,0)=(q1,x,R)(q1,0)=(q1,0,R)(q2,Y)=(q2,Y,L)(q3,Y)=(q3,Y,R)(q4,0)=(q4,0,L)(q1,Y)=(q1,Y,R)(q2,x)=(q3,x,R)(q3,B)=(q5,Y,R)(q4,x)=(q0,x,R)(q1,1)=(q2,Y,L)(q2,0)=(q4,0,L)输入：x=0011,则图灵机运行如下：(q0,0011,1)(q1,x011,2)(q1,x011,3)(q2,x0Y1,2)(q4,x0Y1,1)(q0,x0Y1,2)(q1,xxY1,3)(q1,xxY1,4)(q2,xxYY,3)(q2,xxYY,2)(q3,xxYY,3)(q3,xxYY,4)(q3,xxYY,5)(q5,xxYYY,6)q5F X0011被接受