模式识别习题参考1-齐敏教材第6章.doc

句法模式识别****题解答用链码法描述5~9五个数字。20134567解:用弗利曼链码表示,:~:~9的折线化和量化结果各数字的链码表示分别为:“5”的链码表示为;“6”的链码表示为;“7”的链码表示为;“8”的链码表示为;“9”的链码表示为。定义所需基本基元,用PDL法描述印刷体英文大写斜体字母“H”、“K”和“Z”。解:设基元为:bcade用PDL法得到“H”的链描述为;“K”的链描述为;“Z”的链描述为。设有文法,,和P分别为,①,②,③,④⑤,⑥,⑦,⑧①⑦②③①⑥②③①⑦①⑥②④①⑥②④②③写出三个属于的句子。解:以上句子ab,abba,abab,ba,baab,baba均属于。设有文法,其中,,P的各生成式为①,②,③④,⑤,⑥⑦,⑧,⑨,⑩问是否属于语言?⑦⑧⑤④①解:由可知属于语言。写出能产生图示树的扩展树文法,设基元a,b分别为“→”和“↓”,它所描述的模式是什么?a$ababaaababA3⑵⑴A4A2⑶解::A5⑷⑸A9A6(6)A7⑻A8⑺⑾A12⑿⑼A10⑽。查得。删除和及其后代生成式,其余生成式中的和用代替,合并后得到⑸A9A6A5⑷(6)A2⑼A10⑽A2⑴A4A2A3⑵⑶。将⑴中的用S代替得到:设推断的扩展树文法为,由以上推断得:,,,,⑸A9A6A5⑷(6)A2⑼A10⑽A2⑴A4A2A3⑵⑶P的各生成式为aabbbbaaaaa$当基元a,b分别为“→”和“↓”时,:,试推断出余码文法。解:设余码文法为。(1)由得的终止符集。(2)求的全部余码,组成非终止符集。的全部余码为,,,,,,,,等号右边相同的合并,非空余码标以符号组成非终止符集:,,,,所以。(3)建立生成式集P。由,有生成式;由,有生成式;由,有生成式;由,有生成式;由,有生成式;由,有生成式;由,有生成式;由,有生成式;由,有生成式;所以余码文法为,P:,,,,,,,,其中,,P的各生成式为①,②,③④,⑤,⑥,⑦设待识别链,试用填充树图法的顶下法分析x是否属于?解:(1)从S开始考察P中的①、②、③式:若选①,则结果为x=1,排除;若选②,导出的x末位必为1,与题不符,排除;S1BA0A00AS1BA0A0AS1BA0AS1BASB(a)(b)(c)(d)(e)选③式,(a)所示。(2)填充目标为B,考察④、⑤均可填充,先试④,(b)所示。若不行,再返回用⑤式。(3)此时填充目标为A,考察⑥、⑦。若选⑥,导出的x为2位,与题不符,排除。选⑦式,(c)所示。(4)类似地,,树叶为1000。故x属于。,,,P中生成式的乔姆斯基范式为,,,,,用CYK分析法分析链是否为该文法的合法句子。解:待识别链为5位,构造5行5列的三角形分析表,。:(1)令,求,。各子