黄庆明-模式识别与机器学习-第五章-作业.doc

写出上下文无关文法，其终止符集

VT={a,b}

能生成语言

L(G)={ab,ba,aba,bab,abab,baba,…}

G=(VN,VT,P,S)，其中VN={S,A,B}，VT={a,b}，

P：S-aB|bA

B-bA|b

A-aB|a

求一有限态自动机，它只能接受由“偶数个a”与/或“偶数个b”组成的任意字符串，例如：aa,bb,abab,abba,baba等。

G=(VN,VT,P,S)，其中VN={S,A,B,C}，VT={a,b}，

P：

S-aA|bB

A-aS|bC|a

B-bS|aC|b

C-aB|bA

自己定义基元，用PDL文法生成0到5的字符，字符笔划用七划样式。

提示：可参照例题中的基元定义

文法G?=?(VN,?VT,?P,?S)，其中VN={S,S0,S1,S2,S3,S4,S5,A,B,C,D}，VT={?a↓,?b→,?(,?),+,*,~,-}，?

P：S-S0|S1|S2|S3|S4|S5，A-((~a+b)+a)，B-((a+b)+~a)，C-(b+a)，D-((~b+a)+b)?

S0-A*B，?

S1-(a+a)，S2-C+D，S3-((C-b)+a)-b，S4-((a+b)-a)+a，S5-D+a+(~b)

试用树文法生成单位边长的立方体，定义三个基元为立方体的三种方向的边。

对于该树状结构。?

可以对应有一个上下文无关文法G=({S,?A},?{$,?a,?b,?c},?P,?S)?

P:?S-$AAA，A-aAA，A-bA，A-c,A-cAA,A-aA,A-b,A-bAA,?A-cA,A-a?

那么GT’=({S,?A},?{$,?a,?b,?c,?(,?)},?P’,?S)?

P’:?S-($AAA)，A-(aAA)，A-(bA)，A-(c),A-(cAA),A-(aA),A-(b),A-(bAA),?A-(cA),A-(a)?

由G生成：S=$AAA=$aAAAA=$abAAAA=$abcAAA=$abccAA=$abcccAAA=$abcccaAAA?=$abcccabAA=$abcccabbA=$abcccabbbAA=$abcccabbbcAA=$abcccabbbcaA=$abcccabbbcaa?

由GT’生成：?

S=($AAA)=($(aAA)AA)=($(a(bA)A)AA)=($(a(b(c))A)AA)=($(a(b(c))(c))AA)=($(a(b(c))(c))(cAA)A)=($(a(b(c))(c))(c(aA)A)A)=($(a(b(c))(c))(c(a(b))A)A)=($(a(b(c))(c))(c(a(b))(b))A)=($(a(b(c))(c))(c(a(b))(b))(bAA))=($(a(b(c))(c))(c(a(b))(b))(b(cA)A))=($(a(b(c))(c))(c(a(b))(b))(b(c(a))A))=($(a(b(c))(c))(c(a(b))(b))(b(c(a))(a)))

给出字符串样本集为

{aaacc,aaacb,aacc,bacb,aaa,abc,bb,cc}

推断一个有限态文法。

对x1=aaacc，文法G1的生成式P1：S-aA,A-aB,B-aC,C-cc?

对x2=aaacb，文法G2的生成式P2：S-aaD,D-aE,E-cb?

对x3=aacc，文法G3的生成式P3：S-aF,F-aG,G-cc?

对x4=bacb，文法G4的生成式P4：S-baH,H-cb?

对x5=aaa，文法G5的生成式P5：S-aI,I-aa?

对x6=abc，文法G6的生成式P6：S-abc?

对x7=bb，文法G7的生成式P7：S-bb?

对x8=cc，文法G8的生成式P8：S-cc?按以下步骤去掉合并，重复的生成式，?(i)将非终止符C

和G合并为C，

S-aA,A-aB,B-aC,C-cc,S-aaD,D-aE,E-cb,S-aF,F-aC,S-baH,H-cb,S-aI,I-aa,S-abc,S-bb,S-cc?

(ii)再将E和H合并为E，S-aA,A-aB,B-aC,C-cc,S-aaD,D-aE,E-cb,S-aF,F-aC,S-baE,S-aI,I-aa,S-abc,S-bb,S-cc?(iii)引入C-c,替换S-aA,S-abc,S-cc: