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

1、第5章句法模式识别习题解答6.1用链码法描述59五个数字。解：用弗利曼链码表示，基元如解图6.1所示:15数字59的折线化和量化结果如解图6.2所示:各数字的链码表示分别为:“5”的链码表示为x =444660076543 ；“6” 的链码表示为 x =4456667012344 ；“7”的链码表示为x =00066666 ；“8” 的链码表示为 x =3457076543 2101 ；“9” 的链码表示为 x =5432107666544。6.2定义所需基本基元，用PDL法描述印刷体英文大写斜体字母H”、“K”和解：设基元为:abede用PDL法得到“ H”的链描述为x(d (d (e (d

2、 ( d)；“K”的链描述为xK =(d(d a b)；“Z”的链描述为Xz =(g-c) e)。6.3 设有文法G = (Vn ,Vt, P, S)，Vn，Vt和P分别为Vn 二S,A, B，Vt 二a,bP： S aB， S bA， A a， A aS A bAA， B b， B bS， B aBB写出三个属于L(G)的句子。解：SM aBM abS aB abS abbA abbaS aB abS abaB ababSbAba S= bA 二 baS 二 baaB = baab S= bA= baS = babA= baba以上句子 ab，abba，abab，ba， baab, baba

3、均属于 L(G)。6.4 设有文法 G =(Vn,Vt, P,S)，其中 Vn 二S, A,B,C，Vt 二0,1，P 的各生成式为 S 0A， S 1B， S 1C A 0A， A 1B， A 1 B 0 , B 0B， C 0C， C 1 问x =00100是否属于语言L(G) ?解：由 S二 0A二 00A二 001B二 0010B= 00100可知x =00100属于语言L(G)。”，它6.5写出能产生图示树的扩展树文法，设基元a，b分别为和“所描述的模式是什么?/a / a解：1.写出生成树的扩展树文法生成式集: A $A2 A3 aA4A3A。 A bA6A9A5A 一;a7 As

4、 A,。；(11) A11a(12)A( aA10A11A122.检查非终止符的等价性。查得A2三A7三A11。删除A和A11及其后代生成式，其余生成式中的A7和A11用A2代替，合并后得到At $/A2 A- . a A3 aA4A3A4 A bA6A9A5A6 A|0 r bA2A10A23.建立起始产生式。将中的A1用S代替得到:Sr $/A2 A4设推断的扩展树文法为Gt(V,r,P, S)，由以上推断得:V 二 VnVt ,VN- S,A2,A3,A4,A5,A6,A9,A10,VT- $, a, br($)=2 , r(a)=1, 0,r(b)二2,1P的各生成式为S r $ /A

5、2 A4A3 A4 bA bA6A9A5 A9 bA2当基元a, b分别为”和“A10I A2时,它所描述的模式如解图6.3所示:解图6.3描述的模式6.6 已知L(G)的正样本集R丄01,100,111, 0010，试推断出余码文法 Gc。 解：设余码文法为Gc =(VnM,P, S)。(1) 由R 得 Gc的终止符集Vt二0,1。(2) 求R 的全部余码，组成非终止符集 Vn。R的全部余码为D R；二01,100,111, 0010，D0R 二1,010，D“R =00,11 /uD01R =，D10R 二0，D11R 二1，DR 二10DgoR - ， Dm R = ，D001R 工0，

6、 D0010R = 等号右边相同的合并，非空余码标以符号组成非终止符集Vn :S=D,R 二01,100,111, 0010，6 二 DR 二1,010，U D1R = 00,11U3 二 D10R 二0，U4 二 D11R 二1，5 二 DooR 二10所以Vn 二S,U1,U2,U3,U4,U5。(3) 建立生成式集P。由 DS 二1, 010 *1，有生成式 S 0U1 ；由 DU1 二1C =5，有生成式 U1 0U5 ；由 DU2 二0 =5，有生成式 U2 0U3 ；由D0U3二，有生成式U3 0 ；由 D1S 二00,11 =U2，有生成式 S 1U2；由D1U1二-，有生成式U

7、1 1 ；由 D1U2 =1 =U4，有生成式 U2 1U4 ；由D1U4二，有生成式U4 1 ；由 D1U5 =C -U 3，有生成式 U5 1U3 ；所以余码文法Gc =(Vn,Vt, P, S)为Vn = S,U1,U2,U3,U4,U5，Vt 二0,1P： S 0U1，U1 0U5，U2 0U3，U3 0S 1U2，U1 1，U2 1U4，U4 1，U5 1U36.7 设文法 G =(Vn,Vt, P, S)，其中 Vn =S, A, B , Vt 二0,1 , P 的各生成式 为 S 1， S B1， S B B 1A， B B1A， A 0， AA0设待识别链x =1000，试用填

8、充树图法的顶下法分析x是否属于L(G)? 解：(1)从S开始考察P中的、式：若选，则结果为x=1,排除；若选，导出的x末位必为1,与题不符，排除；选式，如解图6.4(a)所示。ABA/s B(a)(b)(c)(d)解图6.4填充树图过程0(e)(2) 填充目标为B，考察、均可填充，先试，如解图 6.4(b)所示。若不行, 再返回用式。(3) 此时填充目标为A，考察、。若选，导出的x为2位，与题不符，排 除。选式，如解图6.4(c)所示。(4) 类似地，得到图6.4所示各步结果，树叶为1000。故x属于L(G)。6.8 设上下文无关文法 G =(Vn,VP,S)，Vn 二S,C，Vt 二0,1，

9、P 中生成式的乔姆斯基范式为S CC，S CS，S 1，C SC，C CS，C 0用CYK分析法分析链x =01001是否为该文法的合法句子。解：待识别链为5位，构造5行5列的三角形分析表，如解图6.5所示t15t14t24t13t23t33t12t22t32t42t11t21t31t41t51解图6.5分析表求表中元素tj的值：令j =1，求知，1 G乞5。各子链为0，1，0，0，1。对于a1 = 0，切=C ；对于 a? = 1，t?1 = S ；对于 a3 = 0， t31 二 C ；对于 a = 0， t41 = C。对于 a5 =1， t41 = S。 令j = 2，求ti2，1 G

10、乞4。各子链为01, 10，00，01。对于 a1 a2 = 01，因有 Sr CS和 C CS， 0， Sr 1，故 t12 = C, S ；对于 a2a3 =10，有 C SC，S 1，C0，故 t?2 = C。对于 a3a4 = 00，有 Sr CC， C r 0，C r 0，故 t32 = S o对于 a4a5 = 01，有 Sr CS和 C CS， 0，1，故t42 = C, S ; 令j =3，求ti3，1 G岂3。各子链为010，100，001 o对于 a1a2a 010，因有 S ； CC，* *C r 0，C= 10 ;和 C SC， S= 01，C 0。故 t13 = C,

11、 S o类似地有 t?3 = S，上33 = C, S，切=C, S ， t24 = C, S，t15 = C, S。填表结果如解图6.6所示。C,SC,SC,SC,SSC,SC,SCSC,SCSCCS解图6.6 CYK分析表填表结果因为S在t15中，所以x L(G)6.9 已知正则文法 G =(Vn,Vt,P, S)，其中 Vn 二S, B , V =a, b , P 的各生成式为S 丿 aB ， B aB ， B bS ， B a构成对应的有限态自动机，画出自动机的状态转换图。解：设有限态自动机A = ( , Q,-：, q, F )，由A与G的对应关系得 =Vt = a, bQ 二Vn

12、F 二S, B, Fq 二 S:由 S r aB，有、；(S, a) = B ；由 B aB，B a 有、(B, a) bS，有、(B, b) =S。故有限态自动机A ,Q,q。，F )为7 = a, b， Q 二S, B, F ， q。二 S6.10已知有限态自动机A = L ,Q，q,F)，其中:-0,1, Q =q, qi, q2, qs , F =q3解：设正则文法为G =(Vn，Vt，P,S)，由G与A的对应关系得：VN - Q q0, qi , q2 , q3；Vt 八=0,1；s ；根据状态转换图有：P:因、(q。, 0)二g，有 q。 0q2 ；因 (q,1) =qi，有 q。

13、 iqi ；因 (qi,0) =q3，有 qi 0q3 ；而 q F，故 qi 0 ；因 (qi,1) =q，有 qi 1q ；因 G，。)=，有 q2 0q ；因 ,1) =4，有 q2 * 1q3 ； 而 q F，故 q?1 ；因 G，0) =qi，有 q3 0qi ；因 (q3,1) =q2，有 q3知。由此得正则文法G =(Vn,Vt, P,S)为Vn =Q =qo, qi, q2, q3，M = 二0,1， S = qoP： qo0q2,qo 1qi, qi 0 ,qi 1qq2 r0q0,q2 r1 , q3 r g ,q3 r 馄6.11已知上下文无关文法G =(Vn,Vt,P,S)，其中Vn =S, A , Vt 二a,b,c,dP的各生成式为S / cA , A- aAb , A d写出文法G的格雷巴赫范式，构成相应的下推自动机。解：文法G =(Vn，%,P,S)的格雷巴赫范式为：Vn =S, A, B，Vt =a, b,c,dP： Sr cA， Ar aAB， Ar d， Br b设相应的下推自动机为 Ap十 ,Q, r、.，q0，Z。，F)，其中、-vt =a,b, c, d，Q=q0r 二 Vn 二S, a, B，z 二 s，F =转换规则八：因 P 中有 S； cA，故 (q,c, S) =(q, A)因 P 中有 A aAB，故、 (q