模式識(shí)別習(xí)題參考1-齊敏教材第6章

句法模式識(shí)別習(xí)題解答用鏈碼法描述5～9五個(gè)數(shù)字。20134567解：用弗利曼鏈碼表示，20134567解解圖6.1弗利曼鏈碼基元數(shù)字5~9的折線化和量化結(jié)果如解圖6.2所示：解解圖6.2數(shù)字5~9的折線化和量化結(jié)果各數(shù)字的鏈碼表示分別為：“5”的鏈碼表示為；“6”的鏈碼表示為；“7”的鏈碼表示為；“8”的鏈碼表示為；“9”的鏈碼表示為。定義所需根本基元，用PDL法描述印刷體英文大寫(xiě)斜體字母“H”、“K”和“Z”。解：設(shè)基元為：bbcade用PDL法得到“H”的鏈描述為；“K”的鏈描述為；“Z”的鏈描述為。設(shè)有文法，，和P分別為，①，②，③，④⑤，⑥，⑦，⑧①⑦②③①①⑦②③①⑥②③①⑦①⑥②④①⑥②④②③解：以上句子ab，abba，abab，ba，baab，baba均屬于。設(shè)有文法，其中，，P的各生成式為①，②，③④，⑤，⑥⑦，⑧，⑨，⑩問(wèn)是否屬于語(yǔ)言？⑦⑧⑤④①解：由⑦⑧⑤④①可知屬于語(yǔ)言。寫(xiě)出能產(chǎn)生圖示樹(shù)的擴(kuò)展樹(shù)文法，設(shè)基元a，b分別為“→”和“↓”，它所描述的模式是什么？aa$ababaaababA3⑵⑴A4AA3⑵⑴A4A2⑶A5A5⑷⑸A9A6(6)A7(6)A7⑻A8⑺⑾A12⑿⑾A12⑿⑼A10⑽A112.檢查非終止符的等價(jià)性。查得。刪除和及其后代生成式，其余生成式中的和用代替，合并后得到⑸⑸A9A6A5⑷(6)A2⑼A10⑽A2⑴A4A2A3⑵⑶A4A23.建立起始產(chǎn)生式。將⑴中的用SA4A2設(shè)推斷的擴(kuò)展樹(shù)文法為，由以上推斷得：，，，，⑸A9⑸A9A6A5⑷(6)A2⑼A10⑽A2⑴A4A2A3⑵⑶aabbbbaaaaaabbbbaaaaa$它所描述的模式如解圖6.3所示：解圖6.3描述的模式解圖6.3描述的模式6.6的正樣本集，試推斷出余碼文法。解：設(shè)余碼文法為。(1)由得的終止符集。(2)求的全部余碼，組成非終止符集。的全部余碼為，，，，，，，，等號(hào)右邊相同的合并，非空余碼標(biāo)以符號(hào)組成非終止符集：，，，，所以。(3)建立生成式集P。由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；所以余碼文法為，P：，，，，，，，6.7設(shè)文法，其中，，P的各生成式為①，②，③④，⑤，⑥，⑦設(shè)待識(shí)別鏈，試用填充樹(shù)圖法的頂下法分析x是否屬于?解：(1)從S開(kāi)始考察P中的①、②、③式：假設(shè)選①，那么結(jié)果為x=1，排除；假設(shè)選②，導(dǎo)出的x末位必為1，與題不符，排除；S1BA0A0S1BA0A00AS1BA0A0AS1BA0AS1BASB(a)(b)(c)(d)(e)解解圖6.4填充樹(shù)圖過(guò)程(2)填充目標(biāo)為B，考察④、⑤均可填充，先試④，如解圖6.4(b)所示。假設(shè)不行，再返回用⑤式。(3)此時(shí)填充目標(biāo)為A，考察⑥、⑦。假設(shè)選⑥，導(dǎo)出的x為2位，與題不符，排除。選⑦式，如解圖6.4(c)所示。(4)類(lèi)似地，得到圖6.4所示各步結(jié)果，樹(shù)葉為1000。故x屬于。6.8設(shè)上下文無(wú)關(guān)文法，，，P中生成式的喬姆斯基范式為，，，，，用CYK分析法分析鏈?zhǔn)欠駷樵撐姆ǖ暮戏ň渥印＝猓捍R(shí)別鏈為5位，構(gòu)造5行5列的三角形分析表，如解圖6.5所示。解解圖6.5分析表t14t13t12t11t23t22t21t32t31t41t15t51t42t33t24求表中元素的值：(1)令，求，。各子鏈為0，1，0，0，1。對(duì)于，；對(duì)于，；對(duì)于，；對(duì)于，。對(duì)于，。(2)令，求，。各子鏈為01，10，00，01。對(duì)于，因有和，，，故；對(duì)于，有，，，故。對(duì)于，有，，，故。對(duì)于，有和，，，故；(3)令，求，。各子鏈為010，100，001。對(duì)于，因有，，；和，，。故。類(lèi)似地有，，，，。填表結(jié)果如解圖6.6所示。解解圖6.6CYK分析表填表結(jié)果C,SC,SCSCSSCCC,SSC,SC,SC,SC,S因?yàn)镾在中，所以。6.9正那么文法，其中，，P的各生成式為，，，構(gòu)成對(duì)應(yīng)的有限態(tài)自動(dòng)機(jī)，畫(huà)出自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖。解：設(shè)有限態(tài)自動(dòng)機(jī)，由A與G的對(duì)應(yīng)關(guān)系得：由，有；由，有；由，有。故有限態(tài)自動(dòng)機(jī)為，，：，，abSBFaabSBFaa解解圖6.7自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換圖6.10有限態(tài)自動(dòng)機(jī)，其中，，A的狀態(tài)轉(zhuǎn)換圖如圖6.15所示，求A對(duì)應(yīng)的正那么文法G。圖6.15狀態(tài)轉(zhuǎn)換圖圖6.15狀態(tài)轉(zhuǎn)換圖11000011解：設(shè)正那么文法為，由G與A的對(duì)應(yīng)關(guān)系得：；；；根據(jù)狀態(tài)轉(zhuǎn)換圖有：P：因，有；因，有；因，有；而，故；因，有；因，有；因，有；而，故；因，有；因，有。由此得正那么文法為，，P：，，，，，，6.11上下文無(wú)關(guān)文法，其中，P的各生成式為，，寫(xiě)出文法G的格