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

句法模式识别习题解答用链码法描述5～9五个数字。20134567解：用弗利曼链码表示，20134567解解图6.1弗利曼链码基元数字5~9的折线化和量化结果如解图6.2所示：解解图6.2数字5~9的折线化和量化结果各数字的链码表示分别为：“5”的链码表示为；“6”的链码表示为；“7”的链码表示为；“8”的链码表示为；“9”的链码表示为。定义所需根本基元，用PDL法描述印刷体英文大写斜体字母“H”、“K”和“Z”。解：设基元为：bbcade用PDL法得到“H”的链描述为；“K”的链描述为；“Z”的链描述为。设有文法，，和P分别为，①，②，③，④⑤，⑥，⑦，⑧①⑦②③①①⑦②③①⑥②③①⑦①⑥②④①⑥②④②③解：以上句子ab，abba，abab，ba，baab，baba均属于。设有文法，其中，，P的各生成式为①，②，③④，⑤，⑥⑦，⑧，⑨，⑩问是否属于语言？⑦⑧⑤④①解：由⑦⑧⑤④①可知属于语言。写出能产生图示树的扩展树文法，设基元a，b分别为“→”和“↓”，它所描述的模式是什么？aa$ababaaababA3⑵⑴A4AA3⑵⑴A4A2⑶A5A5⑷⑸A9A6(6)A7(6)A7⑻A8⑺⑾A12⑿⑾A12⑿⑼A10⑽A112.检查非终止符的等价性。查得。删除和及其后代生成式，其余生成式中的和用代替，合并后得到⑸⑸A9A6A5⑷(6)A2⑼A10⑽A2⑴A4A2A3⑵⑶A4A23.建立起始产生式。将⑴中的用SA4A2设推断的扩展树文法为，由以上推断得：，，，，⑸A9⑸A9A6A5⑷(6)A2⑼A10⑽A2⑴A4A2A3⑵⑶aabbbbaaaaaabbbbaaaaa$它所描述的模式如解图6.3所示：解图6.3描述的模式解图6.3描述的模式6.6的正样本集，试推断出余码文法。解：设余码文法为。(1)由得的终止符集。(2)求的全部余码，组成非终止符集。的全部余码为，，，，，，，，等号右边相同的合并，非空余码标以符号组成非终止符集：，，，，所以。(3)建立生成式集P。由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；由，有生成式；所以余码文法为，P：，，，，，，，6.7设文法，其中，，P的各生成式为①，②，③④，⑤，⑥，⑦设待识别链，试用填充树图法的顶下法分析x是否属于?解：(1)从S开始考察P中的①、②、③式：假设选①，那么结果为x=1，排除；假设选②，导出的x末位必为1，与题不符，排除；S1BA0A0S1BA0A00AS1BA0A0AS1BA0AS1BASB(a)(b)(c)(d)(e)解解图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.6CYK分析表填表结果C,SC,SCSCSSCCC,SSC,SC,SC,SC,S因为S在中，所以。6.9正那么文法，其中，，P的各生成式为，，，构成对应的有限态自动机，画出自动机的状态转换图。解：设有限态自动机，由A与G的对应关系得：由，有；由，有；由，有。故有限态自动机为，，：，，abSBFaabSBFaa解解图6.7自动机的状态转换图6.10有限态自动机，其中，，A的状态转换图如图6.15所示，求A对应的正那么文法G。图6.15状态转换图图6.15状态转换图11000011解：设正那么文法为，由G与A的对应关系得：；；；根据状态转换图有：P：因，有；因，有；因，有；而，故；因，有；因，有；因，有；而，故；因，有；因，有。由此得正那么文法为，，P：，，，，，，6.11上下文无关文法，其中，P的各生成式为，，写出文法G的格