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

1、第5章句法模式识别习题解答6.1用链码法描述 59 五个数字。解：用弗利曼链码表示，基元如解图6.1 所示：数字 59的折线化和量化结果如解图6.2 所示：各数字的链码表示分别为：“5”的链码表示为434446600765x；“6”的链码表示为3444456667012x；“7”的链码表示为00066666x；“8”的链码表示为21013457076543x；“9”的链码表示为5445432107666x。2 0 1 3 4 5 6 7 解图 6.1 弗利曼链码基元解图 6.2 数字 59 的折线化和量化结果6.2定义所需基本基元，用pdl 法描述印刷体英文大写斜体字母“h” 、 “k”和“z

2、” 。解：设基元为：用 pdl 法得到“ h”的链描述为)(ddcddxh；“k”的链描述为)(baddxk；“z”的链描述为)(ccgxz。6.3设有文法),(spvvgtn，nv，tv和 p 分别为,basvn，,bavt：pabs，bas，aa，asabaaa，bb，bsb，abbb写出三个属于)(gl的句子。解：以上句子 ab，abba，abab，ba，baab，baba均属于)(gl。6.4设有文法),(spvvgtn，其中,cbasvn，1, 0tv，p 的各生成式为as0，bs1，cs1bcadeabbaabbaabsabsababsbabasabababababsabsbaab

3、baabbasbasbababababasbasaa0，ba1，1a0b，bb0 ，cc0，1c问00100 x是否属于语言)(gl？解：由可知00100 x属于语言)(gl。6.5写出能产生图示树的扩展树文法，设基元a，b 分别为“”和“”，它所描述的模式是什么？解：1. 写出生成树的扩展树文法生成式集：2. 检查非终止符的等价性。a $ a b a b a a a b a b 001000010001000bbaas$a1a4a2a3aa2aa3ba5a9a6a5ba4aa12(6)aa6a7a8aa7aa8ba9a10ba10a11aa11a12查得1172aaa。删除7a和11a及其后

4、代生成式，其余生成式中的7a和11a用2a代替，合并后得到3. 建立起始产生式。将中的1a用 s代替得到：设推断的扩展树文法为),(sprvgt，由以上推断得：tnvvv，,10965432aaaaaaasvn，,ba$vt2)($r，0, 1)(ar，1,2)(brp 的各生成式为当基元 a，b 分别为“”和“”时，它所描述的模式如解图6.3 所示：a a b b b b a a a a a $ $sa4a2ba5a9a6a5ba4(6)aa6a2ba9a10ba10a2$a1a4a2a3aa2aa3ba5a9a6a5ba4(6)aa6a2ba9a10ba10a2$sa4a2a3aa2aa3

5、解图 6.3 描述的模式6.6 已知)(gl的正样本集0010,111,100,01r，试推断出余码文法cg。解：设余码文法为),(spvvgtnc。(1) 由 r 得cg的终止符集1, 0tv。(2) 求 r 的全部余码，组成非终止符集nv。 r 的全部余码为0010,111,100,01rd，010, 10rd，11,001rd01rd，010rd，111rd，1000rd100rd，111rd，0001rd，0010rd等号右边相同的合并，非空余码标以符号组成非终止符集nv：0010,111,100,01rds，010, 101rdu，11,0012rdu0103rdu，1114rdu，

6、10005rdu所以,54321uuuuusvn。(3) 建立生成式集 p。由10010,1usd，有生成式10us；由51010uud，有生成式510uu；由3200uud，有生成式320uu；由30ud，有生成式03u；由2111,00usd，有生成式21us；由11ud，有生成式11u；由4211uud，有生成式421uu；由41ud，有生成式14u；由3510uud，有生成式351uu；所以余码文法),(spvvgtnc为,54321uuuuusvn，1,0tvp：10us，510uu，320uu，03u21us，11u，421 uu，14u，351uu6.7 设文法),(spvvgt

7、n，其中,basvn，1,0tv，p 的各生成式为1s，1bs，bsab1，abb1，0a，0aa设待识别链1000 x，试用填充树图法的顶下法分析x 是否属于)(gl? 解：(1) 从 s开始考察 p 中的、式：若选，则结果为x=1，排除；若选，导出的 x 末位必为 1，与题不符，排除；选式，如解图 6.4(a)所示。(2) 填充目标为 b，考察、均可填充，先试，如解图6.4(b)所示。若不行，再返回用式。(3) 此时填充目标为a，考察、。若选，导出的x 为 2 位，与题不符，排除。选式，如解图6.4(c)所示。(4) 类似地，得到图6.4 所示各步结果，树叶为1000。故 x 属于)(gl

8、。6.8 设上下文无关文法),(spvvgtn，,csvn，1, 0tv，p 中生成式的乔姆斯基范式为ccs，css，1s，scc，csc，0c用 cyk 分析法分析链01001x是否为该文法的合法句子。解图 6.4 填充树图过程s 1 b a 0 a 0 0 a s 1 b a 0 a 0 a s 1 b a 0 a s 1 b a s b (a) (b) (c) (d) (e) 解：待识别链为5 位，构造 5 行 5 列的三角形分析表，如解图6.5 所示。求表中元素ijt的值：(1) 令1j，求1it，51i。各子链为 0，1，0，0，1。对于01a，ct11；对于12a，st21；对于0

9、3a，ct31；对于04a，ct41。对于15a，st41。(2) 令2j，求2it，41i。各子链为 01，10，00，01。对于0121aa，因有css和csc，0c，1s，故sct,12；对于1032aa，有scc，1s，0c，故ct22。对于0043aa，有ccs，0c，0c，故st32。对于0154aa，有css和csc，0c，1s，故sct,42；(3) 令3j，求3it，31i。各子链为 010，100，001。对于010321aaa，因有ccs，0c，10*c；和scc，01*s，0c。故sct,13。类似地有st23，sct,33，sct,14，sct,24，sct,15。填

10、表结果如解图 6.6 所示。解图 6.5 分析表t14t13t12t11t23t22t21t32t31t41t15t51t42t33t24因为 s在15t中，所以)(glx。6.9 已知正则文法),(spvvgtn，其中,bsvn，,bavt，p 的各生成式为abs，abb，bsb，ab构成对应的有限态自动机，画出自动机的状态转换图。解：设有限态自动机),(0fqqa，由 a 与 g 的对应关系得,bavt,fbsfvqnsq0：由abs，有bas),(；由abb，ab有,),(fbab；由bsb，有sbb),(。故有限态自动机),(0fqqa为,ba，,fbsq，sq0：bas),(，,),

11、(fbab，sbb),(状态转换图如解图6.7 所示：解图 6.6 cyk 分析表填表结果c,s c,s c s c s s c c c,s s c,s c,s c,s c,s 解图6.7 自动机的状态转换图a b s b f a a 6.10 已知有限态自动机),(0fqqa，其中1,0，,3210qqqqq，3qfa 的状态转换图如图6.15 所示，求 a 对应的正则文法 g。解：设正则文法为),(spvvgtn，由 g 与 a 的对应关系得：,3210qqqqqvn； 1, 0tv；0qs；根据状态转换图有：p：因)0,(20qq，有200qq；因)1,(10qq，有101qq；因)0,

12、(31qq，有310qq；而fq3，故01q；因)1,(01qq，有011qq；因)0,(02qq，有020qq；因)1,(32qq，有321qq；而fq3，故12q；因)0,(13qq，有130qq；因)1,(23qq，有231qq。由此得正则文法),(spvvgtn为,3210qqqqqvn， 1, 0tv，0qs图 6.15 状态转换图1 1 0 0 0 0 0q1q3q2q1 1 p：200qq，101qq，01q，011qq020qq，12q，130qq，231qq6.11 已知上下文无关文法),(spvvgtn，其中,asvn，,dcbavtp 的各生成式为cas，aaba，da写出文法 g 的格雷巴赫范式，构成相应的下推自动机。解：文法),(spvvgtn的格雷巴赫范式为：,basvn，,dcbavtp：cas，aaba，da，bb设相应的下推自动机为),(00fzqqap，其中,dcbavt，0qq,basvn，sz0