第5章 句法模式辨认习题解答6.1 用链码法描述5～9五个数字20134567解:用弗利曼链码表达，基元如解图6.1所示：解图6.1 弗利曼链码基元数字5~9的折线化和量化成果如解图６.2所示: 解图6.2 数字5~9的折线化和量化成果各数字的链码表达分别为:“５”的链码表达为;“６”的链码表达为；“7”的链码表达为；“8”的链码表达为；“９”的链码表达为6.2 定义所需基本基元，用PDＬ法描述印刷体英文大写斜体字母“H”、“K”和“Ｚ”解：设基元为：bcade用ＰDＬ法得到“Ｈ”的链描述为;“K”的链描述为；“Z”的链描述为6.3 设有文法，，和P分别为，①,②，③，④ ⑤,⑥，⑦，⑧①⑦②③①⑥②③①⑦①⑥②④①⑥②④②③写出三个属于的句子解：以上句子ab,abbａ，aｂａb,ba,baａｂ，babａ均属于6.4 设有文法，其中,，P的各生成式为①，②,③④，⑤，⑥⑦,⑧，⑨,⑩问与否属于语言？⑦⑧⑤④①解：由可知属于语言6.5 写出能产生图示树的扩展树文法,设基元a,b分别为“→”和“↓”,它所描述的模式是什么？ a$ababaaababA3⑵⑴A4A2⑶解:1. 写出生成树的扩展树文法生成式集:A5⑷⑸A9A6(6)A7⑻A8⑺⑾A12⑿⑼A10⑽A112. 检查非终结符的等价性。
查得删除和及其后裔生成式，其他生成式中的和用替代，合并后得到⑸A9A6A5⑷(6)A2⑼A10⑽A2⑴A4A2A3⑵⑶A4A2３. 建立起始产生式将⑴中的用Ｓ替代得到: 设推断的扩展树文法为，由以上推断得:,,,，⑸A9A6A5⑷(6)A2⑼A10⑽A2⑴A4A2A3⑵⑶P的各生成式为aabbbbaaaaa$ 当基元ａ，ｂ分别为“→”和“↓”时，它所描述的模式如解图6．3所示：解图6.3 描述的模式6.６ 已知的正样本集，试推断出余码文法解：设余码文法为１） 由得的终结符集2) 求的所有余码,构成非终结符集的所有余码为,， ,，，，, ，等号右边相似的合并,非空余码标以符号构成非终结符集：，，，，因此3） 建立生成式集P由，有生成式;由，有生成式；由，有生成式;由，有生成式；由，有生成式;由,有生成式;由，有生成式;由,有生成式；由，有生成式；因此余码文法为 , Ｐ:，,, ，，，,６.7 设文法，其中,，P的各生成式为①，②,③④，⑤，⑥，⑦设待辨认链,试用填充树图法的顶下法分析ｘ与否属于?解:(１） 从S开始考察Ｐ中的①、②、③式:若选①,则成果为x=1,排除；若选②，导出的x末位必为１,与题不符,排除；S1BA0A00AS1BA0A0AS1BA0AS1BASB(a) (b) (c) (d) (e) 选③式,如解图6.4(a）所示。
解图6.4 填充树图过程(２） 填充目的为B,考察④、⑤均可填充，先试④,如解图6.4(ｂ)所示若不行，再返回用⑤式3) 此时填充目的为Ａ,考察⑥、⑦若选⑥,导出的x为 2位,与题不符，排除选⑦式,如解图6．４(ｃ)所示4) 类似地,得到图6．４所示各步成果,树叶为1０00 故x属于6.８ 设上下文无关文法,，，Ｐ中生成式的乔姆斯基范式为,,，，，用CYＫ分析法分析链与否为该文法的合法句子解：待辨认链为5位，构造5行5列的三角形分析表，如解图6.5所示解图6.5 分析表t14t13t12t11t23t22t21t32t31t41t15t51t42t33t24 求表中元素的值:（1) 令,求, 各子链为0，1,０，0，1 对于，； 对于,； 对于,； 对于， 对于,２） 令，求，各子链为01,10,00,01对于,因有和，，,故;对于，有,，，故对于,有，，，故对于，有和，，,故;(３) 令,求，各子链为010,１0０，０01对于，因有,，；和，,类似地有，,,，填表成果如解图6.6所示解图6.6 CYK分析表填表成果C,SC,SCSCSSCCC,SSC,SC,SC,SC,S 由于S在中,因此。
6.9 已知正则文法,其中,，P的各生成式为,,,构成相应的有限态自动机,画出自动机的状态转换图解：设有限态自动机，由Ａ与G的相应关系得:由，有; 由，有； 由,有故有限态自动机为,,:，，abSBFaa状态转换图如解图６.7所示：解图 6.7 自动机的状态转换图6.1０ 已知有限态自动机，其中,,A的状态转换图如图6.１5所示，求A相应的正则文法G图6.15 状态转换图11000011解：设正则文法为，由G与Ａ的相应关系得:；；；根据状态转换图有:P：因，有; 因,有;因,有；而，故；因，有;因,有；因，有；而，故;因,有；因,有由此得正则文法为,,P:,，， ,,，6．11 已知上下文无关文法,其中,P的各生成式为，,写出文法G的格雷巴赫范式，构成相应的下推自动机解：文法的格雷巴赫范式为：， Ｐ:,，, 设相应的下推自动机为,其中,，，转换规则： 因P中有,故 因Ｐ中有，故 因P中有，故 因P中有,故即下推自动机为：,，，,P：,,。