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

模式識別習(xí)題參考1-齊敏教材第6章PAGEPAGE10句法模式識別習(xí)題解答用鏈碼法描述5～9五個數(shù)字。20134567解：用弗利曼鏈碼表示，20134567解解圖6.1弗利曼鏈碼基元數(shù)字5~9的折線化和量化結(jié)果如解圖6.2所示：解解圖6.2數(shù)字5~9的折線化和量化結(jié)果各數(shù)字的鏈碼表示分別為：“5”的鏈碼表示為；“6”的鏈碼表示為；“7”的鏈碼表示為；“8”的鏈碼表示為；“9”的鏈碼表示為。定義所需基本基元，用PDL法描述印刷體英文大寫斜體字母“H”、“K”和“Z”。解：設(shè)基元為：bbcade用PDL法得到“H”的鏈描述為；“K”的鏈描述為；“Z”的鏈描述為。設(shè)有文法，，和P分別為，①，②，③，④⑤，⑥，⑦，⑧①⑦②③①①⑦②③①⑥②③①⑦①⑥②④①⑥②④②③解：以上句子ab，abba，abab，ba，baab，baba均屬于。設(shè)有文法，其中，，P的各生成式為①，②，③6.7設(shè)文法，其中，，P的各生成式為①，②，③④，⑤，⑥，⑦設(shè)待識別鏈，試用填充樹圖法的頂下法分析x是否屬于?解：(1)從S開始考察P中的①、②、③式：若選①，則結(jié)果為x=1，排除；若選②，導(dǎo)出的x末位必為1，與題不符，排除；S1BA0A0S1BA0A00AS1BA0A0AS1BA0AS1BASB(a)(b)(c)(d)(e)解解圖6.4填充樹圖過程(2)填充目標(biāo)為B，考察④、⑤均可填充，先試④，如解圖6.4(b)所示。若不行，再返回用⑤式。(3)此時填充目標(biāo)為A，考察⑥、⑦。若選⑥，導(dǎo)出的x為2位，與題不符，排除。選⑦式，如解圖6.4(c)所示。(4)類似地，得到圖6.4所示各步結(jié)果，樹葉為1000。故x屬于。6.8設(shè)上下文無關(guān)文法，，，P中生成式的喬姆斯基范式為，，，，，用CYK分析法分析鏈?zhǔn)欠駷樵撐姆ǖ暮戏ň渥?。解：待識別鏈為5位，構(gòu)造5行5列的三角形分析表，如解圖6.5所示。解解圖6.5分析表t14t13t12t11t23t22t21t32t31t41t15t51t42t33t24求表中元素的值：(1)令，求，。各子鏈為0，1，0，0，1。對于，；對于，；對于，；對于，。對于，。(2)令，求，。各子鏈為01，10，00，01。對于，因有和，，，故；對于，有，，，故。對于，有，，，故。對于，有和，，，故；(3)令，求，。各子鏈為010，100，001。對于，因有，，；和，，。故。類似地有，，，，。填表結(jié)果如解圖6.6所示。解解圖6.6CYK分析表填表結(jié)果C,SC,SCSCSSCCC,SSC,SC,SC,SC,S因為S在中，所以。6.9已知正則文法，其中，，P的各生成式為，，，構(gòu)成對應(yīng)的有限態(tài)自動機(jī)，畫出自動機(jī)的狀態(tài)轉(zhuǎn)換圖。解：設(shè)有限態(tài)自動機(jī)，由A與G的對應(yīng)關(guān)系得：由，有；由，有；由，有。故有限態(tài)自動機(jī)為，，：，，abSBFaabSBFaa解解圖6.7自動機(jī)的狀態(tài)轉(zhuǎn)換圖6.10已知有限態(tài)自動機(jī)，其中，，A的狀態(tài)轉(zhuǎn)換圖如圖6.15所示，求A對應(yīng)的正則文法G。圖6.15狀態(tài)轉(zhuǎn)換圖圖6.15狀態(tài)轉(zhuǎn)換圖11000011解：設(shè)正則文法為，由G與A的對應(yīng)關(guān)系得：；；；根據(jù)狀態(tài)轉(zhuǎn)換圖有：P：因，有；因，有；因，有；而，故；因，有；因，有；因，有；而，故；因，有；因，有。由此得正則文法為，，P：，，，，，，6.11已知上下文無關(guān)文法，其中，P的各生成式為，，寫出文法G的格雷巴赫范式，構(gòu)成相應(yīng)的下推自動機(jī)。解：文法的格雷巴赫范式為：，P：，，，