下推自動(dòng)機(jī)與上下文無(wú)關(guān)文法的對(duì)應(yīng)關(guān)系課件

1、第6章 6.1 句法模式識(shí)別概述6.2 形式語(yǔ)言的基本概念6.3 模式的描述方法6.4 文法推斷6.5 句法分析6.6 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別第6章 句法模式識(shí)別6.1 句法模式識(shí)別概述模式用句子形式描述，結(jié)構(gòu)信息十分重要。 模式子模式基元句子詞組單詞組合關(guān)系自然語(yǔ)言的文法 句法模式識(shí)別用小而簡(jiǎn)單的基元與語(yǔ)法規(guī)則描述和識(shí)別大而復(fù)雜的模式，通過(guò)對(duì)基元的識(shí)別，進(jìn)而識(shí)別子模式，最終識(shí)別復(fù)雜模式。 符合某個(gè)文法的所有句子的集合一個(gè)模式類（b）墻壁 f地板 gEDBbadce（c）圖6.1 景物結(jié)構(gòu)描述與英文句子句法描述的對(duì)比句法模式識(shí)別系統(tǒng)的組成： 句法模式識(shí)別的理論基礎(chǔ)：形式語(yǔ)言 20世紀(jì)50年代中期

2、喬姆斯基（Chomsky）。 * 基元選擇尚無(wú)通用的方法；* 文法推斷理論遠(yuǎn)不及統(tǒng)計(jì)學(xué)習(xí)發(fā)展得成熟。 句法模式識(shí)別存在的主要問(wèn)題：6.2 形式語(yǔ)言的基本概念6.2.1 基本定義1字母表與問(wèn)題有關(guān)的符號(hào)的有限集合，用V或表示。 2句子 由字母表中符號(hào)組成的有限長(zhǎng)度的符號(hào)串，又稱鏈?？站溆帽硎?。 組成：英文小寫(xiě)字母、數(shù)字。例：由 中元素可組成句子： 例：abc，aacc，重寫(xiě)次數(shù)句子的長(zhǎng)度：句子包含符號(hào)的數(shù)目，用|表示。3語(yǔ)言由字母表中的符號(hào)根據(jù)某種文法組成的句子的集合。 V *：V中符號(hào)組成的所有句子的集合，包括空句；V +：不包含空句的句子集合。 例：4文法構(gòu)成一種語(yǔ)言的句子所必須遵守的規(guī)則。

3、 VN ：非終止符的有限集，子模式的集合，大寫(xiě)字母表示。 VT ：終止符有限集，基元的集合，字母表起始部分的小寫(xiě) 字母表示 。終止符和非終止符組成的混合字符串：用英文字母表尾部的小寫(xiě)字母x，y，v，w等表示。終止符組成的字符串：用希臘字母，等表示。性質(zhì)： （字母表）（空集）P：生成式的有限集。用文法產(chǎn)生句子時(shí)的重寫(xiě)規(guī)則。字符串 字符串 替換 S：起始符，代表模式本身，特殊的非終止符。用生成式構(gòu)成句子時(shí)，必須由左邊是S的生成式開(kāi)始。 一種語(yǔ)言有一種文法，由文法G構(gòu)成的語(yǔ)言用L(G)表示： 文法G構(gòu)成的句子由終止符組成VT中字符組成的所有句子的集合 文法G的推導(dǎo)關(guān)系 利用文法構(gòu)成句子時(shí)，除第一個(gè)生

4、成式必須利用左邊為起始符 S 的生成式外，其余生成式使用的先后次序及重復(fù)使用的次數(shù)都不受限制。是說(shuō)明：解：6.2.2 文法分類四種類型：0型文法、1型文法、2型文法和3型文法。10型文法：無(wú)約束文法。P：其中， ， 。21型文法：上下文有關(guān)文法 。含意： 32型文法：上下文無(wú)關(guān)文法 。解：每個(gè)生成式的左邊都是單變量，右邊是非空字符串， 故G是上下文無(wú)關(guān)文法。 屬于L(G)的句子： 結(jié)果不唯一。 43型文法：正則文法、有限態(tài)文法。 是 后一種文法的限制比前一種文法的限制嚴(yán)格；限制愈多的文法愈容易推斷；句法模式識(shí)別中多采用上下文無(wú)關(guān)文法和正則文法。6.3 模式的描述方法6.3.1 基元的確定根據(jù)結(jié)

5、構(gòu)特征對(duì)模式進(jìn)行描述。 結(jié)構(gòu)描述法，又稱句法表示法。 模式的表示：鏈表示法、樹(shù)表示法、圖表示法。 對(duì)應(yīng)的文法：鏈文法（串文法）、樹(shù)文法、圖文法。 還有網(wǎng)文法、陣列文法等。 目前關(guān)于基元的確定沒(méi)有一個(gè)通用的解決辦法?；倪x擇遵循兩個(gè)基本原則。 1基元應(yīng)是模式的基本單元，能夠通過(guò)一定的結(jié)構(gòu)關(guān)系對(duì)數(shù) 據(jù)進(jìn)行緊湊、方便地描述。2基元應(yīng)該容易用現(xiàn)有的非句法方法進(jìn)行提取或識(shí)別。例如：語(yǔ)音識(shí)別中 音素； 識(shí)別手寫(xiě)文字 筆劃。6.3.2 模式的鏈表示法1鏈碼法鏈碼：用不同斜率的直線段或曲線段為基元表示圖形模式。弗利曼鏈碼： 以八個(gè)基本方向的有向線段為基元，用07八個(gè)數(shù)字符號(hào)表示。 用字符表示基元后，被描述的

6、圖形表示成的字符串。 弗利曼鏈碼基元 數(shù)字“2”的折線化和量化結(jié)果編碼： 矩形網(wǎng)格覆蓋； 折線化和量化；形成鏈碼(有序結(jié)構(gòu))。例：“2”的鏈碼表示為2圖形描述語(yǔ)言法簡(jiǎn)稱PDL（Picture Description Language，PDL）。 基本基元：有向線段(直線段、弧線段) 。由 “頭(箭頭端)” 和 “尾” 構(gòu)成。關(guān)系基元：表示基元之間連接關(guān)系的算子。頭尾相接 頭頭相接 尾尾相接 頭頭 且尾尾相接頭尾顛倒 （）組合關(guān)系(配合使用)例：用PDL法表示大寫(xiě)英文字母A。(a+b)(a+b)*c)(a+b)*c)+b)(a+(a+b)*c)+b)鏈表示法：只能從左邊或右邊與其它符號(hào)相連，一維

7、連接方式。 6.3.3 模式的樹(shù)表示法高維表示法。 1樹(shù)的定義樹(shù)T是一個(gè)或一個(gè)以上結(jié)點(diǎn)的有限集合，并且滿足：1）存在一個(gè)唯一的指定為根的結(jié)點(diǎn)；2）其余結(jié)點(diǎn)分為m個(gè)不相交的集合T1，T2，Tm，其中 每一個(gè)集合本身都是一個(gè)樹(shù)，稱為T(mén)的子樹(shù)。同一層上各子樹(shù)交換位置構(gòu)成的樹(shù)不同。樹(shù)的有序性：一個(gè)結(jié)點(diǎn)具有子樹(shù)的個(gè)數(shù)，結(jié)點(diǎn)a的秩記為 r(a) 。葉結(jié)點(diǎn)的秩為零。 秩：長(zhǎng)方體 基元 樹(shù)結(jié)構(gòu)描述 結(jié)點(diǎn)a的秩可能是2，l或0。例：結(jié)點(diǎn)a可能有2，1或0個(gè)分枝樹(shù)文法定義為四元式2樹(shù)文法字母表 以字母表中字母為根結(jié)點(diǎn)的樹(shù)的秩 起始樹(shù)的有限集 生成式的有限集由樹(shù)文法Gt產(chǎn)生的語(yǔ)言L(Gt)是一些樹(shù)的集合即模式集：

8、所有結(jié)點(diǎn)都是終止符的樹(shù)的集合樹(shù)T由S中的起始樹(shù)Ti開(kāi)始，用文法Gt的生成式逐步導(dǎo)出圖6.7 模式的樹(shù)狀表示解：生成式 中右邊的樹(shù)分別用T1，T2 ，T3表示。有 試判斷圖6.7所示的樹(shù)是否屬于L(Gt)的一個(gè)句子。3擴(kuò)展樹(shù)文法其中，P中生成式 形式：一個(gè)樹(shù)文法有一個(gè)對(duì)應(yīng)的擴(kuò)展樹(shù)文法。例6.6 構(gòu)成例6.5中樹(shù)文法對(duì)應(yīng)的擴(kuò)展樹(shù)文法。6.4 文法推斷6.4.1 基本概念文法推斷：用已知類別的模式樣本集訓(xùn)練類別文法的過(guò)程。統(tǒng)計(jì)模式識(shí)別訓(xùn)練判別函數(shù) 句法模式識(shí)別訓(xùn)練類別文法 目的：構(gòu)造出能正確描述某類模式的文法，其中主要是求 生成式集合P。 * 選擇文法形式（鏈文法、樹(shù)文法、圖文法）。 * 根據(jù)樣本進(jìn)

9、行推斷文法。 基本步驟：1語(yǔ)言L(G)的正樣本集和負(fù)樣本集2文法推斷的基本思路根據(jù)樣本集RR+，R-推導(dǎo)出文法G，簡(jiǎn)化時(shí)只有R+ 。* 給定一個(gè)R+型的訓(xùn)練樣本集，共n個(gè)句子，陸續(xù)送入 一個(gè) “文法推斷機(jī)”。* 輸入一個(gè)句子，由此初步推斷出一個(gè)能導(dǎo)生出該句子 的文法G1。* 輸入第二個(gè)句子，補(bǔ)充或修改G1，從而推斷出能導(dǎo)生 出這兩個(gè)句子的文法G2。* 推斷出文法Gn。* 將Gn中各條文做合并處理。* 先推斷出幾種不同的文法，然后再選擇一種。簡(jiǎn)化文法的方法：6.4.2 余碼文法的推斷1余碼的定義2余碼文法的推斷余碼文法又稱形式微商文法。 6.4.3 擴(kuò)展樹(shù)文法的推斷 第三步：合并等價(jià)非終止符，刪

10、除被合并的非終止符的所有后代生成式。例6.8 設(shè)某類句法模式樹(shù)描述的樣本集中含有樹(shù)T1和T2： 解：第一步：分別寫(xiě)出產(chǎn)生樹(shù)T1和T2的生成式。產(chǎn)生樹(shù)T1的生成式：增加一個(gè)，得到產(chǎn)生樹(shù)T2的生成式： 6.5 句法分析6.5.1 參考鏈匹配法利用文法對(duì)未知類別的句法模式進(jìn)行識(shí)別或分類的過(guò)程。句法分析：* 對(duì)每一類模式給出一組樣本鏈(參考鏈)。 設(shè)有M類模式。* 將輸入鏈x與每一類的參考鏈進(jìn)行比較，并規(guī)定一個(gè)比較容 限。 x被識(shí)別為與其匹配“最好”的參考鏈所屬的模式類。 6.5.2 填充樹(shù)圖法用于上下文無(wú)關(guān)文法的分析。 若已知某語(yǔ)言的文法Gi，給定某待識(shí)別的鏈x，建立一個(gè)以x為底，以起始符S為頂?shù)娜?/p>

11、角形，如圖6.8所示。 用文法Gi的生成式填充這個(gè)三角形，使之成為一個(gè)分析樹(shù)。若填充成功，表示x可以由文法Gi導(dǎo)出， 圖6.8 待填充的三角形 填充三角形的方法： 頂下法 底上法 解：填充三角形成功， 圖6.9 用文法G的生成式填充的三角形6.5.3 CYK分析法庫(kù)克(Cocke) -楊格(Younger) -卡塞米(Kasami)分析法用于上下文無(wú)關(guān)文法的分析1喬姆斯基范式 要求：生成式必須表示為喬姆斯基范式。 或其中A，B，C為非終止符，a為終止符。 例如，喬姆斯基范式為2CYK分析法輸入：?jiǎn)棠匪够妒降纳舷挛臒o(wú)關(guān)文法G、輸入鏈x；輸出：關(guān)于鏈x的分析表。關(guān)鍵：構(gòu)造x的分析表 方法：步驟：

12、 第五步：停機(jī)，填表結(jié)束。 6.5.4 厄利分析法一種有效的上下文無(wú)關(guān)文法的分析算法。 圓點(diǎn)：分割開(kāi)經(jīng)分析后符合的部分和尚未考慮的部分。 思路： 步驟： 反復(fù)執(zhí)行2和3，到?jīng)]有新項(xiàng)目加入I0為止。反復(fù)執(zhí)行5和6，到?jīng)]有項(xiàng)目加到Ij中為止。解： 6.6 句法結(jié)構(gòu)的自動(dòng)機(jī)識(shí)別自動(dòng)機(jī)：句法模式識(shí)別器。識(shí)別輸入鏈?zhǔn)欠穹吓c該機(jī)相對(duì)應(yīng)的文法。 0型文法圖靈機(jī)1型文法線性有界自動(dòng)機(jī)2型文法下推自動(dòng)機(jī)3型文法有限態(tài)自動(dòng)機(jī)每類文法對(duì)應(yīng)一類自動(dòng)機(jī)： 鏈文法： 樹(shù)文法樹(shù)自動(dòng)機(jī)。 其他：1有限態(tài)自動(dòng)機(jī)6.6.1 有限態(tài)自動(dòng)機(jī)與正則文法輸入字母表 內(nèi)部狀態(tài)有限集狀態(tài)轉(zhuǎn)換規(guī)則 初始狀態(tài) 終止?fàn)顟B(tài)集 自動(dòng)機(jī)每次從一個(gè)狀態(tài)

13、只能轉(zhuǎn)換到另一個(gè)指定的狀態(tài)。確定的有限態(tài)自動(dòng)機(jī)：非確定的有限態(tài)自動(dòng)機(jī)： 自動(dòng)機(jī)每次從一個(gè)狀態(tài)可以轉(zhuǎn)換到一個(gè)指定狀態(tài)集中的任意一狀態(tài)。如： 2有限態(tài)自動(dòng)機(jī)接受語(yǔ)言的方式有限態(tài)自動(dòng)機(jī)接受的語(yǔ)言：指有限態(tài)自動(dòng)機(jī)接受的鏈x的集合，記為L(zhǎng)(A)。 結(jié)構(gòu)：* x中的字符從左到右依次記錄在輸入帶上。 工作方式：* 只讀頭從輸入帶的最左邊一個(gè)單元開(kāi)始依次讀取輸入字符。 * 每讀取一個(gè)字符，狀態(tài)控制器搜尋原存入的狀態(tài)轉(zhuǎn)換規(guī)則， 接受/拒絕這個(gè)字符。 * 如果自動(dòng)機(jī)連續(xù)地接受輸入鏈的每個(gè)字符，最后停在一個(gè)終 止?fàn)顟B(tài)上，則稱輸入鏈屬于該自動(dòng)機(jī)能接受的那種語(yǔ)言，即 解：將鏈x輸入自動(dòng)機(jī)A，狀態(tài)轉(zhuǎn)換過(guò)程為狀態(tài)轉(zhuǎn)換圖：狀

14、態(tài) 終止態(tài) 進(jìn)入箭頭 狀態(tài)變化狀態(tài)變化方向3有限態(tài)自動(dòng)機(jī)與正則文法的對(duì)應(yīng)狀態(tài)1）按正則文法構(gòu)造有限態(tài)自動(dòng)機(jī)A和G的對(duì)應(yīng)關(guān)系：正則文法的生成式 * 由正則文法G構(gòu)成對(duì)應(yīng)的有限態(tài)自動(dòng)機(jī)A；應(yīng)用：若將非終止符Ai，Aj分別命名為qi，qj：A接受鏈x的過(guò)程為：2）按有限態(tài)自動(dòng)機(jī)確定正則文法對(duì)應(yīng)關(guān)系：若將qi，qj分別命名為Ai，Aj：6.6.2 下推自動(dòng)機(jī)與上下文無(wú)關(guān)文法1下推自動(dòng)機(jī)有限態(tài)自動(dòng)機(jī)的限制：下推自動(dòng)機(jī)(PDA)：有限態(tài)自動(dòng)機(jī)+下推存儲(chǔ)器只能接受正則文法產(chǎn)生的語(yǔ)言，不能接受上下文無(wú)關(guān)文法產(chǎn)生的語(yǔ)言?？勺R(shí)別上下文無(wú)關(guān)文法產(chǎn)生的句子。結(jié)構(gòu)： * 初始狀態(tài)q0：棧頂為最初的非終止符；* 只讀頭讀取輸入帶字符：輸入鏈中的終止符和棧頂?shù)姆墙K止 符共同決定自動(dòng)機(jī)狀態(tài)的轉(zhuǎn)換；* 狀態(tài)轉(zhuǎn)換同時(shí)，棧頂內(nèi)容發(fā)生變化。* 自動(dòng)機(jī)內(nèi)部狀態(tài)處于終止態(tài)或堆棧變空時(shí)，稱輸入鏈被自動(dòng) 機(jī)接受（識(shí)別）了。下推自動(dòng)機(jī)定義： 有限態(tài)自動(dòng)機(jī)加Z0和下推符號(hào)有限集最初處于棧頂?shù)姆墙K止符內(nèi)部狀態(tài)轉(zhuǎn)換和棧頂內(nèi)容改變的規(guī)則 規(guī)則 ：討論：* 為單個(gè)非終止符。