模式識(shí)別講義第二章_第1頁
模式識(shí)別講義第二章_第2頁
模式識(shí)別講義第二章_第3頁
模式識(shí)別講義第二章_第4頁
模式識(shí)別講義第二章_第5頁
已閱讀5頁,還剩39頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

模式識(shí)別講義第二章第1頁,共44頁,2023年,2月20日,星期五短語結(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頁,共44頁,2023年,2月20日,星期五文法類型無約束文法:一個(gè)文法如果它的產(chǎn)生式的形式不受任何限制(除了串重寫規(guī)則是有窮集合這個(gè)一般規(guī)定以外)則它就是無約束的。

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

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

第5頁,共44頁,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頁,共44頁,2023年,2月20日,星期五有限自動(dòng)機(jī)的一般表示

起始態(tài)總是q0,由∑+來的輸入串x放在帶上,從帶的最左邊單元開始一個(gè)符號(hào)挨者一個(gè)符號(hào)對(duì)帶進(jìn)行掃描。從q0開始,掃描整個(gè)x串并遵循一個(gè)狀態(tài)序列,最后停在F中的一個(gè)狀態(tài)上,我們就說串x被接受了或者說被識(shí)別了(帶運(yùn)動(dòng)方向)輸入帶只讀頭有窮狀態(tài)集Q有限自動(dòng)機(jī)的一般表示第7頁,共44頁,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頁,共44頁,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來說p在δ(q,a)之中}。第9頁,共44頁,2023年,2月20日,星期五習(xí)題已知有限自動(dòng)機(jī)如圖:請(qǐng)將其確定化。q0bq1a有限自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移圖第10頁,共44頁,2023年,2月20日,星期五習(xí)題解答qAqBq0qφbb確定的有限自動(dòng)機(jī)aababa第11頁,共44頁,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頁,共44頁,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頁,共44頁,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頁,共44頁,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頁,共44頁,2023年,2月20日,星期五等價(jià)的上下文無關(guān)文法

如果L(G1)=L(G2)

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

等價(jià)變換:

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

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

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

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

的導(dǎo)出式,則這個(gè)文法就是無循環(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ì)被刪除。

無循環(huán)的文法

A=>A+A=>A+第17頁,共44頁,2023年,2月20日,星期五無循環(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來說,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頁,共44頁,2023年,2月20日,星期五在對(duì)N中的每個(gè)非終結(jié)符A確定了集合K(A)以后,我們用定義等價(jià)文法G2=(N,∑,p,S)的方法刪除所有的形式為A→B的產(chǎn)生式(從而刪除了任何循環(huán))??筛鶕?jù)下述要求來確定等價(jià)文法G2的產(chǎn)生式:對(duì)非終結(jié)符A和B來說,如果B是在K(A)中,并且在P中存在一個(gè)產(chǎn)生式B→β,其中β不是單個(gè)的非終結(jié)符,那么就把產(chǎn)生式A→β放在p中。

無循環(huán)的文法變換(2)^^第19頁,共44頁,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頁,共44頁,2023年,2月20日,星期五非終結(jié)符A是無用的條件是:(i)不存在滿足導(dǎo)出式的終結(jié)符串x;或

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

A=>xG1*S=>aAβG1*第21頁,共44頁,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)成過程結(jié)束。G1等價(jià)的文法是G2=(N,∑,P,S),其中,N=J(G1),和P只包括那些來自P,并和N中的元素有關(guān)的那些產(chǎn)生式

消除不能導(dǎo)出終結(jié)符的A^^^^^第22頁,共44頁,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é)符的無用的非終結(jié)符,求其等價(jià)文法G2。第23頁,共44頁,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)造過程終止G1等價(jià)的文法是G2=(N,∑,P,S),其中,N=R(S),P只包括P的一部分產(chǎn)生式,在這部分產(chǎn)生式中,只有N中的元素才出現(xiàn)在其左邊或右邊^(qū)^^^^第24頁,共44頁,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á)無用的非終結(jié)符,求其等價(jià)文法G2。

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

遞歸定義A=>γA

+A=>Aβ

+第30頁,共44頁,2023年,2月20日,星期五消除左遞歸把重寫非終結(jié)符A的產(chǎn)生式集分為兩個(gè)子集。第一個(gè)子集產(chǎn)生式的右面是以A本身開始的,如{A→Aγ1,A→Aγ2,…,A→Aγn};第二個(gè)子集是那些右面不是從A開始的,如{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頁,共44頁,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頁,共44頁,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頁,共44頁,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頁,共44頁,2023年,2月20日,星期五下推自動(dòng)機(jī)的一般表示(帶運(yùn)動(dòng)方向)輸入帶只讀頭有窮狀態(tài)集Q下推自動(dòng)機(jī)的一般表示讀寫頭下推表機(jī)器開始運(yùn)行時(shí)狀態(tài)是q0堆棧上只有Z0輸入帶上包含來自∑+的串x,從左到右逐個(gè)地掃描串x的每個(gè)符號(hào)。δ映射規(guī)定下一個(gè)狀態(tài),以及規(guī)定Γ*中哪個(gè)串能代替堆棧頂上的單字符。

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

第36頁,共44頁,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í)別的語言:{x|x=candbn,n≥0}

第37頁,共44頁,2023年,2月20日,星期五上下文無關(guān)文法→下推自動(dòng)機(jī)G=(N,Σ,P,S)是一個(gè)上下文無關(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頁,共44頁,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頁,共44頁,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頁,共44頁,2023年,2月20日,星期五確定的下推自動(dòng)機(jī)DPDA是一個(gè)七元組Ap=(∑,Q,Γ,δ,q0,Z0,F(xiàn))

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論