第6章 句法模式识别习题解答6.1 用链码法描述5～9五个数字。

解：用弗利曼链码表示，基元如解图6.1所示：数字5~9的折线化和量化结果如解图6.2所示：各数字的链码表示分别为：“5”的链码表示为434446600765=x ； “6”的链码表示为3444456667012=x ； “7”的链码表示为00066666=x ； “8”的链码表示为21013457076543=x ； “9”的链码表示为5445432107666=x 。

17解图6.1 弗利曼链码基元 解图6.2 数字5~9的折线化和量化结果6.2 定义所需基本基元，用PDL 法描述印刷体英文大写斜体字母“H ”、“K ”和“Z ”。

解：设基元为：用PDL 法得到“H ”的链描述为)))))(~((((d d c d d x H ⨯+⨯+=；“K ”的链描述为))((b a d d x K ⨯⨯+=； “Z ”的链描述为))((c c g x Z ⨯-=。

6.3 设有文法),,,(S P V V G T N =，N V ，T V 和P 分别为},,{B A S V N =，},{b a V T =：P ①aB S →，②bA S →，③a A →，④aS A →⑤bAA A →，⑥b B →，⑦bS B →，⑧aBB B → 写出三个属于)(G L 的句子。

解：以上句子ab ，abba ，abab ，ba ，baab ，baba 均属于)(G L 。

6.4 设有文法),,,(S P V V G T N =，其中},,,{C B A S V N =，}1,0{=T V ，P 的各生成式为①A S 0→，②B S 1→，③C S 1→bcadeabba abbA abS aB S ⇒⇒⇒⇒ ① ⑦ ② ③ab aB S ⇒⇒ ① ⑥ba bA S ⇒⇒② ③ abab abaB abS aB S ⇒⇒⇒⇒ ① ⑦ ① ⑥baab baaB baS bA S ⇒⇒⇒⇒ ② ④ ① ⑥baba babA baS bA S ⇒⇒⇒⇒② ④ ② ③④A A 0→，⑤B A 1→，⑥1→A ⑦0→B ，⑧B B 0→，⑨C C 0→，⑩1→C问00100=x 是否属于语言)(G L ？ 解：由可知00100=x 属于语言)(G L 。

6.5 写出能产生图示树的扩展树文法，设基元a ，b 分别为“→”和“↓”，它所描述的模式是什么？解：1. 写出生成树的扩展树文法生成式集：2. 检查非终止符的等价性。

a$babbab001000010001000⇒⇒⇒⇒⇒B B A A S① ④ ⑤ ⑧ ⑦⑴$A →14A 2A 3⑵a A →2⑶a A →3⑸b A →59A 6A 5⑷b A →4⑿a A →12(6)a A →6A 7A 8⑺a A →7⑻a A →8⑼b A →9A 10⑽b A →10A 11⑾a A →11A 12查得1172A A A ≡≡。

删除7A 和11A 及其后代生成式，其余生成式中的7A 和11A 用2A 代替，合并后得到3. 建立起始产生式。

将⑴中的1A 用S 代替得到：设推断的扩展树文法为),,,(S P r V G t ='，由以上推断得：T N V V V =，},,,,,,,{10965432A A A A A A A S V N =，},,{b a $V T =2)(=$r ，}0,1{)(=a r ，}1,2{)(=b rP 的各生成式为当基元a ，b 分别为“→”和“↓”时， 它所描述的模式如解图6.3所示：a ab b b ba aa aa$ $S →4A 2⑸b A →59A 6A 5⑷b A →4(6)a A →6A 2⑼b A →9A 10⑽b A →10A 2⑴$A →14A 2A 3⑵a A →2⑶a A →3⑸b A →59A 6A 5⑷b A →4(6)a A →6A 2⑼b A →9A 10⑽b A →10A 2⑴$S →4A 2A 3⑵a A →2⑶a A →3解图6.3 描述的模式6.6 已知)(G L 的正样本集}0010,111,100,01{=+R ，试推断出余码文法c G 。

解：设余码文法为),,,(S P V V G T N c =。

(1) 由+R 得c G 的终止符集}1,0{=T V 。

(2) 求+R 的全部余码，组成非终止符集N V 。

+R 的全部余码为}0010,111,100,01{=+R D λ，}010,1{0=+R D ，}11,00{1=+R D}{01λ=+R D ，}0{10=+R D ，}1{11=+R D ，}10{00=+R D }{100λ=+R D ，}{111λ=+R D ， }0{001=+R D ，}{0010λ=+R D等号右边相同的合并，非空余码标以符号组成非终止符集N V ：}0010,111,100,01{==+R D S λ，}010,1{01==+R D U ，}11,00{12==+R D U}0{103==+R D U ，}1{114==+R D U ，}10{005==+R D U所以},,,,,{54321U U U U U S V N =。

(3) 建立生成式集P 。

由10}010,1{U S D ==，有生成式10U S →； 由510}10{U U D ==，有生成式510U U →； 由320}0{U U D ==，有生成式320U U →； 由λ=30U D ，有生成式03→U ；由21}11,00{U S D ==，有生成式21U S →； 由λ=11U D ，有生成式11→U ；由421}1{U U D ==，有生成式421U U →； 由λ=41U D ，有生成式14→U ； 由351}0{U U D ==，有生成式351U U →； 所以余码文法),,,(S P V V G T N c =为},,,,,{54321U U U U U S V N =，}1,0{=T V P ：10U S →，510U U →，320U U →，03→U 21U S →，11→U ，421U U →，14→U ，351U U →6.7 设文法),,,(S P V V G T N =，其中},,{B A S V N =，}1,0{=T V ，P 的各生成式为①1→S ，②1B S →，③B S →④A B 1→，⑤A B B 1→，⑥0→A ，⑦0A A →设待识别链1000=x ，试用填充树图法的顶下法分析x 是否属于)(G L ? 解：(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 属于)(G L 。

6.8 设上下文无关文法),,,(S P V V G T N =，},{C S V N =，}1,0{=T V ，P 中生成式的乔姆斯基范式为CC S →，CS S →，1→S ，SC C →，CS C →，0→C用CYK 分析法分析链01001=x 是否为该文法的合法句子。

解图6.4 填充树图过程 S1BAAS1BAAS1BAAS1BAS B (a) (b) (c) (d) (e)解：待识别链为5位，构造5行5列的三角形分析表，如解图6.5所示。

求表中元素ij t 的值：(1) 令1=j ，求1i t ，51≤≤i 。

各子链为0，1，0，0，1。

对于01=a ，C t =11； 对于12=a ，S t =21； 对于03=a ，C t =31； 对于04=a ，C t =41。

对于15=a ，S t =41。

(2) 令2=j ，求2i t ，41≤≤i 。

各子链为01，10，00，01。

对于0121=a a ，因有CS S →和CS C →，0→C ，1→S ，故S C t ,12=； 对于1032=a a ，有SC C →，1→S ，0→C ，故C t =22。

对于0043=a a ，有CC S →，0→C ，0→C ，故S t =32。

对于0154=a a ，有CS S →和CS C →，0→C ，1→S ，故S C t ,42=； (3) 令3=j ，求3i t ，31≤≤i 。

各子链为010，100，001。

对于010321=a a a ，因有CC S →，0→C ，10*⇒C ；和SC C →，01*⇒S ， 0→C 。

故S C t ,13=。

类似地有S t =23，S C t ,33=，S C t ,14=，S C t ,24=，S C t ,15=。

填表结果如解图6.6所示。

解图6.5 分析表t 14 t 13t 12 t 11t 23t 22 t 21t 32 t 31t 41t 15 t 51t 42 t 33t 24因为S 在15t 中，所以)(G L x ∈。

6.9 已知正则文法),,,(S P V V G T N =，其中},{B S V N =，},{b a V T =，P 的各生成式为aB S →，aB B →，bS B →，a B →构成对应的有限态自动机，画出自动机的状态转换图。

解：设有限态自动机),,,,(0∑=F q Q A δ，由A 与G 的对应关系得∑==},{b a VT},,{F B S F V Q N ==S q =0δ：由aB S →，有B a S =),(δ；由aB B →，a B →有},{),(F B a B =δ；由bS B →，有S b B =),(δ。

故有限态自动机),,,,(0∑=F q Q A δ为∑=},{b a ，},,{F B S Q =，S q=0δ：B a S =),(δ，},{),(F B a B =δ，S b B =),(δ解图6.6 CYK 分析表填表结果 C,S C,S CS C SS CCC,S SC,S C,S C,S C,S 解图 6.7 自动机的状态转换图6.10 已知有限态自动机),,,,(0∑=F q Q A δ，其中∑=}1,0{，},,,{321q q q q Q =，}{3qF =A 的状态转换图如图6.15所示，求A 对应的正则文法G 。

解：设正则文法为),,,(S P V V G T N =，由G 与A 的对应关系得：},,,{3210q q q q Q V N ==；∑==}1,0{T V ；0q S =；根据状态转换图有：P ：因}{)0,(20q q =δ，有200q q →； 因}{)1,(10q q =δ，有101q q →；因}{)0,(31q q =δ，有310q q →；而F q ∈3，故01→q ； 因}{)1,(01q q =δ，有011q q →； 因}{)0,(02q q =δ，有020q q →；因}{)1,(32q q =δ，有321q q →；而F q ∈3，故12→q ； 因}{)0,(13q q =δ，有130q q →； 因}{)1,(23q q =δ，有231q q →。