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

第5章 句法模式识别习题解答6.1 用链码法描述59五个数字。20134567解：用弗利曼链码表示，基元如解图6.1所示：解图6.1 弗利曼链码基元数字59的折线化和量化结果如解图6.2所示： 解图6.2 数字59的折线化和量化结果各数字的链码表示分别为：“5”的链码表示为；“6”的链码表示为；“7”的链码表示为；“8”的链码表示为；“9”的链码表示为。6.2 定义所需基本基元，用PDL法描述印刷体英文大写斜体字母“H”、“K”和“Z”。解：设基元为：bcade用PDL法得到“H”的链描述为；“K”的链描述为；“Z”的链描述为。6.3 设有文法，和P分别为， ，写出三个属于的句子。解：以上句子ab，abba，abab，ba，baab，baba均属于。6.4 设有文法，其中，P的各生成式为，问是否属于语言？解：由可知属于语言。6.5 写出能产生图示树的扩展树文法，设基元a，b分别为“”和“”，它所描述的模式是什么？ a$ababaaababA3A4A2解：1. 写出生成树的扩展树文法生成式集：A5A9A6(6)A7A8A12A10A112. 检查非终止符的等价性。查得。删除和及其后代生成式，其余生成式中的和用代替，合并后得到A9A6A5(6)A2A10A2A4A2A3A4A23. 建立起始产生式。将中的用S代替得到： 设推断的扩展树文法为，由以上推断得：，A9A6A5(6)A2A10A2A4A2A3P的各生成式为aabbbbaaaaa$ 当基元a，b分别为“”和“”时，它所描述的模式如解图6.3所示：解图6.3 描述的模式6.6 已知的正样本集，试推断出余码文法。解：设余码文法为。(1) 由得的终止符集。(2) 求的全部余码，组成非终止符集。的全部余码为， ， ，等号右边相同的合并，非空余码标以符号组成非终止符集：，所以。(3) 建立生成式集P。由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；所以余码文法为 ， P：， ，6.7 设文法，其中，P的各生成式为，设待识别链，试用填充树图法的顶下法分析x是否属于?解：(1) 从S开始考察P中的、式：若选，则结果为x=1，排除；若选，导出的x末位必为1，与题不符，排除；S1BA0A00AS1BA0A0AS1BA0AS1BASB(a) (b) (c) (d) (e) 选式，如解图6.4(a)所示。解图6.4 填充树图过程(2) 填充目标为B，考察、均可填充，先试，如解图6.4(b)所示。若不行，再返回用式。(3) 此时填充目标为A，考察、。若选，导出的x为 2位，与题不符，排除。选式，如解图6.4(c)所示。(4) 类似地，得到图6.4所示各步结果，树叶为1000。 故x属于。6.8 设上下文无关文法，P中生成式的乔姆斯基范式为，用CYK分析法分析链是否为该文法的合法句子。解：待识别链为5位，构造5行5列的三角形分析表，如解图6.5所示。解图6.5 分析表t14t13t12t11t23t22t21t32t31t41t15t51t42t33t24 求表中元素的值：(1) 令，求，。 各子链为0，1，0，0，1。 对于，； 对于，； 对于，； 对于，。 对于，。(2) 令，求，。各子链为01，10，00，01。对于，因有和，故；对于，有，故。对于，有，故。对于，有和，故；(3) 令，求，。各子链为010，100，001。对于，因有，；和，。故。类似地有，。填表结果如解图6.6所示。解图6.6 CYK分析表填表结果C,SC,SCSCSSCCC,SSC,SC,SC,SC,S 因为S在中，所以。6.9 已知正则文法，其中，P的各生成式为，构成对应的有限态自动机，画出自动机的状态转换图。解：设有限态自动机，由A与G的对应关系得：由，有；由，有； 由，有。故有限态自动机为，：，abSBFaa状态转换图如解图6.7所示：解图 6.7 自动机的状态转换图6.10 已知有限态自动机，其中，A的状态转换图如图6.15所示，求A对应的正则文法G。图6.15 状态转换图11000011解：设正则文法为，由G与A的对应关系得：；根据状态转换图有：P：因，有； 因，有；因，有；而，故；因，有；因，有；因，有；而，故；因，有；因，有。由此得正则文法为，P：， ，6.11 已知上下文无关文法，其中，P的各生成式为，写出文法G的格雷