中科院《模式識別》——第七章

1、第七章 句法模式識別第七章 句法模式識別 統(tǒng)計模式識別是基于模式特征的一組測量值來組成特征向量，用決策理論劃分特征空間的方法進行分類。 基于描述模式的結(jié)構(gòu)信息，用形式語言中的規(guī)則進行分類，可以更典型地應(yīng)用于景物圖片的分析。 因為在這類問題中，所研究的模式通常十分復(fù)雜，需要的特征也很多，僅用數(shù)值上的特征不足以反映它們的類別。第七章 句法模式識別 句法模式識別系統(tǒng)的組成 圖像預(yù)處理 圖像分割 基元及其關(guān)系識別 句法分析第七章 句法模式識別 句法模式識別系統(tǒng)框圖第七章 句法模式識別 對圖像的結(jié)構(gòu)信息描述第七章 句法模式識別 句法模式識別系統(tǒng)處理過程 待識別的輸入圖像，經(jīng)過增強、去噪聲等處理后，按識別

2、的具體對象分割成子圖； 三角體D和長方體E 然后將子圖分割成更簡單的模式基元； 組成三角體和長方體的各個面L,T和X,Y,Z 判別基元之間的關(guān)系。 三角體D是由相互鄰接的四邊形L和三角形T組成 長方體E是有三個相互鄰接的四邊形X,Y和Z組成第七章 句法模式識別 句法模式識別系統(tǒng)處理過程 基元本身包含的結(jié)構(gòu)信息已不多，僅需少量特征即可識別。 如果用有限個字符代表不同的基元，則由基元按一定結(jié)構(gòu)關(guān)系組成的子圖或圖形可以用一個有序的字符串來代表。 假如事先用形式語言的規(guī)則從字符串中推斷出能生成它的文法，則可以通過句法分析，按給定的句法（文法）來辨識由基元字符組成的句子，從而判別它是否屬于由該給定文法所

3、能描述的模式類，達到分類的目的。第七章 句法模式識別 句法模式識別學(xué)習(xí)過程 為了要事先確定一個文法來描述所要研究模式的結(jié)構(gòu)信息，同樣需要采用模式的訓(xùn)練樣本集把文法推斷出來。 有了推斷出來的文法，才可以對未知類別的字符串進行句法分析，達到分類的目的。 這一過程類似于統(tǒng)計模式識別中的學(xué)習(xí)過程，但文法推斷過程遠不及統(tǒng)計學(xué)習(xí)來的成熟。7.1 集合論中的關(guān)系運算 要進行句法識別中基元之間關(guān)系的判別，首先要明確關(guān)系運算。 “關(guān)系”在客觀世界中廣泛存在 社會生活：父子關(guān)系，母子關(guān)系，兄弟關(guān)系，等等； 數(shù)學(xué)運算：大于、等于和小于關(guān)系，函數(shù)關(guān)系，等等。 二元關(guān)系 凡是一對對象之間的關(guān)系，都是二元關(guān)系。7.1 集

4、合論中的關(guān)系運算 二元關(guān)系的相關(guān)概念 有序偶 設(shè)用表示一有序偶，它可以代表迪卡兒坐標(biāo)，例如，等，它們表示平面坐標(biāo)上的不同點。 兩個有序偶和相等，定義為 迪卡兒積 設(shè)A和B是任意兩個集合，由A中的一個元素和B中的一個元素組成有序偶，那么由A和B中所有元素組成的有序偶集合，稱為A和B的迪卡兒積，寫成A x B。 公式表達： 例子)By()Ax( | )y, x(BA7.1 集合論中的關(guān)系運算 二元關(guān)系的相關(guān)概念 二元關(guān)系的定義及表示 任意有序?qū)Φ募隙x一種二元關(guān)系，簡稱為關(guān)系 表示 設(shè)一有序?qū)?，其中R是一種關(guān)系，則記為xRy 例子7.1 集合論中的關(guān)系運算 二元關(guān)系的性質(zhì) 定義：自反 集合X中

5、的關(guān)系R是自反的，只要對X中的每個x，有xRx，則屬于R。 寫法：X中的R是自反的 定義：對稱 集合X中的關(guān)系R是對稱的，只要對X中的每個x和y，每當(dāng)xRy時總有yRx。 寫法： X中的R是對稱的 例：實數(shù)集合中的“=”不是對稱的，但“=”關(guān)系是對稱的。 例：全體人的集合中，師生關(guān)系不是對稱的，但同學(xué)關(guān)系是對稱的。 例：平面上三角形集合中的相似關(guān)系是自反的和對稱的。7.1 集合論中的關(guān)系運算 二元關(guān)系的性質(zhì) 定義：傳遞 集合X中的關(guān)系R是傳遞的，只要對X中的每個x, y和z，一旦xRy且yRz，則有xRz。 寫法：X中的R是傳遞的 例：若abc，則ac，表明”“關(guān)系是傳遞的 定義：非自反 集合

6、X中的關(guān)系R是非自反的，只要對X中的每個x，有不屬于R。 例7.1 集合論中的關(guān)系運算 二元關(guān)系的性質(zhì) 定義：反對稱 集合X中的關(guān)系R是反對稱的，只要對X中的每個x和y，一旦xRy且yRx，則有x=y。 寫法： X中的R是反對稱的 例7.1 集合論中的關(guān)系運算 關(guān)系圖 關(guān)系可以用圖形表示 設(shè)R為集合X=x, y, z中的一種關(guān)系，X中的元素用結(jié)點表示，并用相應(yīng)的元素名稱標(biāo)志。如果xRy，則用帶箭頭的弧線連接結(jié)點x和y。7.1 集合論中的關(guān)系運算 等價關(guān)系 如果集合X中的關(guān)系R是自反的、對稱的和傳遞的，則稱它是一個等價關(guān)系。 實數(shù)集合中的數(shù)值相等 三角形集合中的三角形相似 一個班內(nèi)同學(xué)之間的同班

7、關(guān)系 等價類定義 等價類性質(zhì) 集合X上的等價關(guān)系R所構(gòu)成的類兩兩不相交，且覆蓋了整個集合X。7.1 集合論中的關(guān)系運算 等價關(guān)系 可以用圖形方法分析研究等價劃分：由于等價關(guān)系是自反的、對稱的、傳遞的，因此由這些性質(zhì)的圖形特點可知： 一個集合X上的等價關(guān)系R的關(guān)系圖，其每個結(jié)點必有環(huán)； 若兩個結(jié)點間有邊相連，則必有方向彼此相反的兩條有向邊； 若圖中任何兩個結(jié)點是可達的，則必有邊直接相連。 例子7.1 集合論中的關(guān)系運算 兼容關(guān)系 如果X中的關(guān)系R是自反的而且是對稱的，則稱R是一個兼容關(guān)系。 所有的等價關(guān)系是兼容關(guān)系； 兼容關(guān)系不一定是傳遞的。 偏序關(guān)系 集合P上的二元關(guān)系R稱為P上的一個偏序關(guān)系

8、，當(dāng)且僅當(dāng)R是自反的、反對稱的和傳遞的。 偏序關(guān)系通常用“=”表示，但注意“ A”叔侄”C7.1 集合論中的關(guān)系運算 二元關(guān)系的復(fù)合 關(guān)系圖7.1 集合論中的關(guān)系運算 二元關(guān)系的復(fù)合 關(guān)系的復(fù)合運算可以施加于自身 表示為：RR =R2，RRR =R3 ， 傳遞閉包 例子7.2 形式語言理論和句法模式識別 形式語言的起源可以追溯到二十世紀(jì)五十年代； 喬姆斯基(Chomsky)等科學(xué)家在研究語言的工作中發(fā)展了文法的數(shù)學(xué)模型； 其基本目的是發(fā)展一種應(yīng)用于計算機的文法，使它有描述自然語言的能力，例如英文。 如果能做到這一點，則有希望“教”計算機理解自然語言，以達到翻譯的目的。7.2 形式語言理論和句法

9、模式識別 形式語言的基本目的迄今為止尚未完全實現(xiàn)，但在這個領(lǐng)域的研究成果卻大大沖擊了其它一些領(lǐng)域 計算機編譯系統(tǒng)的設(shè)計 計算機語言 自動機理論 模式識別7.2 形式語言理論和句法模式識別 在模式識別中，如果大量復(fù)雜的模式的集合，能用一組為數(shù)不多的簡單的模式基元和文法規(guī)則來描述，則對每一個模式的識別，就可以按給定的一組文法結(jié)構(gòu)規(guī)則來剖析； 如果解析的結(jié)果表明，模式基元能為給定的文法規(guī)則所接受，則可判別它屬于該模式類，否則就不屬于該模式類。7.2 形式語言理論和句法模式識別7.2.1 形式語言理論中的某些定義 形式語言是一種抽象語言，它可以包括人類使用的自然語言、計算機使用的各種語言、數(shù)學(xué)中的公式

10、語言等。 自然語言（英文）：它的基本組成是有限個字母，將字母（組成的單詞）按一定的文法規(guī)則排列，可以構(gòu)成句子，而一種語言則是所有句子的集合。 人類的自然語言是一個不可數(shù)的有窮集 英文：26個字母按一定的文法規(guī)則組合，可以表達無數(shù)的思想內(nèi)容。7.2 形式語言理論和句法模式識別7.2.1 形式語言理論中的某些定義 字母表和符號串 字母表：以某些符號作為元素的非空有窮集，以V或表示。 符號串：由字母表中符號組成的任何有窮序列。 例子 空符號串：不包含任何符號的串，用表示。 符號串的長度：符號串x所包含的符號個數(shù)，用|x|表示。 例子 符號串的聯(lián)接：若x和y都是符號串，則把y符號串寫在x符號串之后，就

11、得到聯(lián)接的符號串xy。 例子7.2 形式語言理論和句法模式識別7.2.1 形式語言理論中的某些定義 字母表和符號串 符號串集合的乘積 例子 如果A和B只是代表一個符號串，而不是符號串的集合，則乘積AB與符號串的聯(lián)接結(jié)果相同。 符號串和符號串集合A的冪 集合A的正閉包、閉包 字母表V的冪 集合V的正閉包、閉包 例子7.2 形式語言理論和句法模式識別7.2.1 形式語言理論中的某些定義 文法 一種語言中構(gòu)成句子所必須遵守的規(guī)則； 由某種語言的字母表中的字母所組成的串不一定都是該語言的句子； 只有當(dāng)一個串符合該語言的文法規(guī)則時，才能算是該語言的句子，否則就不是該語言的句子。7.2 形式語言理論和句法

12、模式識別7.2.1 形式語言理論中的某些定義 文法定義 文法舉例 在生成規(guī)則P中，帶的符號稱為語法元，不帶的符號稱為單詞； 一個簡單句的生成由語法元()開始，反復(fù)把生成規(guī)則中箭頭左邊的部分用其右邊的部分替換，直到所得的形式中不再出現(xiàn)語法元而只有單詞為止。 簡單句“The boy runs.”符合給定的文法規(guī)則，因為它可以由上述的文法規(guī)則產(chǎn)生。 生成過程7.2 形式語言理論和句法模式識別7.2.1 形式語言理論中的某些定義 文法舉例 文法樹7.2 形式語言理論和句法模式識別7.2.1 形式語言理論中的某些定義 利用文法樹可以闡明文法的形式化定義： 文法樹的根一定是文法G的起始符S； 樹的葉一定是

13、終止符； 樹的每一個分支（子樹）在沿著根到葉的方向上可以表示成一個直接推導(dǎo)的生成式； 如果利用文法樹的逆過程，則可將生成過程重新構(gòu)造出來。7.2 形式語言理論和句法模式識別7.2.2 語言的生成過程 利用文法G來生成語言的過程中的一些規(guī)定 非終止符VN用大寫英文字母：S, A, B, C, 終止符VT用英文字母表起始部分的小寫字母：a, b, c, 終止符組成的字符串用英文字母表中尾部的小寫字母：u, v, w, x, 終止符和非終止符混合組成的字符串用希臘字母：, , , , 7.2 形式語言理論和句法模式識別7.2.2 語言的生成過程 利用文法G來生成語言的過程中的一些規(guī)定 生成式P由以下

14、形式的表達式組成：-，其中是V+中的字符串， 是V*中的字符串，“- ”表示字符串被所取代。 =表示根據(jù)文法G，由一字符串直接推導(dǎo)出另一字符串。 例子7.2 形式語言理論和句法模式識別7.2.2 語言的生成過程 句型和句子 定義 句型是由起始符開始進行推導(dǎo)而得到的由字母表中的符號（包括VN 、VT和）組成的任意字符串； 句型和句子關(guān)系 句子一定是由字母表中終止符組成的字符串。7.2 形式語言理論和句法模式識別7.2.2 語言的生成過程 語言 定義 短語 定義 從起始符推導(dǎo)一個句子的過程，實際上就是將推導(dǎo)過程中句型的一部分不斷用短語來取代的過程，這種文法稱為短語結(jié)構(gòu)文法。7.2 形式語言理論和句

15、法模式識別7.2.2 語言的生成過程 例子 從生成規(guī)則P中可以看出，只有第二生成式A-aAc中出現(xiàn)了a和c，可見由此生成的字符串中a和c的個數(shù)是同樣多的，且a和c只能分別地連續(xù)出現(xiàn)。 如果不用第二生成式A-aAc而用第三生成式A-B時，則只能往下用第四生成式B-bB和第五生成式B-b，這樣再也不會出現(xiàn)a和c。 因此由P生成的字符串只能是anbmcn的形式。L(G)=anbmcn|m,n=1且僅為整數(shù)7.2 形式語言理論和句法模式識別7.2.2 語言的生成過程 文法G產(chǎn)生語言的描述 一個文法G=(VN, VT , P, S)所產(chǎn)生的語言，是由S開始所推導(dǎo)出的所有終止符的集合，它滿足兩個條件 每一

16、個字符串只能由終止符組成，即每一個字符串都是終止符句子； 每一個字符串都能從S開始，適當(dāng)應(yīng)用P中的生成式來導(dǎo)出。7.2 形式語言理論和句法模式識別7.2.2 文法的分類 文法可定義為一個四元組G=(VN,VT,P,S)，喬姆斯基按照文法所允許的生成形式的不同，定義四種文法類型： 0型文法：稱為無約束文法 1型文法：稱為上下文有關(guān)文法 2型文法：稱為上下文無關(guān)文法 3型文法：稱為正則文法7.2 形式語言理論和句法模式識別7.2.2 文法的分類 0型文法（無約束文法） 生成式形式 說明 可以有=，但不能有=； 只有0型文法才允許有產(chǎn)生空句的生成式。7.2 形式語言理論和句法模式識別7.2.2 文法

17、的分類 1型文法（上下文有關(guān)文法） 生成式形式 說明 在1和2之間的非終止符可以重寫為，這里1和2稱為句型1A2對于A的上下文； 不是在1和2之間的A不能使用此規(guī)則。 例子 從表面上看似乎上下文并不完整； 但根據(jù)1型文法的定義， 1、2屬于V*，可以有1=2 =； 因此生成規(guī)則P可以改寫成例中生成式右側(cè)所示形式。7.2 形式語言理論和句法模式識別7.2.2 文法的分類 2型文法（上下文無關(guān)文法） 生成式形式 說明 該文法表明生成式左側(cè)為單變量，可由右側(cè)的字符串來取代，因此是上下文無關(guān)的。7.2 形式語言理論和句法模式識別7.2.2 文法的分類 3型文法（正則文法） 生成式形式 說明 該文法表明

18、規(guī)則右側(cè)一定要首先含有非終止符。7.2 形式語言理論和句法模式識別7.2.2 文法的分類 四種文法比較 正則文法（3型文法）生成規(guī)則的右側(cè)若不強調(diào)終止符的首先出現(xiàn)，就變成上下文無關(guān)文法（2型文法）； 上下文無關(guān)文法（2型文法）生成規(guī)則的左側(cè)若不強調(diào)單變量，而加以上下文限制，就變成上下文有關(guān)文法（1型文法）； 上下文有關(guān)文法（1型文法）去掉上下文的限制，就變成無約束文法（0型文法）。7.2 形式語言理論和句法模式識別7.2.2 文法的分類 四種文法比較 包含關(guān)系： 正則文法 上下文無關(guān)文法 上下文有關(guān)文法 無約束文法 所有正則文法都是上下文無關(guān)的； 所有上下文無關(guān)文法都是上下文有關(guān)的； 所有上下

19、文有關(guān)文法都是無約束的。 在句法模式識別中，多采用上下文無關(guān)文法和正則文法。7.2 形式語言理論和句法模式識別7.2.2 文法的分類 例1：無約束文法 例2：上下文有關(guān)文法 例3：上下文無關(guān)文法 例4：正則文法作業(yè) 寫出上下文無關(guān)文法，其終止符集VT=a,b能生成語言L(G)=ab,ba,aba,bab,abab,baba,7.3 句法結(jié)構(gòu)的自動機識別 一種類別的模式，可以用一個文法來描述。 要識別一個未知的模式，可以先用其基元表征成一個字符串或句子，然后再用該文法進行判斷。 若能被接受，則說明它是屬于該文法所生成的語言，亦即它是屬于該類模式，否則就不屬于該類模式。 自動機就是一種句法識別器，

20、它可以判斷一個句子是否屬于某種語言，并且自動機的類型與文法的類型有著某種對應(yīng)關(guān)系。7.3 句法結(jié)構(gòu)的自動機識別7.3.1 有限態(tài)自動機 有限態(tài)自動機是研究自動系統(tǒng)的一種數(shù)學(xué)模型，它能模擬多種離散的自動系統(tǒng)。 結(jié)構(gòu)概念實例：八進制計數(shù)器和有限態(tài)自動機模型 一個八進制計數(shù)器，要求每逢計數(shù)到6輸出一脈沖。 將該裝置看成是一個離散系統(tǒng)。7.3 句法結(jié)構(gòu)的自動機識別7.3.1 有限態(tài)自動機 結(jié)構(gòu)概念實例：八進制計數(shù)器和有限態(tài)自動機組成 輸入信息：接受順序輸入的計數(shù)脈沖作為輸入信息，有脈沖時為1，無脈沖時為0，以0,1組成的字符串作為輸入。 輸出信息：當(dāng)計數(shù)器的狀態(tài)到達6時，輸出一脈沖，其余情況均輸出為0

21、 ，以0,1組成的字符串作為輸出。 內(nèi)部狀態(tài)：觸發(fā)器q1、q2和q3所處的0或1的狀態(tài)。 該計數(shù)裝置是否有脈沖輸出，不僅依賴于當(dāng)前的輸入信息，而且還依賴于前一時刻觸發(fā)器所處的狀態(tài)亦即該觸發(fā)器的內(nèi)部狀態(tài)。這里三個觸發(fā)器所處的狀態(tài)的集合q1, q2, q3屬于有限個狀態(tài)的集合。7.3 句法結(jié)構(gòu)的自動機識別7.3.1 有限態(tài)自動機 結(jié)構(gòu)概念實例：八進制計數(shù)器和有限態(tài)自動機組成 狀態(tài)轉(zhuǎn)換：設(shè)以表示輸入0,1的集合，以Q表示內(nèi)部狀態(tài)的集合q1, q2 , q3，則狀態(tài)轉(zhuǎn)換函數(shù)可以表示成Q和到Q的映射，寫成迪卡兒乘積的形式為：Q x - Q， 稱為狀態(tài)轉(zhuǎn)移函數(shù)。 內(nèi)部狀態(tài)的轉(zhuǎn)換既依賴于輸入，也依賴于前一時

22、刻的內(nèi)部狀態(tài)。 輸出函數(shù)：在某時刻的輸出信息，一般由同一時刻的輸入信息和內(nèi)部狀態(tài)所決定。 它也是內(nèi)部狀態(tài)與輸入的映射 從上述組成可以看出，一個離散的有限狀態(tài)的自動系統(tǒng)由五部分組成。一個有限態(tài)自動機A是模擬多種離散自動系統(tǒng)的一種數(shù)學(xué)模型。7.3 句法結(jié)構(gòu)的自動機識別7.3.1 有限態(tài)自動機 有限態(tài)自動機定義 映射的狀態(tài)圖表示： 并不是全部可能的輸出函數(shù)都一定是需要的輸出終止?fàn)顟B(tài)，只有其中部分輸出狀態(tài)才是感興趣的輸出終止?fàn)顟B(tài)。 有限態(tài)自動機抽象結(jié)構(gòu)示意圖7.3 句法結(jié)構(gòu)的自動機識別7.3.1 有限態(tài)自動機 結(jié)構(gòu)示意圖描述 控制器上記錄了各種狀態(tài)，并且各種狀態(tài)之間按一定的規(guī)則在控制器中變化，而變化的

23、改變是受輸入支配的。 具體來說，控制器相對于輸入磁帶自左向右移動，每接受一個輸入符號便右移一個單位，并改變一次狀態(tài)，直至一個句子的全部符號輸入結(jié)束。 同時，每輸入一個符號，控制器要根據(jù)狀態(tài)規(guī)則來判斷能否接受該符號，若所有的符號都能被接受，就說明該句子屬于該自動機所能接受的那種語言。 此時，狀態(tài)變換(q,a)=q表示“處于狀態(tài)q并正在掃描輸入符號a”的自動機A，將讀入磁頭右移一個單元，并轉(zhuǎn)到狀態(tài)q。 自動機輸入句子后，若(q,x)=q且q在F中，則稱句子x被有限態(tài)自動機A所接受。7.3 句法結(jié)構(gòu)的自動機識別7.3.1 有限態(tài)自動機 正規(guī)集 由有限態(tài)自動機A接受的所有句子x的集合表示為： T(A)

24、=x|(q,x)在F中，F(xiàn)是終止?fàn)顟B(tài)集。 由有限態(tài)自動機接受的句子的任何集合，稱為正規(guī)集。7.3 句法結(jié)構(gòu)的自動機識別7.3.1 有限態(tài)自動機 例子 狀態(tài)圖7.3 句法結(jié)構(gòu)的自動機識別7.3.2 非確定有限態(tài)自動機 確定有限態(tài)自動機 映射關(guān)系唯一 非確定的有限態(tài)自動機 它所確定的狀態(tài)不是唯一的，可以由若干個狀態(tài)可供選擇，亦即是一個狀態(tài)集。 映射關(guān)系：(q, x) =p1, p2, , pk 自動機A在狀態(tài)q若輸入字母為x，則其轉(zhuǎn)換到下一時刻的狀態(tài)可以從p1, p2, pk這k個狀態(tài)中任選一個，這樣的一種自動機稱為非確定有限態(tài)自動機。7.3 句法結(jié)構(gòu)的自動機識別7.3.2 非確定有限態(tài)自動機 形

25、式化定義 例子7.3 句法結(jié)構(gòu)的自動機識別7.3.2 非確定有限態(tài)自動機 非確定有限態(tài)自動機與確定有限態(tài)自動機的關(guān)系 非確定有限態(tài)自動機是確定有限態(tài)自動機的推廣 形式化描述7.3 句法結(jié)構(gòu)的自動機識別7.3.2 非確定有限態(tài)自動機 非確定有限態(tài)自動機與確定有限態(tài)自動機的關(guān)系 例子 非確定的有限態(tài)自動機和確定的有限態(tài)自動機統(tǒng)稱為有限態(tài)自動機7.3 句法結(jié)構(gòu)的自動機識別7.3.3 按正則文法構(gòu)造有限態(tài)自動機 形式化描述 例子7.3 句法結(jié)構(gòu)的自動機識別7.3.4 按有限態(tài)自動機確定正則文法 形式化描述 例子作業(yè) 求一有限態(tài)自動機，它只能接受由“偶數(shù)個a”與/或“偶數(shù)個b”組成的任意字符串，例如：a

26、a, bb, abab, abba, baba等。7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 上下文無關(guān)語言的范式 任何上下文無關(guān)文法的生成式A-都可以寫成喬姆斯基范式或格雷巴赫標(biāo)準(zhǔn)式 喬姆斯基范式 形式：A-BC，A-a，其中 例子 格雷巴赫標(biāo)準(zhǔn)式 形式：A-a ，其中 例子7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 構(gòu)造下推自動機的原因 若正則文法的生成規(guī)則為A-aB，生成式的左側(cè)和右側(cè)都只有一個非終止符，則用有限態(tài)自動機的狀態(tài)轉(zhuǎn)換來表達就已經(jīng)足夠了。 但在上下文無關(guān)文法中，生成式左側(cè)只有一個非終止符，但右側(cè)不止一個非終止符，如A-aBC。

27、對于A-a的一般情況，生成式右側(cè)可以是任意數(shù)目的非終止符，如寫成A-aA1A2An。 在這種情況下，如果仍舊用有限態(tài)自動機來識別，當(dāng)自動機接受了a后，狀態(tài)A只能轉(zhuǎn)換到A1，下一步僅能考慮從A1開始， A2An都被忽略了。 結(jié)論：用有限態(tài)自動機不能識別上下文無關(guān)文法。7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 下推自動機的概念 下推自動機針對上述情況，另行配置一個堆棧來壓入任意數(shù)目的非終止符。這些非終止符都應(yīng)包括在上下文無關(guān)文法之中。 堆棧：后進先出，就是最后一個被壓入的非終止符始終處于棧的頂部。 在沒有壓入任何符號串之前，棧頂內(nèi)容為起始符。 在處理過程中，棧頂?shù)姆墙K止符

28、Ai與輸入字符串中的終止符a共同決定了自動機狀態(tài)的轉(zhuǎn)移，而在輸入終止符使自動機狀態(tài)轉(zhuǎn)移的同時，棧頂內(nèi)容亦改變。 帶有這種堆棧結(jié)構(gòu)成為下推自動機的特點。7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 下推自動機的概念 根據(jù)下推自動機的特點，下推自動機不能只用一個狀態(tài)參數(shù)qi來描述，而必須加上棧頂內(nèi)容ri 。 若將棧頂內(nèi)容也看作是一個狀態(tài)，則兩個參數(shù)聯(lián)合的格局(qi, ri)才能準(zhǔn)確地描述自動機的當(dāng)前狀態(tài)。 輸入終止符a，將引起自動機的格局轉(zhuǎn)移，每個輸入終止符所引起的新格局，都和原格局有關(guān)，即與以前的輸入內(nèi)容有關(guān)。所以，每個新格局都能反映當(dāng)時及以前的輸入符號串。 按此推理，自動

29、機的最后格局也就反映了輸入句子的全部符號，可用它來進行句子的識別。7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 下推自動機的模型和定義 下推自動機構(gòu)造模型7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 下推自動機的模型和定義 下推自動機實質(zhì)上是在有限態(tài)自動機上再加上一個后進先出的堆棧，堆棧的一段固定，只能在另一端上存或取。 通常用代表轉(zhuǎn)換過程中處于棧頂?shù)挠邢拮帜讣?=Zi|i=1,2,n7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 下推自動機的模型和定義 下推自動機定義 映射的含義：在自動機q狀態(tài)下和堆棧頂為Z時，輸入符號a，這

30、時造成的映射使自動機進入下一個格局(qi, ri)，即原來處于棧頂?shù)姆朲被壓入棧內(nèi)，而棧頂變成ri串中的首位符號，自動機進入狀態(tài)qi 。7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 下推自動機的模型和定義 格局變幻的表達式： 變換式的含義： 對應(yīng)于映射規(guī)則，輸入一個符號a，可使下推自動機M從格局(q, Zr)轉(zhuǎn)向(qi, rir)，這里Z為轉(zhuǎn)換前的棧頂符號，ri為轉(zhuǎn)換后的棧頂符號串。 ri代表一個符號串，這時棧頂符號應(yīng)為ri串中的首位符號。 一個連串導(dǎo)出關(guān)系 若存在 ，則對1n之間的所有i，有7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 下推自動機

31、接受語言的方式 終止?fàn)顟B(tài)方式 定義：下推自動機用終止?fàn)顟B(tài)方式所接受的語言T(M)定義為： 含義：當(dāng)下推自動機M從起始狀態(tài)q0開始到達終止?fàn)顟B(tài)q，同時其堆棧棧頂符號從起始符號Z0開始變成r，則接受一個句子x，這是利用狀態(tài)參數(shù)q是否到達終止?fàn)顟B(tài)集F來識別語言的方式。 所有識別的句子x的集合就是下推自動機所接受的語言T(M)。rF,qr),(q,| )Z,(q:x|xT(M)*007.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 下推自動機接受語言的方式 空堆棧方式 定義：下推自動機用空堆棧方式所接受的語言N(M)定義為： 含義：不管q是否到達終止?fàn)顟B(tài)，只要堆棧變空，輸入句子x就被

32、接受，這是利用輸入x的過程中堆棧符號r的變換來識別語言的方式。7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 下推自動機接受語言的方式 例子 在接受xcxR, x=0,1*的句型時： 在狀態(tài)q1時可反復(fù)使用(q1,a,A)接受x，其中a=0或1，A=R,B或G，并使下推自動機存有符號串=(RUB,G*)R 接受符號c后，狀態(tài)變?yōu)閝2 在狀態(tài)q2時，每接受一個符號（0或1），堆棧中的符號被上推，被取出時的次序與存入時的次序恰好相反，故在q2狀態(tài)下接受xR 因此，L(G)為xcxR7.3 句法結(jié)構(gòu)的自動機識別7.3.5 下推自動機和上下文無關(guān)文法 下推自動機與上下文無關(guān)語言的聯(lián)

33、系 描述 例子7.4 基元的提取 模式識別的主要任務(wù)之一就是圖形的識別。描述一個待識別的圖形模式可以借助于一組基元，用語言結(jié)構(gòu)法進行識別。 基元對應(yīng)于文法中的終止符，它是構(gòu)成句子的最基本單位。 選擇好的基元對有效地進行句法模式識別是十分重要的，可惜的是目前基元選擇還沒有一個通用的方法，只能根據(jù)具體因素而定。 模式的數(shù)據(jù)性質(zhì) 待識別對象的具體應(yīng)用 識別系統(tǒng)所用的技術(shù)7.4 基元的提取 基元選擇應(yīng)注意的兩點 基元應(yīng)是模式的基本單元，且易于利用它們之間的結(jié)構(gòu)關(guān)系來緊湊方便地描述模式。 例如：圖形識別中各子圖形之間的連接關(guān)系就可以用基元的結(jié)構(gòu)關(guān)系來表達 基元是最簡單的子模式，它本身的結(jié)構(gòu)信息已不重要，

34、可用非語言方法（如統(tǒng)計方法、幾何尺寸度量等）來提取。 例如：識別手寫文字用筆畫作為基元比較有效，語音識別采用音素作為基元比較方便，心電圖識別采用收縮波和擴張波的波形變化特征作為基元比較直接，等等。7.4 基元的提取 在圖形識別中，對平面圖形可以采用兩種類型的基元。 從圖形的邊界、輪廓或骨架提取基元； 以圖形的基本組成區(qū)域作為基元。7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 Freeman鏈碼可以用來描述圖形的邊界和骨架。7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 Freeman鏈碼可以用來描述圖形的邊界和骨架。 將待描述的曲線量化，曲線落在每一個方格中的各個分段可用8個

35、方向之一來近似。 例如，圖中的曲線可表示為字符串：4444570767077 可以通過句法分析來判別待識別的曲線。7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 Freeman鏈碼可以用來描述圖形的邊界和骨架。 在實際應(yīng)用中，直接采用Freeman鏈碼中的元素作為基元，會將曲線圖形分割的太細，造成句法分析的復(fù)雜化。 若選用若干種有共性特點的弧形曲線段作為基元，亦能描述圖形，但比直接用Freeman鏈碼簡單。 可用一種變換把原來的8種基本方向變換成一組弧形曲線基元，使描述模式的句子短一些。7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 可將模式的描述用字符串的形式表示為：V=V1

36、 V2 Vn，其中Vi是串中的一個基元，它可以是一段不變曲率的弧，多邊形的一條邊，或一段二次曲線的弧等等。 若Vi取自有窮字母表，則可直接采用句法分析。 進行句法分析之前要消除噪聲，對邊界曲線進行預(yù)處理。7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 例子：亞中央著絲點染色體的多級結(jié)構(gòu)描述7.4 基元的提取7.4.1 圖形邊界或骨架的基元選擇 例子：亞中央著絲點染色體的多級結(jié)構(gòu)描述 基元采用曲線段a,b,c,d 從左到右把樹的葉子匯集起來，就構(gòu)成了一個字符串，恰好表達了染色體的邊界形狀。 用符號編碼表示為：babcbabdbabcbabd，表達了這類染色體的一個句子。7.4 基元的提取

37、7.4.1 圖形邊界或骨架的基元選擇 討論 描述一種圖形采用哪種基元最合適沒有統(tǒng)一的標(biāo)準(zhǔn)和方法，因圖形曲線的不同而異。 一般可兼顧兩點 基元的提取方法盡可能簡單 描述曲線的句子盡量短一些7.4 基元的提取7.4.2 按區(qū)域劃分成多邊形近似的基元 這種基元著眼于待識別圖形的區(qū)域。 將待識別的圖形理想化為一個多邊形，再以若干個凸多邊形的“并”來表示該多邊形，而凸多邊形又用若干半平面的“交”來組成。 用形式語言表示 半平面是字母 凸多邊形是由這些字母組成的字 由這些字組成的句子就相當(dāng)于代表圖形的多邊形 可采用凸多邊形作為基元7.4 基元的提取7.4.2 按區(qū)域劃分成多邊形近似的基元 例子：采用凸多邊

38、形作為基元的五邊形 用窮舉試探法求取基元的試探步驟 例子7.5 形式語言在圖形識別中的應(yīng)用7.5.1 各種文法用于模式識別的功能比較 前面討論了基元的提取問題，下面要根據(jù)各種提取的基元來構(gòu)造適當(dāng)?shù)奈姆ǎ援a(chǎn)生出描述所要識別的圖形的一種語言。 從理論上講，最好是能有一個推斷文法的機器，它能根據(jù)給定的一些符號串的集合，推斷出一個合適的文法。 但遺憾的是，在實際中除了某些非常特殊的情況外，至今還沒有這樣一種有效的機器。 一般上仍是由設(shè)計者憑自己的經(jīng)驗和所謂的先驗知識來構(gòu)造文法。7.5 形式語言在圖形識別中的應(yīng)用7.5.1 各種文法用于模式識別的功能比較 構(gòu)造圖形識別的文法仍以前面介紹的形式語言為基礎(chǔ)

39、。 一般來說，希望采用有很強描述圖形能力的文法，但這樣做反過來又增加識別器的復(fù)雜性。7.5 形式語言在圖形識別中的應(yīng)用7.5.1 各種文法用于模式識別的功能比較 正則文法的生成式最為簡單，它所受的限制也最多，描述圖形模式的能力最差，但在句法分析中是最容易實現(xiàn)的，因為一定存在一個確定的有限態(tài)自動機與之對應(yīng)。 上下文無關(guān)文法所受的限制要少一些，描述能力要強一些，但為了接受這種文法產(chǎn)生的語言，通常要求非有限、非確定性的句法分析步驟，與之對應(yīng)的是一個不確定的下推自動機，因而實現(xiàn)起來比確定的有限態(tài)自動機復(fù)雜。 上下文有關(guān)文法所產(chǎn)生的語言的分析，就更困難了。7.5 形式語言在圖形識別中的應(yīng)用7.5.1 各

40、種文法用于模式識別的功能比較 例子 采用上下文有關(guān)文法 采用上下文無關(guān)文法 采用正則文法 結(jié)果分析 n為有限整數(shù)時可構(gòu)造上下文無關(guān)文法，n限于3以內(nèi)可構(gòu)造正則文法。 但顯然，正則文法由于其規(guī)則數(shù)增多，造成其復(fù)雜性增加，而且隨著n的增大，規(guī)則數(shù)更是倍增，相比而言，上下文無關(guān)文法就簡潔得多。7.5 形式語言在圖形識別中的應(yīng)用7.5.1 各種文法用于模式識別的功能比較 討論 在具體應(yīng)用時，只能根據(jù)問題，在增加文法描述能力和簡化句法分析之間權(quán)衡，采取一些辦法來進行折衷，針對具體問題來構(gòu)造文法。 一般可通過對正則文法進行某些修改而使問題簡化。 例如文法的形式可能是上下文無關(guān)的，但設(shè)計語言則可以用有限態(tài)語

41、言來近似。7.5 形式語言在圖形識別中的應(yīng)用7.5.1 各種文法用于模式識別的功能比較 討論 此外，還要注意不要使構(gòu)造的文法所產(chǎn)生的符號串過剩。 圖形符號串的數(shù)目總是有限的，但多數(shù)情況下所構(gòu)造的文法，可能產(chǎn)生數(shù)目很大或無限多的符號串。 雖然希望過剩的符號串與代表圖形的符號串相似，但遺憾的是實際情況往往不是這樣，過剩的符號串常常是由文法自行構(gòu)造出來的。 當(dāng)過剩的符號串包含了屬于其它類別的圖形符號串時，問題就會變得非常嚴(yán)重，這是必須進行校正，把過剩的符號串從該文法所產(chǎn)生的語句中排除掉。7.5 形式語言在圖形識別中的應(yīng)用7.5.1 各種文法用于模式識別的功能比較 討論 綜上所述，建立一個文法，要同時

42、考慮圖形基元的選擇和文法的構(gòu)成，要兼顧文法的描述能力和句法分析系統(tǒng)的簡潔性，所以文法一般由設(shè)計者根據(jù)具體情況來構(gòu)造。 可以先由設(shè)計者提出基本性的文法和各種折衷方案，然后利用人機交互系統(tǒng)在計算機上進行修改和實驗，最終獲得一種高效文法及其推斷。7.5 形式語言在圖形識別中的應(yīng)用7.5.2 程序文法 為了使字符串文法的結(jié)構(gòu)更為緊湊，可在喬姆斯基文法上加上生成式去向的標(biāo)號，以規(guī)定某幾條生成式使用之后，下一次只能用規(guī)定的另外哪幾條生成式。 這樣可以使原來的字符串文法使用起來更為方便，易于檢查。7.5 形式語言在圖形識別中的應(yīng)用7.5.2 程序文法 定義和例子 例1 這里，生成式(1)采用成功后可繼續(xù)執(zhí)行

43、(1),(2)或(3)，而且其本身可反復(fù)使用。 生成式(2)成功后去向范圍是(2),(3)，即使用(2)后不能再使用(1)，但可用(2),(3)，這使P的生成語句中a,b,c只能各自連續(xù)地出現(xiàn)。 當(dāng)應(yīng)用的去向范圍遇到空時，則生成停止。7.5 形式語言在圖形識別中的應(yīng)用7.5.2 程序文法 例2 程序文法屬于喬姆斯基文法的哪一種形式，決定于生成式的核。 如果生成式的核為上下文無關(guān)形式，則這個文法是上下文無關(guān)的。 如果程序文法的核是正則形式，則該文法是正則文法。7.5 形式語言在圖形識別中的應(yīng)用7.5.2 程序文法 例3 可以證明，該上下文無關(guān)文法可以生成an bn cn |n=1 這個程序文法的

44、簡潔程度和剛才介紹的生成同樣語言的上下文有關(guān)文法相類似。7.5 形式語言在圖形識別中的應(yīng)用7.5.3 圖形描述語言PDL(Picture Description Language) 字符串文法中的基元與子模式的連接，按語法規(guī)則只能是左右連接，不能同時從四面八方連接，這種一維的連接方式不能滿足描述復(fù)雜圖形的要求。 PDL中的基元是由兩個點（稱為“頭”和“尾”）構(gòu)成的矢量，它可以組成任一復(fù)雜結(jié)構(gòu)的圖形。 對于二維圖形，該基元就是平面上的一個有向線段，它只需有兩個定義點，即頭和尾。 PDL用于描述圖形模式識別是比較成功的。7.5 形式語言在圖形識別中的應(yīng)用7.5.3 圖形描述語言PDL PDL基元的

45、連接規(guī)則7.5 形式語言在圖形識別中的應(yīng)用7.5.3 圖形描述語言PDL PDL基元的連接規(guī)則 一個基元只能在頭和尾兩點上與其它基元連接，因此它是具有有向支路的圖形結(jié)構(gòu)，可用字符串文法來處理。 空白基元：用來產(chǎn)生不連接的結(jié)構(gòu) 零點基元：表示頭和尾處于相同的位置 b：表示基元的頭尾反轉(zhuǎn)7.5 形式語言在圖形識別中的應(yīng)用7.5.3 圖形描述語言PDL 例子 生成式中無循環(huán)性 生成式中有循環(huán)性7.5 形式語言在圖形識別中的應(yīng)用7.5.3 圖形描述語言PDL 討論 采用句法模式識別，可以提供兩種或多種文法，并用每一種文法對不同模式樣本進行句法分析。 如果一個樣本能成功地被某一種文法所分析，便可歸為這一

46、類。 如果一個樣本對各種文法都得不到被成功分析的結(jié)果，則該文法被拒絕。7.5 形式語言在圖形識別中的應(yīng)用7.5.3 圖形描述語言PDL 例子作業(yè) 自己定義基元，用PDL文法生成0到5的字符，字符筆劃用七劃樣式。 提示：可參照例題中的基元定義7.5 形式語言在圖形識別中的應(yīng)用7.5.4 樹文法 如果一個圖形模式易于用樹的結(jié)構(gòu)來描述，則可采用樹文法。 它可將一維連接的符號串文法向多維推廣，是一種應(yīng)用較廣泛的高維文法。7.5 形式語言在圖形識別中的應(yīng)用7.5.4 樹文法 例子 對一個邊長為a, b和c的立方體，如果用一維字符串描述，有的邊會重復(fù)，用樹表示可直接分成三個叉，每條邊僅出現(xiàn)一次。7.5 形

47、式語言在圖形識別中的應(yīng)用7.5.4 樹文法 樹的定義：樹是具有一個或一個以上結(jié)點的有限集T，它具有以下性質(zhì)：(i)具有唯一的被指定為根的結(jié)點。(ii)其余的結(jié)點被分到m個不相交的集合T1,T2,Tm中，且這些子集的每一個又都是樹，稱為T的子樹。 從定義可以看出，樹的每個結(jié)點都是這個樹中所包含的某個子樹的根。 一個結(jié)點具有子樹的個數(shù)稱為該結(jié)點的秩。秩的相關(guān)定義 秩：一個結(jié)點的直接分支數(shù)定義為該結(jié)點的秩。 葉結(jié)點：秩為零的結(jié)點稱為葉結(jié)點（終端結(jié)點）。 分支結(jié)點：秩不為零的結(jié)點稱為分支結(jié)點（非終端結(jié)點）。7.5 形式語言在圖形識別中的應(yīng)用7.5.4 樹文法 討論 在計算機中數(shù)據(jù)的表示是有序的，所以子

48、樹的排列也是有一定的相對次序。 同一層上各子樹間相互交換位置就構(gòu)成不同的樹。 因此，樹是有序的。 比如前面的立方體，葉結(jié)點就是有序的。7.5 形式語言在圖形識別中的應(yīng)用7.5.4 樹文法 結(jié)論 用樹來描述圖形時，不但要知道樹的結(jié)點，還要知道與其相鄰結(jié)點的關(guān)系。 這里，相鄰結(jié)點的關(guān)系確定了基元與圖形的其它子結(jié)構(gòu)間的物理關(guān)系。7.5 形式語言在圖形識別中的應(yīng)用7.5.4 樹文法 秩的集合的表示 設(shè)X是結(jié)點符號的有窮集，a是結(jié)點的編號，(a)是結(jié)點a上的一棵樹，則(a)的秩的集合可用r(a)表示。 若(a)能夠具有的秩為r1,r2,rn，可寫成r(a)=r1,r2,rn 例子 樹的另一種表示法 圓括

49、號法 與左括號緊挨著的字母表示根。 其子樹是緊挨著根字母的一串左右成對的括號中的內(nèi)容。 例子7.5 形式語言在圖形識別中的應(yīng)用7.5.4 樹文法 樹文法的定義 上下文無關(guān)文法和樹文法的對應(yīng)關(guān)系 如果將樹用圓括號法表示，則上下文無關(guān)語言中的字符串和由樹文法生成的樹之間存在對應(yīng)關(guān)系。 描述 GT中的每一次推導(dǎo)，就用圓括號表示出了推導(dǎo)過程中生成式的使用次序，根據(jù)它可確定生成式的構(gòu)造。 例子作業(yè) 試用樹文法生成單位邊長的立方體，定義三個基元為立方體的三種方向的邊。7.6 句法分析 若對兩類模式進行分類，應(yīng)判別描述模式的字符串x是否可由文法G產(chǎn)生。 假若G能生成x，則x屬于1，否則x屬于2。 推廣到M類

50、模式，應(yīng)先確定M種文法，它能生成M類語言L(Gi)，i=1,2,M。 一個未知類別的模式字符串x，當(dāng)它是屬于L(Gi)中的一個句子，則x屬于i。 假如x不屬于任何一種語言，則它可被拒識，即x不被接受為M類中的任一類。7.6 句法分析 句法識別其原理圖7.6 句法分析 采用有限態(tài)自動機對未知模式進行識別，實質(zhì)上是對輸入字符串從左向右進行推導(dǎo)，判斷它是否為機器所接受。 這種識別方法計算工作量小，但是沒有對語法結(jié)構(gòu)進行分析。 在某些情況下，不僅需要判斷字符串是否屬于L(G)，還要知道它的語法結(jié)構(gòu)，以便改進文法，這就需要采用句法分析（句法剖析）。7.6 句法分析7.7.1 通過生成樹的句法分析 生成樹

51、構(gòu)造原則 已知一個句子x和文法G，若x是用上下文無關(guān)文法生成的，則其生成樹可用如下原則構(gòu)造： 把推導(dǎo)中出現(xiàn)的屬于VT的元素作為樹的葉，屬于VN的元素作為樹的結(jié)點，每一片葉和每一個結(jié)點都設(shè)置一個標(biāo)號。 將S作為樹根的標(biāo)號。 如果一個結(jié)點的后代子句中，至少有一個字符與它本身不同，則該結(jié)點的標(biāo)號必屬于VN 。 如果結(jié)點A有k個直接后代A1, A2, ,Ak，且它們是從左到右排列。則一定存在這樣一條生成式：A- A1A2Ak 。7.6 句法分析7.7.1 通過生成樹的句法分析 分析的兩種方法：“自上而下”和“自下而上” “自上而下”分析法是從G中的起始符S著手，應(yīng)用P中的生成式從左至右逐個代換非終止符

52、，以得到x。 “自下而上”分析法是從x本身著手，反方向使用生成式，尋找其中與某個生成式右側(cè)部分相同的字符子串，將它用生成式左邊的字符代換，直至最后達到起始符S。7.6 句法分析7.7.1 通過生成樹的句法分析 例子 分析a2b2c2 分析a2bc 自下而上 自上而下7.6 句法分析7.7.2 CKY(Cocke-Kasami-Younger)分析算法 采用樹結(jié)構(gòu)的分析算法實質(zhì)上是窮舉試探，它對任意上下文無關(guān)文法所需的分析時間，可能按字符串長度呈指數(shù)增長。 為此，采用CKY的分析算法，其時間為輸入串長度的三次方。7.6 句法分析7.7.2 CKY(Cocke-Kasami-Younger)分析算

53、法 問題描述 設(shè)描述某類模式的文法是上下文無關(guān)的，G=(VN,VT,P,S)，其生成式是喬姆斯基范式。 設(shè)輸入字符串x=a1a2an, |x|=n，要求設(shè)計CKY算法來判斷x是否屬于L(G)。 CKY算法的關(guān)鍵 構(gòu)表原則 構(gòu)表步驟7.6 句法分析7.7.2 CKY(Cocke-Kasami-Younger)分析算法 CKY算法實例7.6 句法分析7.7.3 最小距離誤差的句法校正分析 上面的識別過程并未考慮圖形模式的隨機干擾。 實際上，在獲取模式的基元描述時，由于隨機噪聲的干擾，可能發(fā)生部分的基元描述錯誤。 例：模式的正確描述字符串為abcbbc，受干擾后成為一有誤差的字符串a(chǎn)bbbbac。

54、為了識別這種存在某些誤差的串，在比較簡單的場合，可以采用通過計算最小距離誤差的校正句法分析。7.6 句法分析7.7.3 最小距離誤差的句法校正分析 字符串的相似性度量 字符串中的誤差通常歸納為三類：代換誤差、抹去誤差和插入誤差，可將它們用相應(yīng)的轉(zhuǎn)換式來表示。 代換誤差的轉(zhuǎn)換 抹去誤差的轉(zhuǎn)換 插入誤差的轉(zhuǎn)換 轉(zhuǎn)換距離 例子7.6 句法分析7.7.3 最小距離誤差的句法校正分析 誤差覆蓋文法的構(gòu)成 最小距離誤差的句法校正分析 設(shè)L(G)是一給定文法，y是一個給定的帶有誤差的句子，則最小距離誤差的句法校正分析實質(zhì)上就是在L(G)中找出x，使其滿足最小距離準(zhǔn)則。 d(x,y)的計算： 構(gòu)成一個誤差校正

55、程序的過程時，修改給定文法G，把它擴大為G，使得L(G)不僅包括L(G)，而且包括能生成具有上述三類誤差的所有可能的句子。 根據(jù)G對帶有誤差的句子進行分析，計算能產(chǎn)生三類誤差的生成式的最少應(yīng)用次數(shù)，從而求得關(guān)于最小距離的度量。 構(gòu)成誤差覆蓋文法G的過程7.6 句法分析7.7.3 最小距離誤差的句法校正分析 最近鄰分類 兩類模式 若已知兩類模式，分別用文法G1和G2來描述，其誤差覆蓋文法分別為G1和G2。對于一個待分類的輸入模式x，用最小距離誤差分析算法計算出它與L(G1)和L(G2)之間的距離分別為d(x, L(G1)和d(x, L(G2)。如果有d(x, L(G1)d(x,L(G2)，則x屬

56、于L(G1) ，否則x屬于L(G2)。 c類模式 對于c類模式情況，可對相應(yīng)的c個文法G1,G2,GL分別進行最小距離誤差校正句法分析，計算出待分類的輸入模式x和各類語言間的距離d(x,L(Gk)，k=1,2,c。若對于所有的ji，有d(x, L(Gi)d(x, L(Gj)，則x屬于L(Gi) 。ji 7.7 句法模式識別的隨機文法 在模式識別中，由于測量噪聲的影響以及對模式識別的特征可能缺乏全面的知識，使得被研究的過程存在著某種程度的不確定性，造成描述這類模式的語言的歧異性。 對于一個特定模式類產(chǎn)生的字符串，本來是由某一種文法說明的，但實際上除了該文法外還有其它文法也能產(chǎn)生該類中的字符串。

57、例子 由文法G1產(chǎn)生的語言L(G1)中有句子aaab，由文法G2產(chǎn)生的語言L(G2)中有句子baab。由于測量上的誤差，可能使aaab變成abab，也可能使baab變成abab。如果以此為訓(xùn)練樣本來推斷G1和G2，兩種語言L(G1)和L(G2)就變成相交的了。7.7 句法模式識別的隨機文法 為了解決這類問題，提出了用隨機語言的處理方法 對于一種語言L中的每一條字符串x，分配一個概率p(x)，它用來表征L的不確定性。 如果一個模式文法可能產(chǎn)生某些“不想要”的句子，就可分配以很小的概率。 “不想要”的句子是由噪聲產(chǎn)生的，并不真正代表該類中的模式。 把形式語言的概念推廣到隨機語言有兩種途徑 把文法的生成式隨機化 把識別裝置的狀態(tài)轉(zhuǎn)移條件隨機化7.7 句法模式識別的隨機文法7.7.1 隨機文法 定義 例子 由隨機文法GS生成隨機語言L