模式識(shí)別講義第二章

模式識(shí)別講義第二章第1頁(yè)，共44頁(yè)，2023年，2月20日，星期五短語(yǔ)結(jié)構(gòu)文法文法可以形式地定義為一個(gè)四元組G=(VN,VT,P,S)，其中：VN是非終結(jié)符或變量的有窮集合，VT是終結(jié)符或常數(shù)的有窮集合，P是產(chǎn)生式或重寫規(guī)則的有窮集合，S在VN中，是起始符。VN∩VT=Φ、V是集合VN∪VT

，P由形式為α→β的重寫規(guī)則組成，其中α是在V*VNV*中，β是在V*中第2頁(yè)，共44頁(yè)，2023年，2月20日，星期五文法類型無(wú)約束文法：一個(gè)文法如果它的產(chǎn)生式的形式不受任何限制（除了串重寫規(guī)則是有窮集合這個(gè)一般規(guī)定以外）則它就是無(wú)約束的。

上下文有關(guān)文法上下文無(wú)關(guān)文法正則文法：產(chǎn)生式的形式是A→aB或A→a，其中A和B在N中，以及a在Σ中。第3頁(yè)，共44頁(yè)，2023年，2月20日，星期五上下文有關(guān)文法上下文有關(guān)文法的產(chǎn)生式的形式是θAσ→θρσ，其中θ和σ在V*中，ρ在V*中，和A在VN中。術(shù)語(yǔ)“上下文有關(guān)”指的是僅當(dāng)非終結(jié)符A出現(xiàn)在子串θ和σ的上下文之中時(shí)，才能被重寫為ρ這個(gè)事實(shí)。與其等價(jià)的定義是：對(duì)任何產(chǎn)生式α→β，在β中的符號(hào)的總數(shù)（非終結(jié)符和終結(jié)符）必須不少于在α中的總數(shù)，也就是說(shuō)，|α|≤|β|。

第4頁(yè)，共44頁(yè)，2023年，2月20日，星期五上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法的產(chǎn)生式的形式是A→α，其中A在VN中，α在V+中。術(shù)語(yǔ)“上下文無(wú)關(guān)”是從這樣的一個(gè)事實(shí)產(chǎn)生的：非終結(jié)符A可被重寫為串α，而與A出現(xiàn)在什么樣的上下文中無(wú)關(guān)。

第5頁(yè)，共44頁(yè)，2023年，2月20日，星期五有限自動(dòng)機(jī)一個(gè)（不確定的）有限自動(dòng)機(jī)是一個(gè)五元組A=（Σ，Q，δ，q0，F(xiàn)）規(guī)定的系統(tǒng)。其中

Q是狀態(tài)的有窮集；

Σ是有窮輸入字母表；

δ是從Q×Σ到2Q的映射，是Q的全體子集的集合

q0在Q中，是起始態(tài)；

F是終止或接受態(tài)，是Q的一個(gè)子集。第6頁(yè)，共44頁(yè)，2023年，2月20日，星期五有限自動(dòng)機(jī)的一般表示

起始態(tài)總是q0，由∑+來(lái)的輸入串x放在帶上，從帶的最左邊單元開(kāi)始一個(gè)符號(hào)挨者一個(gè)符號(hào)對(duì)帶進(jìn)行掃描。從q0開(kāi)始，掃描整個(gè)x串并遵循一個(gè)狀態(tài)序列，最后停在F中的一個(gè)狀態(tài)上，我們就說(shuō)串x被接受了或者說(shuō)被識(shí)別了（帶運(yùn)動(dòng)方向）輸入帶只讀頭有窮狀態(tài)集Q有限自動(dòng)機(jī)的一般表示第7頁(yè)，共44頁(yè)，2023年，2月20日，星期五有限自動(dòng)機(jī)舉例有限自動(dòng)機(jī)A=（Σ，Q，δ，q0，F(xiàn)），其中：Q={q0，q1}Σ={a，b}F={q1}，而δ定義為：

δ（q0，a）={q0}，δ（q0，b）={q1}，δ（q1，a）=δ（q1，b）=φ。

模式基元L電感C電容

a終結(jié)符R電阻

b1.模式基元和終結(jié)符q0bq1a2.有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移圖第8頁(yè)，共44頁(yè)，2023年，2月20日，星期五有限自動(dòng)機(jī)的確定化

不完全規(guī)定的自動(dòng)機(jī)A=({a,b},{q0,q1},δ,q0,{q1}),構(gòu)造確定的自動(dòng)機(jī)A’=(∑’,Q’,δ’,q0’,F’)

其中：Q’=2Q。起始態(tài)q0’={q0}，終止態(tài)集為F’={q’|q’在2Q

中，q’至少包含F(xiàn)的一個(gè)狀態(tài)}。δ’:δ’(q’，a)={p|p在Q中，對(duì)于子集q’中的某狀態(tài)q來(lái)說(shuō)p在δ(q，a)之中}。第9頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題已知有限自動(dòng)機(jī)如圖：請(qǐng)將其確定化。q0bq1a有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移圖第10頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題解答qAqBq0qφbb確定的有限自動(dòng)機(jī)aababa第11頁(yè)，共44頁(yè)，2023年，2月20日，星期五正則文法→有限自動(dòng)機(jī)正則文法G=(N,∑,P,，X0)，求對(duì)應(yīng)有限自動(dòng)機(jī)Af=(∑,Q,δ,q0,F)的方法如下：假設(shè)非終結(jié)符N={X0,X1,X2,……,Xn}組成，X0是起始符，那么，狀態(tài)集Q={q0,q1…,qn,qn+1}組成。qi和Xi相對(duì)應(yīng)，0≤i≤n，qn+1是個(gè)符加態(tài)。集合F就是{qn+1}。而輸入符號(hào)集和G中的終結(jié)符集相同。δ映射規(guī)則定義，即:對(duì)于每個(gè)i和j，0≤i≤n，0≤j≤n，如果Xi→aXj在P中，則δ(qi，a)包括qj；如果Xi→a在P中，則δ(qi，a)包括qn+1。第12頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題給定正則文法G=({S},{a,b},P,S)，其產(chǎn)生式為S→aSS→b。構(gòu)造一個(gè)能識(shí)別L(G)的有限自動(dòng)機(jī)Af=(∑,Q,δ,q0,F)

第13頁(yè)，共44頁(yè)，2023年，2月20日，星期五有限自動(dòng)機(jī)→正則文法一個(gè)有限自動(dòng)機(jī)Af=(Q,∑,δ,q0,F)，則我們可以規(guī)定出一個(gè)正則文法G=(N,∑,P,X0)，為此，令N和狀態(tài)集Q對(duì)應(yīng)，起始非終結(jié)符X0和q0對(duì)應(yīng)，而G的產(chǎn)生式可用下述方法得到：1、如果qj在δ(qi,a)中，就有產(chǎn)生式Xi→aXj2、如果F中的一個(gè)狀態(tài)在δ(qi,a)內(nèi)，就有產(chǎn)生式Xi→a第14頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題已給有限自動(dòng)機(jī)Af=({0,1},{q0,q1,q2},δ,q0,{q2})，其狀態(tài)轉(zhuǎn)移圖如圖4.4所示。狀態(tài)映射為：δ(q0,0)={q2}，

δ(q0,1)={q1}，

δ(q1,0)={q2}，

δ(q1,1)={q0}，

δ(q2,0)={q2}，

δ(q2,1)={q1}。

求其正則文法。q0q1110010圖4.4有限自動(dòng)機(jī)q2第15頁(yè)，共44頁(yè)，2023年，2月20日，星期五等價(jià)的上下文無(wú)關(guān)文法

如果L(G1)=L(G2)

那么，文法G1和G2是等價(jià)的。

等價(jià)變換：

1、無(wú)循環(huán)的文法

2、沒(méi)有無(wú)用符號(hào)或產(chǎn)生式的文法

3、具有標(biāo)準(zhǔn)形產(chǎn)生式的文法

第16頁(yè)，共44頁(yè)，2023年，2月20日，星期五一個(gè)循環(huán)是一個(gè)形式為的導(dǎo)出，其中A是在N中。如果對(duì)任何非終結(jié)符A都不存在

的導(dǎo)出式，則這個(gè)文法就是無(wú)循環(huán)的。當(dāng)且僅當(dāng)存在以下這樣一組只包含單個(gè)非終結(jié)符的產(chǎn)生式：A→B1，B1→B2，…，Bn-1→Bn，Bn→A，n>0時(shí)，才能出現(xiàn)循環(huán)。這樣，如果把所有形式為A→B的產(chǎn)生式都去掉，循環(huán)就會(huì)被刪除。

無(wú)循環(huán)的文法

A＝＞A+A＝＞A+第17頁(yè)，共44頁(yè)，2023年，2月20日，星期五無(wú)循環(huán)的文法變換（1）對(duì)某個(gè)具體的非終結(jié)符A，按下述遞歸規(guī)則定義非終結(jié)符集K（A）：(i)K0(A)={A}(ii)K1(A)=K0(A)∪{B|A→B是P中的一個(gè)產(chǎn)生式}(iii)Ki+1(A)=Ki(A)∪{C|對(duì)Ki(A)中的某個(gè)B來(lái)說(shuō)，B→C是在P中的一個(gè)產(chǎn)生式}，i=1,2,3…從Ki(A)構(gòu)成Ki+1(A)，如果不增加任何新的非終結(jié)符，我們有K(A)=Ki(A)=Ki+1(A)第18頁(yè)，共44頁(yè)，2023年，2月20日，星期五在對(duì)N中的每個(gè)非終結(jié)符A確定了集合K(A)以后，我們用定義等價(jià)文法G2=(N,∑,p,S)的方法刪除所有的形式為A→B的產(chǎn)生式（從而刪除了任何循環(huán)）。可根據(jù)下述要求來(lái)確定等價(jià)文法G2的產(chǎn)生式：對(duì)非終結(jié)符A和B來(lái)說(shuō)，如果B是在K(A)中，并且在P中存在一個(gè)產(chǎn)生式B→β，其中β不是單個(gè)的非終結(jié)符，那么就把產(chǎn)生式A→β放在p中。

無(wú)循環(huán)的文法變換（2）^^第19頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題已知：文法G1=({S，A，B}，{a，b}，P，S)，有產(chǎn)生式{S→aSA，S→A，A→BAb，A→B，B→aS，B→b}

求其等價(jià)文法G2，使其不含循環(huán)。第20頁(yè)，共44頁(yè)，2023年，2月20日，星期五非終結(jié)符A是無(wú)用的條件是：（i）不存在滿足導(dǎo)出式的終結(jié)符串x；或

（ii）不存在滿足導(dǎo)出式的句形αAβ。如果A是無(wú)用的，那么可以把所有的形式為A→θ(對(duì)任何的θ)的產(chǎn)生式，或所有形式為B→ωAσ（對(duì)任何的非結(jié)符B）的產(chǎn)生式刪除，而不影響L(G1)。沒(méi)有無(wú)用符號(hào)或產(chǎn)生式的文法

A=>xG1*S=>aAβG1*第21頁(yè)，共44頁(yè)，2023年，2月20日，星期五集合J(G1)包括，且僅包括那些至少能推導(dǎo)出一個(gè)終結(jié)符串的非終結(jié)符 用以下的方法由Ji(G1)構(gòu)成Ji+1(G1)，0≤i，（i）J0(G1)=φ（ii）Ji+1(G1)=Ji(G1)∪{A|存在有一個(gè)產(chǎn)生式A→α，α在(Ji(G1)∪∑)*中}，i=0,1,2,…當(dāng)Ji+1(G1)=Ji(G1)時(shí)，上述構(gòu)成過(guò)程結(jié)束。G1等價(jià)的文法是G2=(N，∑，P，S)，其中，N=J(G1)，和P只包括那些來(lái)自P，并和N中的元素有關(guān)的那些產(chǎn)生式

消除不能導(dǎo)出終結(jié)符的A^^^^^第22頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題已知文法G1=({S，A，B}，{a，b}，P，S)，具有產(chǎn)生式{S→aBA，S→bA，A→aA，A→b，B→aAB}

消除G1中導(dǎo)不出終結(jié)符的無(wú)用的非終結(jié)符，求其等價(jià)文法G2。第23頁(yè)，共44頁(yè)，2023年，2月20日，星期五消除不可到達(dá)的A從起始符S出發(fā)可達(dá)到的非終結(jié)符的集合記作R(S)。由Ri(S)構(gòu)造Ri+1(S)0≤i,具體的方法如下：（i）

R0(S)={S}（ii）

Ri+1(S)=Ri(S)∪{A|A在N中，對(duì)Ri(S)中的某個(gè)B，存在一個(gè)產(chǎn)生式B→σAγ},i=0,1,2,…，當(dāng)Ri+1(S)=Ri(S)時(shí)，構(gòu)造過(guò)程終止G1等價(jià)的文法是G2=(N，∑，P，S)，其中，N=R(S)，P只包括P的一部分產(chǎn)生式，在這部分產(chǎn)生式中，只有N中的元素才出現(xiàn)在其左邊或右邊^(qū)^^^^第24頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題假設(shè)文法G1=({S，A，B，C}，{a，b}，P，S)，以及產(chǎn)生式{S→aAA，A→aAb，A→aCA，B→b，B→Aa，C→b}。消除G1中不可到達(dá)無(wú)用的非終結(jié)符，求其等價(jià)文法G2。

第25頁(yè)，共44頁(yè)，2023年，2月20日，星期五具有喬姆斯基范式的文法

用喬姆斯基范式表示的產(chǎn)生式或者是A→BC形式（A，B，C在N中），或者是A→a的形式（A在N中，a在∑中），變換時(shí)產(chǎn)生式A→θ1θ2…θn替換為：

A→Y1Y2……n

Y2……n→Y2Y3……n

…… Yn-1,n→Yn-1Yn

帶下標(biāo)的Y是非終結(jié)符。如果，θi是非終結(jié)符，我們令Yi等于θi；如果θi是終結(jié)符，我們令Yi是一個(gè)新的非終結(jié)符，并引入產(chǎn)生式Y(jié)i→θi。第26頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題假設(shè)文法G2=({S，A，B}，{a，b}，P，S)具有產(chǎn)生式{S→BA，A→a，A→abABa，B→b}。將其產(chǎn)生式轉(zhuǎn)換為喬姆斯基范式，求其等價(jià)文法G2。第27頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題解答新非終結(jié)符集是{S,A,B,Y1，Y2345

，Y2，Y345

，Y45

，Y5}喬姆斯基范式產(chǎn)生式是：

S→BA，A→a，B→b

A→Y1Y2345

Y1→a Y2345→Y2Y345

Y2→b Y345→AY45

Y45→BY5

Y5→a

第28頁(yè)，共44頁(yè)，2023年，2月20日，星期五具有格雷巴赫范式的文法如果文法的每個(gè)產(chǎn)生式都是A→aα形式的，其中A是非終結(jié)符，a是終結(jié)符，α是在N*中，那么這個(gè)文法是格雷巴赫（Greibach）范式的令重寫某一特定非終結(jié)符A的產(chǎn)生式的整個(gè)集合是{A→γ1，A→γ2，…，A→γn}；那么，G1中的形式為B→σAθ的任何產(chǎn)生式可以用產(chǎn)生式集{B→σγ1θ，B→σγ2θ，…，B→σγnθ}代替

第29頁(yè)，共44頁(yè)，2023年，2月20日，星期五如果一種文法，其中至少存在一個(gè)非終結(jié)符A，對(duì)于(N∪∑)*中的γ，能使成立，那么稱這個(gè)文法為右遞歸的。相似的，如果有一種文法，其中存在一個(gè)非終結(jié)符A，對(duì)(N∪∑)*中β的，能使成立，那么稱這種文法為左遞歸的

遞歸定義A=>γA

+A=>Aβ

+第30頁(yè)，共44頁(yè)，2023年，2月20日，星期五消除左遞歸把重寫非終結(jié)符A的產(chǎn)生式集分為兩個(gè)子集。第一個(gè)子集產(chǎn)生式的右面是以A本身開(kāi)始的，如{A→Aγ1,A→Aγ2,…,A→Aγn}；第二個(gè)子集是那些右面不是從A開(kāi)始的，如{A→α1,A→α2,…,A→αm}。從這些產(chǎn)生式導(dǎo)出的句形是在集合{α1,…,αm}{γ1,…,γn}*中（i）A→α1,A→α2,…,A→αm（ii）A→α1A’,A→α2A’,…,A→αmA’，其中A’是新的非終結(jié)符。（iii）A’→γ1，A’→γ2，…，A’→γn

（iv）A’→γ1A’，A’→γ2A’，…，A’→γnA’第31頁(yè)，共44頁(yè)，2023年，2月20日，星期五格雷巴赫范式變換假設(shè)G1已經(jīng)是喬姆斯基范式非終結(jié)符集記作{A1，A2，…，Am}，其中下標(biāo)是任意分配的。調(diào)整產(chǎn)生式，以保證如果有Ai→Ajθ，則j>i。我們按i=1，2，…，m增加的次序進(jìn)行調(diào)整。每個(gè)產(chǎn)生式都是Ak+1→aα形式，或者Ak+1→A1α形式，其中a在∑中，α在N*中，以及l(fā)≥k+1對(duì)每個(gè)Ak+1→Ak+1α這樣的產(chǎn)生式刪除左遞歸

第32頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題假設(shè)文法G2=({S，A，B}，{a，b}，P，S)具有產(chǎn)生式{S→BA，A→a，A→abABa，B→b}。將其產(chǎn)生式轉(zhuǎn)換格雷巴赫為范式，求其等價(jià)文法G2。第33頁(yè)，共44頁(yè)，2023年，2月20日，星期五下推自動(dòng)機(jī)PDA

下推自動(dòng)機(jī)它可形式地定義為7元組：M=（∑,Q,Γ,δ,q0,Z0,F），其中Q、∑、q0及F和有限自動(dòng)機(jī)中的定義相同。Γ是有窮下推字母表，δ是從Q×(∑U{λ})×Γ到Q×Γ*的有窮子集的映射，Z0在Γ中，是下推表的初始符。第34頁(yè)，共44頁(yè)，2023年，2月20日，星期五下推自動(dòng)機(jī)的一般表示（帶運(yùn)動(dòng)方向）輸入帶只讀頭有窮狀態(tài)集Q下推自動(dòng)機(jī)的一般表示讀寫頭下推表機(jī)器開(kāi)始運(yùn)行時(shí)狀態(tài)是q0堆棧上只有Z0輸入帶上包含來(lái)自∑+的串x，從左到右逐個(gè)地掃描串x的每個(gè)符號(hào)。δ映射規(guī)定下一個(gè)狀態(tài)，以及規(guī)定Γ*中哪個(gè)串能代替堆棧頂上的單字符。

如果機(jī)器從q0和堆棧頂上Z0開(kāi)始，掃描全部x后停在F的一個(gè)狀態(tài)上，則稱串x被PDA接受了。第35頁(yè)，共44頁(yè)，2023年，2月20日，星期五下推自動(dòng)機(jī)識(shí)別的語(yǔ)言L(M)={x|x在Σ+中，從狀態(tài)q0及堆棧頂?shù)腪0開(kāi)始，掃描全部x后M停在F的一個(gè)狀態(tài)上}。Lλ(M)={x|x在Σ+中，M從q0及Z0開(kāi)始，掃描全部x后M停在空棧上}。

第36頁(yè)，共44頁(yè)，2023年，2月20日，星期五下推自動(dòng)機(jī)舉例用空堆棧接受這些句子的PDA是個(gè)不確定的自動(dòng)機(jī)M=（{a,b,c,d}，{q0}，{S,A,B,C,D},δ,q0,S,Φ），其中δ映射定義如下：δ(q0,c,S)={(q0,DAB),(q0,C)}，δ(q0,d,C)={(q0,λ)}δ(q0,a,D)={(q0,λ)}δ(q0,b,B)={(q0,λ)}δ(q0,a,A)={(q0,DAB),(q0,C)}識(shí)別的語(yǔ)言:{x|x=candbn，n≥0}

第37頁(yè)，共44頁(yè)，2023年，2月20日，星期五上下文無(wú)關(guān)文法→下推自動(dòng)機(jī)G=(N,Σ,P,S)是一個(gè)上下文無(wú)關(guān)文法。構(gòu)造使L(G)=L(Ap)的下推自動(dòng)機(jī)。我們定義M=({q0},Σ,N∪Σ,δ,q0,S,Φ)，按下述方式從產(chǎn)生式得到δ映射：

（1）如果A→α在P中，則δ（q0,λ,A）包含(q0,α)；（2）對(duì)每個(gè)在Σ中的終結(jié)符a，有δ（q0,a,a）={(q0,λ)}

第38頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題G=({S,A}，{a,b,c,d}，P，S)，其中產(chǎn)生式為：

{S→cA,A→aAb,A→d}。 請(qǐng)給出下推自動(dòng)機(jī)

第39頁(yè)，共44頁(yè)，2023年，2月20日，星期五習(xí)題格雷巴赫范式文法是G1=({A,S,B},{a,b,c,d},P,S),其產(chǎn)生式為：S→cA，A→aAB，A→d，B→b

構(gòu)造下推自動(dòng)機(jī)M第40頁(yè)，共44頁(yè)，2023年，2月20日，星期五確定的下推自動(dòng)機(jī)DPDA是一個(gè)七元組Ap=（∑，Q，Γ，δ，q0，Z0，F(xiàn)）