模式識(shí)別導(dǎo)論(七)

1、第七章句法結(jié)構(gòu)模式識(shí)別形式語(yǔ)言概述文法推斷句法分析自動(dòng)機(jī)理論誤差校正句法分析7-1 形式語(yǔ)言概述形式語(yǔ)言概述一、基本概念一、基本概念1、字母表、字母表：與所研究的問(wèn)題有關(guān)的符號(hào)集合。例：V1=A,B,C,D,V2=a,b,c,d2、句子、句子(鏈鏈)：由字母表中的符號(hào)所組成的有限長(zhǎng)度的符號(hào)串。3、句子、句子(鏈鏈)的長(zhǎng)度的長(zhǎng)度：所包含的符號(hào)數(shù)目。例:|a3b3c3|=94、語(yǔ)言、語(yǔ)言：由字母表中的符號(hào)組成的句子集合，用L表示。例：字母表V=a,bL1=ab,aab,abab有限語(yǔ)言L2=anbm|n,m=0,1,2.無(wú)限語(yǔ)言5、文法、文法：在一種語(yǔ)言中，構(gòu)成句子所必須遵循的規(guī)則的集合，用G表示

2、。L(G)表示由文法G構(gòu)成的語(yǔ)言。6、V*:由字母表V中的符號(hào)組成的所有句子的集合，包括空句子在內(nèi)。例：V*,01,0017、 V:不包括空句子在內(nèi)的句子集合，即VV*()8、VT:終止符，不能再分割的最簡(jiǎn)基元的集合，用小寫字母表示。VT=a,b,c9、 VN:非終止符，由基元組成的子模式和句子的集合。用大寫字母表示。VN=A,B,CVT，VN的關(guān)系：VTVN=(空集) VTVN=V（全部字母表）10、產(chǎn)生式、產(chǎn)生式(再寫規(guī)則再寫規(guī)則)P：存在于終止符和非終止符間的關(guān)系式。例：，VN，VN,VT.11、文法的數(shù)學(xué)定義、文法的數(shù)學(xué)定義：它是一個(gè)四元式，由四個(gè)參數(shù)構(gòu)成。G=VN,VT,P,S 二二

3、. 短語(yǔ)結(jié)構(gòu)文法短語(yǔ)結(jié)構(gòu)文法1. 0型文法（無(wú)限制）型文法（無(wú)限制）設(shè)文法G=(VN,VT,P,S)VN：非終止符，用大寫字母表示VT：終止符，用小寫字符表示P：產(chǎn)生式S：起始符產(chǎn)生式P：，其中V+，V*，無(wú)任何限制(V+不包括空格,V*包括空格)例：0型文法G=(VN,VT,P,S)VN=S,A,BVP=a,b,cP:SaAbcAbbAAcBbccbBBbaBaaAaB(空格)SAa bcabAcabBbccaBbbccbbcc此文法可以產(chǎn)生：X=anbn+2cn+2n0X|n=0=bbcc由0型文法產(chǎn)生的語(yǔ)言稱為0型語(yǔ)言。2. 1型文法（上下文有關(guān)文法）型文法（上下文有關(guān)文法）設(shè)文法G=(

4、VN,VT,P,S)產(chǎn)生式P：1A212其中AVN，V+,1,2V*|1A2|12|,或|A|B|由上下文有關(guān)文法構(gòu)成的語(yǔ)言稱為上下文有關(guān)語(yǔ)言，用L(G1)表示，G1：上下文有關(guān)文法例：G=(VN,VT,P,S)VN=S,B,CVT=a,b,cP:SaSBCCBBCSabCbBbbbCbccCcc1S21aSBC2,bBbb對(duì)于SaSBC1=,2=,A=S,B=aSBC,并且|S|0解：G=(VN,VT,P,S)VT=(0,1)P:S0BB0BB1SB0VN=(S,B)四種文法的關(guān)系四種文法的關(guān)系 :包含關(guān)系：限制不嚴(yán)格的文法必然包含限制嚴(yán)格的文法。3型2型1型0型三三. 圖象描述語(yǔ)言（圖象描

5、述語(yǔ)言（PDL）1970年，Show提出圖像描述語(yǔ)言任何圖象都可用頭尾來(lái)表示定義了四種二元連接算子1.a+b2.axb3.ab4.a*btha頭與b尾相連hhta尾與b尾相連,形成兩個(gè)頭htta頭與b頭相連，形成一頭二尾a頭連b頭,a尾連b尾，形成一頭一尾hhttht基元bababab頭頭尾尾一元算子一個(gè)基元的頭或尾可以與另一基元的頭或尾相連而成為模式串，并可設(shè)置一些較復(fù)雜的聯(lián)結(jié)關(guān)系和進(jìn)行各種運(yùn)算。例：文法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)=

6、(b+(b+c)*a)+c);(d+(a+(d)*(b+c)*a)bcaaddbbccaCBSdb+導(dǎo)出過(guò)程da+ c*aSAb+c+Cb+ c*a求表達(dá)式的規(guī)則： 脫括號(hào)由內(nèi)往外的次序進(jìn)行，無(wú)括號(hào)由左向右進(jìn)行 對(duì)于連接基元組成基元結(jié)構(gòu)，必須符合規(guī)定的連接點(diǎn)頭，尾數(shù)目例：給出一個(gè)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可以導(dǎo)出手寫大寫字符“A”的四種表達(dá)式S(A+(B)(a+(B)(a+(C)+D)(a+(E*c)+D)(a+(a+b)*c)+D)(a+(a+b)*c)+(d)(d+(

7、a+b)*c)+b),(a+(a+b)*c)+b),(d+(a+b)*c)+(d)adbbaabbbaddcdaabc四四.標(biāo)準(zhǔn)形式文法標(biāo)準(zhǔn)形式文法在句法分析和自動(dòng)機(jī)的一些算法中，有時(shí)要求標(biāo)準(zhǔn)化文法，下面介紹二種標(biāo)準(zhǔn)文法。1.喬姆斯基(Chomsky)范式,一種上下文無(wú)關(guān)文法如果它的每個(gè)產(chǎn)生式P都符合二種形式：ABC(A,B,CVN)或Aa(AVN,aVT)該文法稱Chomsky范式已知上下文無(wú)關(guān)文法G=(VN,VT,P,S)用以下步驟產(chǎn)生Chomsky范式的等價(jià)文法G=(VN,VT,S)若中已經(jīng)是ABC，Aa形式放入中中其它的產(chǎn)生式形式為A12.n其中iVN或iVTPP用下面的產(chǎn)生式集合代替

8、：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引入新的產(chǎn)生式，Y1a,Y2b,Y5aP符合chomsky范式文法，文法G2=(VN,VT,S)VN=Y1Y2345,Y2Y345,Y45,Y

9、5,S,A,BAY1Y2345,Y1a,Y2345Y2Y345,Y2b,Y345AY45,Y45BY5,Y5a,SBA,Aa,Bb若x=bababa用G1導(dǎo)出：SBAbAbabABabababa,用G2導(dǎo)出：SBAbY1Y2345.baY2345baY2Y345babY345babAY45babaY5bababY5bababa用原文法G1只用四步可以導(dǎo)出bababa而用標(biāo)準(zhǔn)文法G2則用九步才導(dǎo)出P2. 格雷巴赫范式格雷巴赫范式(Greibach)若一個(gè)上下文無(wú)關(guān)文法具有P形式：Aa,AVN,aVT,VN*(帶空格)則此文法稱為Greibach范式。例：上下文無(wú)關(guān)文法G=(VN,VT,P,S)V

10、N=S,C,VT=a,b,cP形式：SaCbb,CaCbbCc變成Greibach范式：Cc即Cc符合Greibach范式，不變SaCbb,用SaCBB,Bb代替CaCbb,用CaCBB,Bb代替符合Greibach范式：P:SaCBB,CaCBB,Cc,Bb,五五.高維文法：高維文法：上面我們介紹的都是一維鏈（串）文法，為了描述更復(fù)雜的圖形、圖象,需要用高維文法,包括樹(shù)文法，圖文法,網(wǎng)文法等等。 1. 樹(shù)文法：樹(shù)文法：定義：四元組Gt=(v,r,P,S)其中V=VNVT，r:秩(一個(gè)節(jié)點(diǎn)的直接分支數(shù))P形式：TiTjTi,Tj都是樹(shù)由Gt產(chǎn)生的語(yǔ)言叫樹(shù)語(yǔ)言。L(Gt)=T|TT,TiTTiS

11、,T是帶有VT中結(jié)點(diǎn)的樹(shù)集合擴(kuò)展樹(shù)文法擴(kuò)展樹(shù)文法：全部產(chǎn)生式形式其中x1,x2.xnVN,xVT，nr(x)具有上面產(chǎn)生式形式的樹(shù)文法稱擴(kuò)展的樹(shù)文法。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導(dǎo)出樹(shù)導(dǎo)出圖bbaa例2：在氫云室內(nèi)用正粒子打擊核目標(biāo)碰撞發(fā)出的射線可以用樹(shù)文法來(lái)描述。樹(shù)文法Gt=(v,r,P,S)，VN（S,A,B），VT(a,b)基本定義：P:ab(凸弧)(凹弧)S a|SS aAB

12、S aABBAS aABBAABA a|AA aB a|BB ar(a)=(0,1,2,4,6),r(b)=(0,1)射線導(dǎo)出樹(shù)：S aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbaab射線圖：7-2文法推斷根據(jù)已知L(G)樣本集導(dǎo)出未知文法G的過(guò)程。(一)基本定義：1.若在產(chǎn)生式中至少有一個(gè)產(chǎn)生式存在以下形式：AiiAii此文法G=(VN,VT,P,S)是循環(huán)文法或不確定，由它產(chǎn)生的語(yǔ)言L(Gt)為無(wú)限的。2.若文法G為不循環(huán)的，則必為確定的，且L(G)為有限的。樣本集推斷算法GtSt=(x1,x2xt)導(dǎo)師3.當(dāng)L(GA)=L(GB)時(shí)，則GA與GB等效，等價(jià)。例：有限狀

13、態(tài)文法GA=(VN,VT,P,S),VN=S,VT=0,1P:S0S,S1則L(GA)=0n1|n=1,2,上下文無(wú)關(guān)文法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)，稱為正取樣，是子集，記為稱為負(fù)取樣，5.若正取樣S+=(x1,x2.xi)=L(G)，稱為S+是完備的，負(fù)取樣=(x1,x2.xi)=,稱也是完備的，且St=(S+,S-)=(x1,x2.xi)=(L(G),)也是完備的。S)(GL)(GLSS)(GLS)(GL(二)有限狀態(tài)文法推斷

14、狀態(tài)圖表示方法，文法可以用圖來(lái)表示例：G=(VN,VT,P,S)VN=S,A,B,CVT=0,1P:S0AA0AB0B0BS1BA1BC0CS1CA1C1T：附加狀態(tài)此文法可以產(chǎn)生的字符串x1=00n1,x2=0n+110m+1,x3=10n+1,x4=10n1ASCBT0000111110一.規(guī)范確定文法已知正取樣S+=(x1,x2.xn)推斷規(guī)范文法Gc=(VN,VT,PL,S)的步驟如下：VT=S+中不同的終止符設(shè)xi=ai1ai2.ain鏈PL:Sai1Zi1Zi1VN,ai1VTZi1ai2Zi2Zi2VN,ai2VTZIn-2ain-1Zin-1Zin-1VN,ain-1VTZIn

15、-1ainainVTVN=S,Zi1,Zi2,.Zin-1,此文法產(chǎn)生的語(yǔ)言是確定的，有限的，且有性質(zhì)：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,狀態(tài)圖：顯

16、然對(duì)任一有限取樣都可用此法推斷出規(guī)范文法，方法簡(jiǎn)單，適用計(jì)算機(jī)運(yùn)算。缺點(diǎn)是非終止符太多，產(chǎn)生式也多。SZ1Z2Z3Z4Z5Z6Z7Z8T000000111111二.導(dǎo)出文法（簡(jiǎn)化規(guī)范文法）設(shè)：Gc為規(guī)范文法，非終止符集合VN=S,Z1,Z2,.Zn,把VN分成r個(gè)子集:VND=Bj,B1,B2.BrSBj,ZiBj這些子集滿足：B Bj jBBk k=, jk=, jkBBj j = V= VN N 定義導(dǎo)出文法GD=(VND,VT,PD,Bs)是由規(guī)范文法Gc產(chǎn)生的文法，導(dǎo)出規(guī)則如下：VT相同VND=(Bs,B1,B2,Br)Bs為起始符，Bs=SPD定義:a.若ZZ在Pc中，則PD中有Bi

17、Bj,ZaBi,ZBjb.若Za在Pc中，則PD中有Bia,ZaBirj=s例：S+=(01，100，111，0010)規(guī)范文法Gc=(VNC,VT,Pc,S)VNC=S,Z1,Z2,Z8對(duì)VNC分割為：VND=(S),(Z1,Z6,Z7),(Z2,Z3,Z8),(Z4,Z5)=Bs,B1,B2,B3對(duì)于S0Z1SBS,Z1B1PD中有BS0B1對(duì)于Z11Z1B1PD中有B11同理：BS1B2，B20B2,B20,BS1B3，B31B3，B31BS0B1，B10B1，B11B2，B20把相同的產(chǎn)生式合并后有：Pc：BS0B1，BS1B2，BS1Bs,B11，B10B1，B11B2，B20B2,

18、B20,B31B3，B31狀態(tài)圖導(dǎo)出文法等效規(guī)范文法L(GC)=L(GD)這種方法由于分割方式不同會(huì)導(dǎo)出不同的文法而分割方式又無(wú)系統(tǒng)理論作指導(dǎo)，而靠經(jīng)驗(yàn)和試探。B5B3B2B1T0011111100三.形式微商文法形式微商定義：集合A對(duì)于符號(hào)aVT的形式微商是：DaA=X|axA若a=(空串)，則DA=A例：A=S+=01,100,111,0010則D0A=D0S+=1，010D1A=D1S+=00，11擴(kuò)展：二次微商Da1a2A=Da2(Da1A)n次微商：Da1a2an1anA=Dan(Da1a2an1)A對(duì)上例：D00S+=D0(D0S+)=D0(1.010)=(10)D11S+=(1)

19、D000S+=,D100S+=已知正取樣S+=x1,x2,.xnT形式微商文法GCD=(VN,VT,P,S),定義如下：VT=（S中不同的符號(hào)）VN=U=(U1,U2,UP)其中Ui(i=1,2p)是S+的形式微商，且令U1=DS起始符，S=U1=DS令Ui,UjVNP:當(dāng)DaUi=Uj,則UiaUj當(dāng)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

20、)=D1U3=U31D111S-=D1(D11S)=D1U3=U31形式微商文法為(相同產(chǎn)生式合并)：GCD=(VN,VT,P,S)VT=（0,1）VN=（S,U2,U3）P:S1U2,U21U3,U20U3,U31狀態(tài)圖為：SU2U3T110.1四.k-尾文法：對(duì)形式微商文法進(jìn)行長(zhǎng)度限制，并對(duì)等價(jià)狀態(tài)進(jìn)行合并k尾定義：(U,A,k)=X|XDaA|X|k形式微商文法中兩個(gè)狀態(tài)間的等效性的充要條件為：(XiS+k)= g(XjS+k)-k尾相等利用k尾等效把形式微商文法中的等效狀態(tài)合并，導(dǎo)出k尾文法。例：S+=01,1001先求形式微商文法DS+=S+=01,1001=U1=SD0S+=1=U

21、2S0U2D01S+=D1(D0S+)=D1U2= U21D1S+=001=U3S1U3D10S-=01=D0U3=U4U30U4D100S+=1=D0U4=U5U40U5D1001S+=U51求k尾等效狀態(tài)：|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等效狀態(tài)為k=4,k=3,k=2,k=1(U2,U5)(U1,U4)(U1,U4)(U1,U3,U4)(U2,U5)(U2,U5)(U2,U5,)合并狀態(tài)，導(dǎo)出k尾文法k=4

22、時(shí)S0U2,U11,S1U3,U30U4,U40U2k=3,2時(shí)S0U2,U21,S1U3,U30Sk=1時(shí)S0U2,U21,S1S,S0S狀態(tài)圖討論：推斷k尾文法時(shí)，k尾的選擇很重要，k小時(shí)文法簡(jiǎn)單，但循環(huán)產(chǎn)生式增多，這樣就可以導(dǎo)出更多的S+以外的子串來(lái)，有時(shí)這是不允許的。1SSSTTT111U2U3U4U2U3U20000000,11K=2,3K=1K=4三.樹(shù)文法推斷一棵樹(shù)可以看成一個(gè)多枝的鏈。因此前邊講的鏈（串）文法的推斷方法可以用在樹(shù)文法的推斷上。任何一個(gè)數(shù)字化的網(wǎng)絡(luò)模板都可以用樹(shù)結(jié)構(gòu)來(lái)表示如下：由下面的四種方式表示成樹(shù)枝全從根開(kāi)始的樹(shù)。X11X12.X1nX21X22.X2n.Xn

23、1Xn2.Xnn樹(shù)狀的數(shù)字化網(wǎng)絡(luò)模式S 根樹(shù)干N個(gè)枝S樹(shù)干M個(gè)枝.樹(shù)文法先選一個(gè)合適的樹(shù)干，由樹(shù)干推出一個(gè)鏈文法再推各樹(shù)枝的文法把樹(shù)干文法與樹(shù)枝文法合并樹(shù)干樹(shù)干樹(shù)枝樹(shù)枝根SS例：已知數(shù)字化模式L1L2L3L4L5L6000111000111110000110000111100111000110000100000R1R2R3R4R5R6樹(shù)干根S先由樹(shù)干推出樹(shù)干文法GAP:S A1A1 $ A2|R1L1A2 $ A3|R2L2A3 $ A4|R3L3A4 $ A5|R4L4A5 $ A6|R5L5A6 $|R6L6上面推出樹(shù)干文法GA,再推出樹(shù)枝文法GL1, GL2. GL6,GR1, GR2,

24、. GR6再將樹(shù)干文法與樹(shù)枝文法合并GT= GAGLGR7-3句法分析一.用句法分析作模式識(shí)別設(shè)給定訓(xùn)練樣本為M類即：1, 2, M每類有N個(gè)樣本，如1的訓(xùn)練樣本為：S=(X1,X2,XN)T由這些樣本可以推斷出1類的文法G1,同樣方法可推斷出2類的文法G2,.M類的文法GM.對(duì)待識(shí)別句子X(jué)進(jìn)行句法分析，若X屬于由文法Gi構(gòu)成的語(yǔ)言L(Gi)，則xi類。框圖如下：XLG1G1XLG2G2XLGMGMx判決Xi句法分析過(guò)程識(shí)別結(jié)果待識(shí)別句子二句法分析的主要方法1參考匹配法：2狀態(tài)圖法：適用于有限狀態(tài)文法例：G=(VN,VT,P,S)VT=（0,1）VN=（S,A,B,C）P:S1A,S0B,S1

25、C,A0A,A0 B0,C0C,C0,C1BX樣本鏈碼X1XLG2xX樣本鏈碼X2X樣本鏈碼XN判決XiXXiSCBAT1100010由狀態(tài)圖可以知道此文法可以識(shí)別的句子X(jué)1=10n+1 , X2=00 , X3=10n10, X4=10n+1未知句子：由狀態(tài)圖可知x1=10010(可以識(shí)別)x2=10110(不可以識(shí)別)00狀態(tài)圖2、填充樹(shù)圖法(適用于上下文無(wú)關(guān)文法)：當(dāng)給定某待識(shí)別鏈X及相應(yīng)的文法G時(shí)，我們建立一個(gè)以X為底，S為頂?shù)娜切?，按文法G的產(chǎn)生式來(lái)填充此三角形，使之成為一個(gè)分折樹(shù)。若填充成功表明 否則填充樹(shù)有二種方法由頂向底剖析由底向頂剖析填充樹(shù)圖法在填充三角形時(shí)應(yīng)遵守三條原則：

26、首位考察：首先考慮選用某個(gè)產(chǎn)生式后能導(dǎo)出X的 第一個(gè)字符用某產(chǎn)生式后，不能出現(xiàn)X中不包含的終止符用某產(chǎn)生式后，不能導(dǎo)致符號(hào)串變長(zhǎng)(變短)(GLX )(GLX SX由頂向底(由上而下)剖析例：G=(VN,VT,P,S)VT=（0,1） VN=（S,A,B）P: S1 SB1 SB B1A BB1A A0A A0設(shè)：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 設(shè)：X=afbgc用I

27、a 用TI用Ib用Ic用TIafbgcIafbgcITafbgcITIafbgcITIIafbgcITIITafbgcITIITTafbgcITIITTSafbgcITIITTS用TIgT用ST用STfSSX=afbgcL(G)三、楊格(Younger)法Younger法是個(gè)較前述各方法更系統(tǒng)的方法，適用于任何相應(yīng)于2型文法類別的識(shí)別。下面結(jié)合一例說(shuō)明此方法。設(shè)有一代表類別的文法G=(VN,VT,P,S)其中VT=（0,1,2） VN=（S,B）P: SSBS BBB BBS S2 B0 B1現(xiàn)在要用Younger法來(lái)識(shí)別X=202102是否G. 首先將上述文法化為Chomsky標(biāo)準(zhǔn)形式。此形

28、式文法的代換式只有兩種形式，即 非終止符非終止符非終止符（雙非終止符形式） 非終止符終止符（終止符形式）將式上所示文法中第1條改為SSA ，ABS兩條（A為人為增加的非終止符），使整個(gè)文法成為： SSA ABS BBB BBS S2 B0 B1 而令VT=（0,1,2） VN=（S,A,B）便完成了Chomsky形式的轉(zhuǎn)化。Younger法將對(duì)Chomsky形式文法進(jìn)行分析。 待識(shí)別符號(hào)串的任一“子串”都可用i,j兩個(gè)整數(shù)來(lái)指明：所謂子串即把一符號(hào)串任一截取一段，這段符號(hào)串（包括單個(gè)符號(hào)）就叫原來(lái)符號(hào)的子串。譬如符號(hào)串202102的子串就有2，0，2，1，0，2（個(gè)數(shù)為1的子串）；20，02，

29、21，10，02（個(gè)數(shù)為2的子串）；202，021，210，102（個(gè)數(shù)為3的子串）；2021，0210，2102（個(gè)數(shù)為4的子串）；20210，02102（個(gè)數(shù)為5的子串）和202102（個(gè)數(shù)為6的子串即原符號(hào)串）。這21個(gè)符號(hào)串都可由正整數(shù)i,j表示。i代表子串中符號(hào)的個(gè)數(shù)（即子串長(zhǎng)度），而j表示這子串的首位在原符號(hào)串中占第幾位。如上面所舉的第1子串“2”，即為i=1、j=1的子串，第13個(gè)子串021即是i=3、j=2的子串?？梢?jiàn)，任一子串都可用i,j二數(shù)來(lái)指明。 識(shí)別表的建立，關(guān)鍵問(wèn)題是根據(jù)給出的待識(shí)別串X,建立一識(shí)別表。對(duì)于202102,根據(jù)所給出的文法算得的識(shí)別表如下： i123j1

30、23456123451234所有子串所有子串2021022002211002202021210102所所有有VNS A B 4561231212021021021022021002102202102 表中每一位置由三個(gè)符號(hào)表示。頭二個(gè)即i和j，而第三個(gè)是非終止符(現(xiàn)為S,A,B,見(jiàn)表中第一列).。i1欄中第2列(j=2)與B行相交的位置即為(1,2,B),余類推。表中(1,2,B)位置上有，代表對(duì)于所給文法，B可導(dǎo)出i=1,j=2的子串，即“0”。反之，若這位置上為 ，則說(shuō)明B不能導(dǎo)生子串“0”。再舉一例，第2欄中第2列、A行位置應(yīng)該用（2,2,A）表示，此位置上有，代表對(duì)于所給文法，B可導(dǎo)出

31、I=2,j=2的子串，即“02”（見(jiàn)表）。（）經(jīng)分析可知，能容易地根據(jù)給出的符號(hào)串(202102),在i=1欄的各位置上打或 ，又根據(jù)此欄結(jié)果，由一遞推公式將i=2欄各位置打上或 。如此遞推下去便可將表填滿，識(shí)別表也就建成。在識(shí)別時(shí)只需檢查最后一欄(現(xiàn)為i=6欄)第一列第S行位置即(6,1,S)上是還是 。若是，表示S可導(dǎo)生子串202102，故判202102符合給出的文法。反之，即判不符合此文法。020SBSA建立識(shí)別表的遞推規(guī)則遞推規(guī)則：將要決定或 的位置表為(i,j,k)通用形式。K代表非終止符。又將r(i,j,K)稱為(i,j,k)位置的識(shí)別值。此值為0或1，分別表示(i,j,k)位置上

32、是或 。計(jì)算r(i,j,K)(也即決定或 )的步驟是：(i)算出其中K1,K2代表KK1K2.例如：ABS,K=A, K1=B, K2=S.),1,1(),1(),2,2(),2(),1,1(),1(212121KijrKjirKjirKjrKjirKjr（1）(ii) 如果(i,j,k)左側(cè)是K的代換式不只一個(gè)，譬如K是B時(shí)，即有BBB、BBS兩個(gè)。這時(shí)則把B、B叫做K1、K2，根據(jù)它計(jì)算式(1)中各值；此外，還需將B、S叫做K1、K2，再按下面式算出：對(duì)于所有i,j,k（包括題中各個(gè)非終止符），算出式(2)中的各值。只要其中之一值為1，便在相應(yīng)當(dāng)位置上打，否則打。如此便可填滿整個(gè)識(shí)別表若左

33、側(cè)為K的代換式有三個(gè)，可按上述原則，再增加計(jì)算將(1)式中K1、K2改為K1、K2后的各值，余類推。),1,1(),1(),2,2(),2(),1,1(),1(212121KijrKjirKjirKjrKjirKjr現(xiàn)作為例子用遞推規(guī)則考察(2,2,A)中的或 。由于左側(cè)為A的代換式只有ABS一個(gè)，故此時(shí)對(duì)于(1)式只需計(jì)算r(1, 2, B) r(1, 3, S)=1 1=1,即(2,2,A)應(yīng)打。此結(jié)果與前面分析得到的相符。根據(jù)上述遞推規(guī)則和給定的文法，容易編制計(jì)算機(jī)程序。當(dāng)待識(shí)別串X進(jìn)入時(shí)，按此算出識(shí)別表，并檢查表中最后一列S位置上是還是；若為，便判屬于給定文法相應(yīng)的類別，否則判為不屬于

34、此類別。作業(yè)：對(duì)作業(yè)：對(duì)Younger法的例題編程上機(jī)，打出識(shí)別表。法的例題編程上機(jī)，打出識(shí)別表。四四.CYK(Cocke-Younger-Kasami).CYK(Cocke-Younger-Kasami)剖析剖析( (列表法列表法) )條件：適用上下文無(wú)關(guān)文法 產(chǎn)生式應(yīng)符合Chomsky范式已知輸入串X=a1a2.an構(gòu)造三角形剖析表步驟如下：令j=1,按從i=1到i=n次序，求ti1.把X分解為長(zhǎng)度為1的子串，對(duì)子串a(chǎn)i,若p中有Aai,把A填入ti1中令j=2,按從i=1到i=n-1次序，求ti2，即第二行。把X分解為長(zhǎng)度為2的子串，對(duì)子串a(chǎn)iai+1,若p中有ABC,且有Bai, Ca

35、i+1則把A填入ti2中對(duì)于j2,1in,已求出tij-1,現(xiàn)求tij對(duì)于1kj中的任一k,當(dāng)P中有ABC且B在tik中.C在ti+k,j-k中時(shí)，把A填入tij中重復(fù)直至完成此表，或整行都是空(拒識(shí))當(dāng)且僅當(dāng)S在tin中，XL(G)，即由G可導(dǎo)出X分析一個(gè)長(zhǎng)度為n的串，所用的存儲(chǔ)量正比于n2,運(yùn)算次數(shù)正比于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 所有產(chǎn)生式符合Chomsky范式令j=1,計(jì)算ti1，1i4i=1,a1=a, P中有Aa 有

36、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,計(jì)算ti2，1i3對(duì)于a1a2=aa, 不能產(chǎn)生aa 有t21=對(duì)于a2a3=ab, SAB, Aa, Bb 有t22=(s)對(duì)于a3a4=bb, P中產(chǎn)生式不能產(chǎn)生bb 有t32=()1234ij4321AABB S 第二次迭代，令j=3,計(jì)算ti3，1i2對(duì)于a1a2a3=aab, 不能產(chǎn)生aab 有t13=對(duì)于a2a3a4=abb, CSB, Sab, Bb 有t23=(C) 第三次迭代，令j=4,計(jì)算ti4，

37、對(duì)于a1a2a3a4=aabb, SAC, Aa, Cabb 有t14=(S) t14=S X=aabb在L(G)中， 此串被識(shí)別。此算法實(shí)際上是一個(gè)由底向頂剖析算法。4321AABB S1234iSC剖析表aabbAABBSSC導(dǎo)出樹(shù)+ 作業(yè)：對(duì)CYK算法的例題上機(jī)編程，打出剖析表和導(dǎo)出樹(shù)。7-4 自動(dòng)機(jī)理論自動(dòng)機(jī)理論引言：x當(dāng)給出某類文法后，可根據(jù)它設(shè)計(jì)一種相應(yīng)的稱為自動(dòng)機(jī)的硬件模型。它由控制裝置、輸入帶和某些類型的存儲(chǔ)器組成，這種硬件模型是一種識(shí)別器稱自動(dòng)機(jī)。不同的自動(dòng)機(jī)可以識(shí)別不同的文法形成的語(yǔ)言。0型文法：圖靈機(jī)識(shí)別上下文有關(guān)型：線性約束自動(dòng)機(jī)上下文無(wú)關(guān)型：下推自動(dòng)機(jī)有限狀態(tài)型：有限

38、狀態(tài)自動(dòng)機(jī)識(shí)別器XLGG一、有限狀態(tài)自動(dòng)機(jī)有限狀態(tài)自動(dòng)機(jī)可以識(shí)別由有限狀態(tài)文法所構(gòu)成的語(yǔ)言1、基本定義：五元式M系統(tǒng)M=(,Q,q0,F)其中：輸入符號(hào)的有限集合Q：狀態(tài)的有限集合 ：狀態(tài)轉(zhuǎn)換函數(shù)是Q到Q的一種映射q0：初始狀態(tài) q0 Q F：終止?fàn)顟B(tài)集合2、有限自動(dòng)機(jī)的結(jié)構(gòu)轉(zhuǎn)換函數(shù)：(q,a)=p表示有限控制器處于q狀態(tài)，而輸入頭讀入符號(hào)a，則有限控制器轉(zhuǎn)換到下一狀態(tài)p。QF 輸入帶0110輸入頭有限狀態(tài)控制器Qq0 q1 .F3、自動(dòng)機(jī)識(shí)別輸入字符串的方式L(M)=x|(q0,x)在F中(q,x) 拒識(shí)，停機(jī)4、自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖:表示自動(dòng)機(jī)識(shí)別過(guò)程例：M=(,Q,q0,F) Q q0,

39、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可以識(shí)別 (q0,110101)= q0 例：已知自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換圖如下 x1=aab 可以識(shí)別 x2=abb 不可以識(shí)別可以識(shí)別的語(yǔ)言：L(G)=anbqB狀態(tài)，只有出沒(méi)有進(jìn)，為不可到達(dá)狀態(tài) q狀態(tài)，只有進(jìn)沒(méi)有出，為陷阱110110abbaabq0qAqBq a,b4、不確定的有限狀態(tài)自

40、動(dòng)機(jī)即：(q,a)= q1, q2, qk當(dāng)輸入a時(shí)，下一個(gè)狀態(tài)可 能為多個(gè)狀態(tài)之一。例：M=(,Q,q0,F) Q q0, q1, q2, q3 , q40,1F =q2， q4(q0,0)= q0, q3, (q0,1)= q0, q1(q1,0)= (在q1不會(huì)輸入0)(q1,1)= q2(q2,0)= q2, (q2,1)= q2,(q3,0)= q4, (q3,1)= (q4,0)= q4, (q4,1)= q4狀態(tài)轉(zhuǎn)換圖輸入字串：010110q0 q0 q0 q0 q0q3 q1 q3 q1 q2 q2Fq0q3q1000，10，1110，1q4q2010110 輸入字符串X=01

41、0110可以被自動(dòng)機(jī)識(shí)別，但在識(shí)別過(guò)程中，對(duì)不確定狀態(tài)需要進(jìn)行試探。5、構(gòu)造一個(gè)有限自動(dòng)機(jī)定理1：設(shè)G=(VN,VT,P,S)為有限狀態(tài)文法，一定存在一個(gè)有限狀態(tài)自動(dòng)機(jī)M=(,Q,S,F)使L(G)=L(M).已知有限狀態(tài)文法G=(VN,VT,P,S)由有限狀態(tài)文法構(gòu)造有限自動(dòng)機(jī)的步驟： 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對(duì)VT中所有的終止符a，都有(T,a)=,aVT例：有限狀態(tài)文法G=(VN,VT,P,S)VN=S,BVT=0,1P:S0B,B0B/1S/0

42、(B0B,B1S, B0)構(gòu)造有限自動(dòng)機(jī)M=(,Q,q0,F) VT 0,1Q VNT S,B，T q0 = S P中無(wú)S F=T S0B,(S,0)=B, B0B,(B,0)=B, B1S,(B,1)=S, B0,(B,0)=T, P中無(wú)S1x,xVN,(S,1)=對(duì)VT=0,1有(T,0)=(T,1)構(gòu)造的自動(dòng)機(jī)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)= 設(shè)x=00100，可以識(shí)別可以證明：L(M)=L(G)010TSB06.由有限自動(dòng)機(jī)M構(gòu)造有限狀態(tài)文法定理2：已知

43、有限自動(dòng)機(jī)M，則有一個(gè)有限狀態(tài)文法G，使L(G)=L(M)。已知M=(,Q,q0,F)，構(gòu)造G=(VN,VT,P,S)的步驟如下：VT VNQ Sq0 對(duì)于(B,a)=C,若B,CQ, a,則P中有BaC. 若CF,則還有產(chǎn)生式Ba例：已知有限自動(dòng)機(jī)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òu)造G=(VN,VT,P,S)如下：VT 0,1VN= Q = q0, q1, q2S = q0 (q0,0)= q2,有q00q2,q2F有q00

44、(q0,1)= q1,有q01q1, (q1,0)= q2,有q10q2,q2F有q10 (q1,1)= q0,有q11q0, (q2,0)= q2,有q20q2,q2F有q20 (q2,1)= q1,有q21q1,有限狀態(tài)文法為：G=(VN,VT,P,S)VT0,1VN= q0, q1, q2S = q0P:q00q2, q01q1, q00 q10q2 , q11q0 ,q10 q20q2 , q21q1, q20 狀態(tài)圖輸入x1100由自動(dòng)機(jī)M：(q0,1100)q2，q2F1100可以接受由有限文法G： q01q111q0110q21100L(M)=L(G)q0q1q211111100

45、0000000q1q0q2 T有限自動(dòng)機(jī)有限狀態(tài)文法二.下推自動(dòng)機(jī)（PDA）可以識(shí)別由上下文無(wú)關(guān)文法構(gòu)成的語(yǔ)言下推自動(dòng)機(jī)結(jié)構(gòu)：七元式MP=(,Q,q0, Z0 ,F, )其中,Q,q0,F同有限自動(dòng)機(jī):轉(zhuǎn)換函數(shù) :推下符號(hào)的有限集合 Z0:推下存貯器的起始符例如：(qi,b,Z)=(qj,)qi：目前狀態(tài)，b：輸入符號(hào)，Z：下推存儲(chǔ)器的內(nèi)容qj：下一狀態(tài)，：下推存儲(chǔ)器的下一狀輸入帶只讀頭有限狀態(tài)器Q讀寫頭下推存儲(chǔ)器（堆棧型）bBZ0識(shí)別輸入字串X的方式終止?fàn)顟B(tài)方式空堆棧識(shí)別方式例：不確定的下推自動(dòng)機(jī)MP=(q0),(a,b,c,d),(S,A,B,C,D), q0, S, )即：Q= (q0)

46、,= (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),(),(,|)(00*FqrqzxqXXMLffP),(),(,|)(00*qzxqXXMLP輸入xcaadbb(q0,S)(q0,DAB)(q0,AB)(q0,CBB)(q0,BB)(q0,B) (q0,C)(q0,ABB)(q0,)堆棧變空，X=caadbb可以接受，這種不確定的下推自動(dòng)機(jī)在識(shí)別過(guò)程中需試探進(jìn)行。caadbda不通不

47、通b例：確定自動(dòng)機(jī)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由上、下文無(wú)關(guān)文法G=(VN,VT,P,S)構(gòu)造一個(gè)下推自動(dòng)機(jī)MP=(,Q,q0, Z0 ,F, )步驟如下： VT VNVTZ0 = SQ=q0F=(用堆棧變空來(lái)識(shí)別)由p構(gòu)造函

48、數(shù)：若A 在P中，則有(q0,A)=(q0,)：對(duì)VT中所有終止符a，有(q0,a,a)=(q0,)例：G=(s,A),(a,b,c,d),p,SP:ScA, AaAb, Ad構(gòu)造MP=(,Q,q0, Z0 ,F, )Q=q0 VTa,b,c,dZ0 = S VNVT=(S,A,a,b,c,d)F=(由堆棧變空來(lái)識(shí)別) 在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)由規(guī)則對(duì)VT：(q0,a,a)=(q0,)，(q0,b,b)=(q0,)(q

49、0,c,c)=(q0,)，(q0,d,d)=(q0,)對(duì)x=caadbb(q0,S) 無(wú)，可以先輸入空格。(q0,S) (q0,CA) (q0,A)(q0,aAb) (q0,Ab) (q0,aAbb) (q0,Abb) (q0,dbb) (q0,bb) (q0,b) (q0,)堆?？杖粑姆ǚ螩reibadh范式，產(chǎn)生式形式為：Aa ,AVN，aVT，上面規(guī)則, 合成一個(gè)規(guī)則，若A ,則有(q0,a,A)=(q0, )C a)(*包括VN caadbb例：Greibach范式文法G=(S,A,B,a,b,c,d,P,S)P:ScA, AaAB, Ad, Bb可以構(gòu)造一個(gè)下推自動(dòng)機(jī)MP=(,Q,

50、 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,)形式，根據(jù)上面的規(guī)則這些產(chǎn)生式都符合aA輸入X=caadbb(q0,S) (q0,A)(q0,AB)(q0,ABB)(q0,BB) (q0,B) (q0,)只用六步就完成，而上例用九步。說(shuō)明符合Greibach范式的文法產(chǎn)生的語(yǔ)言容易被下推自動(dòng)機(jī)識(shí)別。caadbb 三、圖靈機(jī)：可以識(shí)別0型文法所產(chǎn)生的語(yǔ)言

51、1、結(jié)構(gòu)2、定義：一個(gè)圖靈機(jī)T是一個(gè)六元式T=(, Q, ,q0, F)其中：Q：狀態(tài)集合 B, B空 = - B, q0起始狀態(tài)，q0 QF:終止?fàn)顟B(tài)控制裝置讀寫頭輸入帶圖靈機(jī)是最復(fù)雜的自動(dòng)機(jī)。它的一個(gè)構(gòu)型用三元式（q,i）表示qQ, (- B)*映射的使用(q,Ai)=(P,X,R)在Ai處插入X后右移(q,Ai)=(P,X,L)在Ai處插入X后左移3、圖靈機(jī)T所接受的語(yǔ)言,),(*| ) 1 ,(|)(*0*FqiqTXqXXTL例： T=(, Q, ,q0, F)(0,1), Q=(q0,q1, q5),=(0,1,B,X,Y),F=(q5)(q0,0)= (q1,x,R) (q1,0

52、) = (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,則圖靈機(jī)運(yùn)行如下：(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)(q

53、2,xxYY,2)(q3,xxYY,3)(q3,xxYY,4)(q3,xxYY,5)(q5,xxYYY,6)q5F X0011被接受 7-5 誤差校正句法分析一、解決噪聲干擾的方法推斷文法時(shí)，考慮噪聲干擾的樣本在預(yù)處理中，除掉噪聲，平滑處理用隨機(jī)文法,采用概率的概念，給句子的出現(xiàn)加上概率的分布用轉(zhuǎn)換文法，把有噪聲句子轉(zhuǎn)換為無(wú)噪聲句子用誤差校正剖析句法集群法二、隨機(jī)文法定義：四元式GS=(VN,VT,PS,S)PS形式：iij j=1,2.n i=1,2.k 其中i,ij(VNVT)*Pij: i產(chǎn)生ij的可能性為Pij，稱為產(chǎn)生概率。產(chǎn)生概率Pij滿足： 0Pij1以及出現(xiàn)概率P(X)滿足：

54、等于產(chǎn)生概率的乘積。用GS產(chǎn)生的語(yǔ)言稱為隨機(jī)語(yǔ)言。 L(Gs)=(x,P(x)|XVT*,SX,j=1,2.k,且 11njijppxPiki 1)(pxPjkj 1)(pijpj假如某隨機(jī)文法為：Gs=(VN,VT,P,S)VN=A1,A2,.AkVT=a1,a2,.am，S=A1 PS形式：其中11011mllikjmllijppAapAAapAAapAAapAkmiiliiimiklijii.,22112111apAapAapAmiliimilii0010.1例：有隨機(jī)文法Gs=(VN,VT,P,S)VN=S,A,BVT=0,1 PS形式：S1A B0 B1S A0BA1 導(dǎo)出式S1A1

55、0B100, P(X)=P(100)=10.80.3=0.24S1A11, P(X)=P(11)=10.2=0.2由Gs產(chǎn)生的語(yǔ)言L(Gs)產(chǎn)生的鏈XP(X)出現(xiàn)的概率110.21000.24 (101)n11 0.2(0.70.8)n (101)n100 0.24(0.70.8)n10.30.80.2BSA111P=0.7P=0.8P=0.2P=0.3000.7T用隨機(jī)文法作識(shí)別 用大量的樣本去推斷隨機(jī)文法，每個(gè)隨機(jī)文法代表一類 檢查待識(shí)別的樣本符合哪一個(gè)隨機(jī)文法，就把它歸于該 隨機(jī)文法所代表的一類 若待識(shí)別的樣本符合二個(gè)以上的隨機(jī)文法 再求待識(shí)別樣本對(duì)每一類的出現(xiàn)概率，把待識(shí)別樣本歸 于出現(xiàn)概率最大的一類。例：關(guān)于“7”，“1”的手寫體數(shù)字 產(chǎn)生“1”的隨機(jī)文法G1 = (VN,VT, P, S) VN=S, A, B, C, D, E, F, H, I VT=0,1, 3, 4, 5, 6, 7 012347005555055550055565“1”基元P形式：S0A A0BB5C C5D D5E D5E5 A5F F5H H5I I5P1=1