模式识别作业6.docx

作业一:写出上下文无关文法,其终止符集 VT={a,b} 能生成语言 L(G)={ab,ba,aba,bab,abab,baba,…}答案:上下文无关文法:G=(V,T,S,P),V={S,A,B},T={a,b},P如下:S->aAb|aAba|bBa|bBabA->baA|∈B->abB|∈作业二:求一有限态自动机,它只能接受由“偶数个a”与/或“偶数个b”组成的任意字符串,例如:aa,bb,abab,abba,baba等。答案:其中文法为:G=(V,T,S,P),V={S,A,B,C},T={a,b},P如下:S->aA|bBA->aS|bC|aB->aC|bS|bC->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=>$AA=>$AAA=>$aAAA=>$abAA=>$abbA=>$abbbAA=>$abbbcAA=>$abbbcaA=>$abbbcaa由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)))作业五:给出字符