形式语言概述.ppt

第七章句法结构模式识别形式语言概述文法推断句法分析自动机理论误差校正句法分析7-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、文法、文法：在一种语言中，构成句子所必须遵循的规则的集合，用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二二.短语结构文法短语结构文法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,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型三三.图象描述语言（图象描述语言（PDL）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)htbhtbabcdL(G)=(b+(b+c)*a)+c);(d+(a+(d)*(b+c)*a)bcaaddbbccaCBSdb+导出过程da+c*aSAb+c+Cb+c*a求表达式的规则：脱括号由内往外的次序进行，无括号由左向右进行对于连接基元组成基元结构，必须符合规定的连接点头，尾数目例：给出一个PDL文法G=(S,A,B,C,D,E,a,b,d,(,),+,*,P,S)P:S(A+(B)B(C)+DDbE(a+b)AdCE*cD(d)Aac可以导出手写大写字符“A”的四种表达式S(A+(B)(a+(B)(a+(C)+D)(a+(E*c)+D)(a+(a+b)*c)+D)(a+(a+b)*c)+(d)(d+(a+b)*c)+b),(a+(a+b)*c)+b),(d+(a+b)*c)+(d)adbbaabbbaddcdaabc四四.标准形式文法标准形式文法在句法分析和自动机的一些算法中，有时要求标准化文法，下面介绍二种标准文法。1.乔姆斯基(Chomsky)范式,一种上下文无关文法如果它的每个产生式P都符合二种形式：ABC(A,B,CVN)或Aa(AVN,aVT)该文法称Chomsky范式已知上下文无关文法 G=(VN,VT,P,S)用以下步骤产生Chomsky范式的等价文法G=(VN,VT,S)若中已经是ABC，Aa形式放入中中其它的产生式形式为A12.n其中iVN或iVT用下面的产生式集合代替：AY1Y2.nY2.nY2Y3.nYn-1.nYn,n-1YiVN若iVN,则令Yi=i；若iVT,再引入Yii例：把文法G=(VN,VT,P,S)变成Chomsky范式VN=S,A,BVP=a,bP:SAB，Aa,AabABa，Bb把SAB，Aa,Bb放入中AabABa，A12345，其中1=5=a,2=b,3=A,4=BAY1Y2345,Y2345Y2Y345,Y345Y3Y45,Y45Y4Y5,3,4VNY345AY45,Y45BY5,125VT引入新的产生式，Y1a,Y2b,Y5a符合chomsky范式文法，文法G2=(VN,VT,S)VN=Y1Y2345,Y2Y345,Y45,Y5,S,A,BAY1Y2345,Y1a,Y2345Y2Y345,Y2b,Y345AY45,Y45BY5,Y5a,SBA,Aa,Bb若x=bababa用G1导出：SBAbAbabABabababa,用G2导出：SBAbY1Y2345.baY2345baY2Y345babY345babAY45babaY5bababY5bababa用原文法G1只用四步可以导出bababa而用标准文法G2则用九步才导出2.格雷巴赫范式格雷巴赫范式(Greibach)若一个上下文无关文法具有P形式：Aa,AVN,aVT,VN*(带空格)则此文法称为Greibach范式。例：上下文无关文法G=(VN,VT,P,S)VN=S,C,VT=a,b,cP形式：SaCbb,CaCbbCc变成Greibach范式：Cc即Cc符合Greibach范式，不变SaCbb,用SaCBB,Bb代替CaCbb,用CaCBB,Bb代替符合Greibach范式：P:SaCBB,CaCBB,Cc,Bb,五五.高高维维文文法法：上面我们介绍的都是一维链（串）文法，为了描述更复杂的图形、图象,需要用高维文法,包括树文法，图文法,网文法等等。1.树文法：树文法：定义：四元组Gt=(v,r,P,S)其中V=VNVT，r:秩(一个节点的直接分支数)P形式：TiTjTi,Tj都是树由Gt产生的语言叫树语言。L(Gt)=T|TT,TiTTiS,T是带有VT中结点的树集合扩展树文法扩展树文法：全部产生式形式其 中 x1,x2.xnVN,xVT，nr(x)具有上面产生式形式的树文法称扩展的树文法。GtXxx1,x2xn例：Gt=(v,r,P,S)V=VNVT（S,A,B,K,a,b）VT(,),r(a)=(2,0),r(b)=(2,0),r(k)=2P:SKAaBbAaBbSKabABABABABababkABSKabABABabk导出树导出图bbaa例2：在氢云室内用正粒子打击核目标碰撞发出的射线可以用树文法来描述。树文法Gt=(v,r,P,S)，VN（S,A,B），VT(a,b)基本定义：P:ab(凸弧)(凹弧)S a|SS aABS aABBAS aABBAABA a|AA aB a|BB ar(a)=(0,1,2,4,6),r(b)=(0,1)射线导出树：S aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbaab射线图：7-2文法推断根据已知L(G)样本集导出未知文法G的过程。(一)基本定义：1.若在产生式中至少有一个产生式存在以下形式：AiiAii此文法G=(VN,VT,P,S)是循环文法或不确定，由它产生的语言L(Gt)为无限的。2.若文法G为不循环的，则必为确定的，且L(G)为有限的。样本集推断算法GtSt=(x1,x2xt)导师3.当L(GA)=L(GB)时，则GA与GB等效，等价。例：有限状态文法GA=(VN,VT,P,S),VN=S,VT=0,1P:S0S,S1则L(GA)=0n1|n=1,2,上下文无关文法GB=(VN,VT,P,S),VN=S，A,VT=0,1P:SA1,AAA,A0则L(GB)=0n1|n=1,2,L(GA)=L(GB)GA与GB等效4.S+是L(G)的子集，即S+L(G)，称为正取样，是子集，记为称为负取样，5.若正取样S+=(x1,x2.xi)=L(G)，称为S+是完备的，负取样=(x1,x2.xi)=,称也是完备的，且St=(S+,S-)=(x1,x2.xi)=(L(G),)也是完备的。(二)有限状态文法推断状态图表示方法，文法可以用图来表示例：G=(VN,VT,P,S)VN=S,A,B,CVT=0,1P:S0AA0AB0B0BS1BA1BC0CS1CA1C1T：附加状态此文法可以产生的字符串x1=00n1,x2=0n+110m+1,x3=10n+1,x4=10n1ASCBT0000111110一.规范确定文法已知正取样S+=(x1,x2.xn)推断规范文法Gc=(VN,VT,PL,S)的步骤如下：VT=S+中不同的终止符设xi=ai1ai2.ain链PL:Sai1Zi1Zi1VN,ai1VTZi1ai2Zi2Zi2VN,ai2VTZIn-2ain-1Zin-1Zin-1VN,ain-1VTZIn-1ainainVTVN=S,Zi1,Zi2,.Zin-1,此文法产生的语言是确定的，有限的，且有性质：L(GL)=S+例：已知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,S0Z6,Z60Z7,Z71Z8,Z80,状态图：显然对任一有限取样都可用此法推断出规范文法，方法简单，适用计算机运算。缺点是非终止符太多，产生式也多。SZ1Z2Z3Z4Z5Z6Z7Z8T000000111111二.导出文法（简化规范文法）设：Gc为规范文法，非终止符集合VN=S,Z1,Z2,.Zn,把VN分成r个子集:VND=Bj,B1,B2.Br SBj,ZiBj这些子集满足：B Bj jB Bk k=,jk=,jkB Bj j=V=VN N 定义导出文法GD=(VND,VT,PD,Bs)是由规范文法Gc产生的文法，导出规则如下：VT相同VND=(Bs,B1,B2,Br)Bs为起始符，Bs=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,B11，B10B1，B11B2，B20B2,B20,B31B3，B31状态图导出文法等效规范文法L(GC)=L(GD)这种方法由于分割方式不同会导出不同的文法而分割方式又无系统理论作指导，而靠经验和试探。B5B3B2B1T0011111100三.形式微商文法形式微商定义：集合A对于符号aVT的形式微商是：DaA=X|axA若a=(空串)，则DA=A例：A=S+=01,100,111,0010则D0A=D0S+=1，010D1A=D1S+=00，11扩展：二次微商Da1a2A=Da2(Da1A)n次微商：Da1a2an1anA=Dan(Da1a2an1)A对上例：D00S+=D0(D0S+)=D0(1.010)=(10)D11S+=(1)D000S+=,D100S+=已知正取样S+=x1,x2,.xnT形式微商文法GCD=(VN,VT,P,S),定义如下：VT=（S中不同的符号）VN=U=(U1,U2,UP)其中Ui(i=1,2p)是S+的形式微商，且令U1=DS起始符，S=U1=DS令Ui,UjVNP:当DaUi=Uj,则UiaUj当DaUi，则Uia例：S+=101,111,推断形式微商文法如下：VT=（0,1）DS=S=101,111=U1=S起始符D1S=01,11=D1S=U2S1U2D10S=D0(D1S)=D0U2=1=U3U20U3D11S=D1(D1S)=D1U2=1=U3U21U3D101S=D1(D10S)=D1U3=U31D111S-=D1(D11S)=D1U3=U31形式微商文法为(相同产生式合并)：GCD=(VN,VT,P,S)VT=（0,1）VN=（S,U2,U3）P:S1U2,U21U3,U20U3,U31状态图为：SU2U3T110.1四.k-尾文法：对形式微商文法进行长度限制，并对等价状态进行合并k尾定义：(U,A,k)=X|XDaA|X|k形式微商文法中两个状态间的等效性的充要条件为：(XiS+k)=g(XjS+k)-k尾相等利用k尾等效把形式微商文法中的等效状态合并，导出k尾文法。例：S+=01,1001先求形式微商文法DS+=S+=01,1001=U1=SD0S+=1=U2S0U2D01S+=D1(D0S+)=D1U2=U21D1S+=001=U3S1U3D10S-=01=D0U3=U4U30U4D100S+=1=D0U4=U5U40U5D1001S+=U51求k尾等效状态：|X|kk=4,k=3,k=2,k=1U1=DS+=01,1001，01，0,1，U2=D0S+=1，1，1，1U3=D1S+=001，001,，U4=D10S+=01，01，01，U5=D100S+=1，1，1，1等效状态为k=4,k=3,k=2,k=1(U2,U5)(U1,U4)(U1,U4)(U1,U3,U4)(U2,U5)(U2,U5)(U2,U5,)合并状态，导出k尾文法k=4时S0U2,U11,S1U3,U30U4,U40U2k=3,2时S0U2,U21,S1U3,U30Sk=1时S0U2,U21,S1S,S0S状态图讨论：推断k尾文法时，k尾的选择很重要，k小时文法简单，但循环产生式增多，这样就可以导出更多的S+以外的子串来，有时这是不允许的。1SSSTTT111U2U3U4U2U3U20000000,11K=2,3K=1K=4三.树文法推断一棵树可以看成一个多枝的链。因此前边讲的链（串）文法的推断方法可以用在树文法的推断上。任何一个数字化的网络模板都可以用树结构来表示如下：由下面的四种方式表示成树枝全从根开始的树。X11X12.X1nX21X22.X2n.Xn1Xn2.Xnn树状的数字化网络模式S 根树干N个枝S树干M个枝.树文法先选一个合适的树干，由树干推出一个链文法再推各树枝的文法把树干文法与树枝文法合并树干树干树枝树枝根SS例：已知数字化模式L1L2L3L4L5L6000111000111110000110000111100111000110000100000R1R2R3R4R5R6树干根S先由树干推出树干文法GAP:S A1A1$A2|R1L1A2$A3|R2L2A3$A4|R3L3A4$A5|R4L4A5$A6|R5L5A6$|R6L6上面推出树干文法GA,再推出树枝文法GL1,GL2.GL6,GR1,GR2,.GR6再将树干文法与树枝文法合并GT=GAGLGR7-3句法分析一.用句法分析作模式识别设给定训练样本为M类即：1,2,M每类有N个样本，如1的训练样本为：S=(X1,X2,XN)T由这些样本可以推断出1类的文法G1,同样方法可推断出2类的文法G2,.M类的文法GM.对待识别句子X进行句法分析，若X属于由文法Gi构成的语言L(Gi)，则xi类。框图如下：XLG1G1XLG2G2XLGMGMx判决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样本链码X1XLG2xX样本链码X2X样本链码XN判决XiXXiSCBAT1100010由状态图可以知道此文法可以识别的句子X1=10n+1,X2=00,X3=10n10,X4=10n+1未知句子：由状态图可知x1=10010(可以识别)x2=10110(不可以识别)00状态图2、填充树图法(适用于上下文无关文法)：当给定某待识别链X及相应的文法G时，我们建立一个以X为底，S为顶的三角形，按文法G的产生式来填充此三角形，使之成为一个分折树。若填充成功表明 否则填充树有二种方法由顶向底剖析由底向顶剖析填充树图法在填充三角形时应遵守三条原则：首位考察：首先考虑选用某个产生式后能导出X的 第一个字符用某产生式后，不能出现X中不包含的终止符用某产生式后，不能导致符号串变长(变短)SX由顶向底(由上而下)剖析例：G=(VN,VT,P,S)VT=（0,1）VN=（S,A,B）P:S1 SB1 SB B1A BB1A A0A A0设：X=1000，用由上而下剖析方法判断X是否属于L(G)BB10AASBS1ASA00 X=1000L(G)由底向顶(由下而上)剖析例：G=(VN,VT,P,S)VT=（a,b,c,f,g）VN=（S,T,I）P:ST Ia STfs Ib TIgT Ic TI 设：X=afbgc用Ia 用TI用Ib用Ic用TIafbgcIafbgcITafbgcITIafbgcITIIafbgcITIITafbgcITIITTafbgcITIITTSafbgcITIITTS用TIgT用ST用STfSSX=afbgcL(G)三、杨格(Younger)法Younger法是个较前述各方法更系统的方法，适用于任何相应于2型文法类别的识别。下面结合一例说明此方法。设有一代表类别的文法G=(VN,VT,P,S)其中VT=（0,1,2）VN=（S,B）P:SSBS BBB BBS S2 B0 B1现在要用Younger法来识别X=202102是否G.首先将上述文法化为Chomsky标准形式。此形式文法的代换式只有两种形式，即 非终止符非终止符非终止符（双非终止符形式）非终止符终止符（终止符形式）将式上所示文法中第1条改为SSA，ABS两条（A为人为增加的非终止符），使整个文法成为：SSA ABS BBB BBS S2 B0 B1 而令VT=（0,1,2）VN=（S,A,B）便完成了Chomsky形式的转化。Younger法将对Chomsky形式文法进行分析。待识别符号串的任一“子串”都可用i,j两个整数来指明：所谓子串即把一符号串任一截取一段，这段符号串（包括单个符号）就叫原来符号的子串。譬如符号串202102的子串就有2，0，2，1，0，2（个数为1的子串）；20，02，21，10，02（个数为2的子串）；202，021，210，102（个数为3的子串）；2021，0210，2102（个数为4的子串）；20210，02102（个数为5的子串）和202102（个数为6的子串即原符号串）。这21个符号串都可由正整数i,j表示。i代表子串中符号的个数（即子串长度），而j表示这子串的首位在原符号串中占第几位。如上面所举的第1子串“2”，即为i=1、j=1的子串，第13个子串021即是i=3、j=2的子串。可见，任一子串都可用i,j二数来指明。识别表的建立，关键问题是根据给出的待识别串X,建立一识别表。对于202102,根据所给出的文法算得的识别表如下：i123j123456123451234所有子串所有子串2021022002211002202021210102所所有有VNS A B 4561231212021021021022021002102202102 表中每一位置由三个符号表示。头二个即i和j，而第三个是非终止符(现为S,A,B,见表中第一列).。i1栏中第2列(j=2)与B行相交的位置即为(1,2,B),余类推。表中(1,2,B)位置上有，代表对于所给文法，B可导出i=1,j=2的子串，即“0”。反之，若这位置上为，则说明B不能导生子串“0”。再举一例，第2栏中第2列、A行位置应该用（2,2,A）表示，此位置上有，代表对于所给文法，B可导出I=2,j=2的子串，即“02”（见表）。（）经分析可知，能容易地根据给出的符号串(202102),在i=1栏的各位置上打或，又根据此栏结果，由一递推公式将i=2栏各位置打上或。如此递推下去便可将表填满，识别表也就建成。在识别时只需检查最后一栏(现为i=6栏)第一列第S行位置即(6,1,S)上是还是。若是，表示S可导生子串202102，故判202102符合给出的文法。反之，即判不符合此文法。建立识别表的递推规则递推规则：将要决定或 的位置表为(i,j,k)通用形式。K代表非终止符。又将r(i,j,K)称为(i,j,k)位置的识别值。此值为0或1，分别表示(i,j,k)位置上是或。计算r(i,j,K)(也即决定或)的步骤是：(i)算出其中K1,K2代表KK1K2.例如：ABS,K=A,K1=B,K2=S.（1）(ii)如果(i,j,k)左侧是K的代换式不只一个，譬如K是B时，即有BBB、BBS两个。这时则把B、B叫做K1、K2，根据它计算式(1)中各值；此外，还需将B、S叫做K1、K2，再按下面式算出：对于所有i,j,k（包括题中各个非终止符），算出式(2)中的各值。只要其中之一值为1，便在相应当位置上打，否则打。如此便可填满整个识别表若左侧为K的代换式有三个，可按上述原则，再增加计算将(1)式中K1、K2改为K1、K2后的各值，余类推。现作为例子用递推规则考察(2,2,A)中的或。由于左侧为A的代换式只有ABS一个，故此时对于(1)式只需计算r(1,2,B)r(1,3,S)=1 1=1,即(2,2,A)应打。此结果与前面分析得到的相符。根据上述递推规则和给定的文法，容易编制计算机程序。当待识别串X进入时，按此算出识别表，并检查表中最后一列S位置上是还是；若为，便判属于给定文法相应的类别，否则判为不属于此类别。作业：对作业：对Younger法的例题编程上机，打出识别表。法的例题编程上机，打出识别表。四四.CYK(CYK(CockeCocke-Younger-Younger-KasamiKasami)剖析剖析(列表法列表法)条件：适用上下文无关文法 产生式应符合Chomsky范式已知输入串X=a1a2.an构造三角形剖析表步骤如下：令j=1,按从i=1到i=n次序，求ti1.把X分解为长度为1的子串，对子串ai,若p中有Aai,把A填入ti1中令j=2,按从i=1到i=n-1次序，求ti2，即第二行。把X分解为长度为2的子串，对子串aiai+1,若p中有ABC,且有Bai,Cai+1则把A填入ti2中对于j2,1in,已求出tij-1,现求tij对于1kj中的任一k,当P中有ABC且B在tik中.C在ti+k,j-k中时，把A填入tij中重复直至完成此表，或整行都是空(拒识)当且仅当S在tin中，XL(G)，即由G可导出X分析一个长度为n的串，所用的存储量正比于n2,运算次数正比于n3。12345i54321tij剖析表j例：G=(VN,VT,P,S)VT=（a,b）VN=（S,A,B,C）P:SAB SAC Aa Bb CSB 输入串：X=aabb=a1a2a3a4 所有产生式符合Chomsky范式令j=1,计算ti1，1i4i=1,a1=a,P中有Aa 有t11=(A)i=2,a2=a,P中有Aa 有t21=(A)i=3,a3=b,P中有Bb 有t31=(B)i=4,a4=b,P中有Bb 有t41=(B)第一次迭代，令j=2,计算ti2，1i3对于a1a2=aa,不能产生aa 有t21=对于a2a3=ab,SAB,Aa,Bb 有t22=(s)对于a3a4=bb,P中产生式不能产生bb 有t32=()1234ij4321AABB S 第二次迭代，令j=3,计算ti3，1i2对于a1a2a3=aab,不能产生aab 有t13=对于a2a3a4=abb,CSB,Sab,Bb 有t23=(C)第三次迭代，令j=4,计算ti4，对于a1a2a3a4=aabb,SAC,Aa,Cabb 有t14=(S)t14=S X=aabb在L(G)中，此串被识别。此算法实际上是一个由底向顶剖析算法。4321AABB S1234iSC剖析表aabbAABBSSC导出树+作业：对CYK算法的例题上机编程，打出剖析表和导出树。7-4自动机理论自动机理论引言：x当给出某类文法后，可根据它设计一种相应的称为自动机的硬件模型。它由控制装置、输入带和某些类型的存储器组成，这种硬件模型是一种识别器称自动机。不同的自动机可以识别不同的文法形成的语言。0型文法：图灵机识别上下文有关型：线性约束自动机上下文无关型：下推自动机有限状态型：有限状态自动机识别器XLGG一、有限状态自动机有限状态自动机可以识别由有限状态文法所构成的语言1、基本定义：五元式M系统M=(,Q,q0,F)其中：输入符号的有限集合Q：状态的有限集合：状态转换函数是Q到Q的一种映射q0：初始状态 q0 Q F：终止状态集合2、有限自动机的结构转换函数：(q,a)=p表示有限控制器处于q状态，而输入头读入符号a，则有限控制器转换到下一状态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 可以识别 x2=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状态转换图输入字串：010110q0 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中所有的终止符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=00100，可以识别可以证明：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,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,q20状态图输入x1100由自动机M：(q0,1100)q2，q2F1100可以接受由有限文法G：q01q111q0110q21100L(M)=L(G)q0q1q2111111000000000q1q0q2 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=(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例：确定自动机MP=(,Q,q0,Z0,F,)=(0,1)Q q0,q1,q2(2,0)F=(q0)Z0=(Z)(q0,0,Z)=(q1,02),(q1,0,0)=(q1,00)(q1,1,0)=(q2,),(q2,1,0)=(q2,)(q2,2)=(q0,)X=0011(q0,Z)(q1,02)(q1,002)(q2,02)(q2,2)(q0,)堆栈变空，X0011可以被接受0011由上、下文无关文法G=(VN,VT,P,S)构造一个下推自动机MP=(,Q,q0,Z0,F,)步骤如下：VT VNVTZ0=SQ=q0F=(用堆栈变空来识别)由p构造函数：若A 在P中，则有(q0,A)=(q0,)：对VT中所有终止符a，有(q0,a,a)=(q0,)例：G=(s,A),(a,b,c,d),p,SP:ScA,AaAb,Ad构造MP=(,Q,q0,Z0,F,)Q=q0 VTa,b,c,dZ0=S VNVT=(S,A,a,b,c,d)F=(由堆栈变空来识别)在P中有S cA，则(q0,S)=(q0,cA)A aAb，则(q0,A)=(q0,aAb)A d，则(q0,A)=(q0,d)由上式可合并：(q0,A)=(q0,aAb),(q0,d)由规则对VT：(q0,a,a)=(q0,)，(q0,b,b)=(q0,)(q0,c,c)=(q0,)，(q0,d,d)=(q0,)对x=caadbb(q0,S)无，可以先输入空格。(q0,S)(q0,CA)(q0,A)(q0,aAb)(q0,Ab)(q0,aAbb)(q0,Abb)(q0,dbb)(q0,bb)(q0,b)(q0,)堆栈空若文法符合Creibadh范式，产生式形式为：Aa,AVN，aVT，上面规则,合成一个规则，若A ,则有(q0,a,A)=(q0,)C caadbb例：Greibach范式文法G=(S,A,B,a,b,c,d,P,S)P:ScA,AaAB,Ad,Bb可以构造一个下推自动机MP=(,Q,Z0,q0,F)其中 VTa,b,c,d，VN=(S,A,B),Q=q0Z0=S,F=因P中有S cA，则(q0,c,S)=(q0,A)A aAB，则(q0,a,A)=(q0,AB)A d，则(q0,d,A)=(q0,)B b，则(q0,b,B)=(q0,)输入X=caadbb(q0,S)(q0,A)(q0,AB)(q0,ABB)(q0,BB)(q0,B)(q0,)只用六步就完成，而上例用九步。说明符合Greibach范式的文法产生的语言容易被下推自动机识别。caadbb 三、图灵机：可以识别0型文法所产生的语言1、结构2、定义：一个图灵机T是一个六元式T=(,Q,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,