资源描述：
《模式识别作业6.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、作业一：写出上下文无关文法，其终止符集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
2、aAba
3、bBa
4、bBabA->baA
5、∈B->abB
6、∈作业二：求一有限态自动机，它只能接受由“偶数个a”与/或“偶数个b”组成的任意字符串，例如：aa,bb,abab,abba,baba等。答案：其中文法为：G=(V,T,S,P)，V={S,A,B,C}，T={a,b},P如下：S->aA
7、bBA->aS
8、bC
9、aB->aC
10、bS
11、bC->aB
12、
13、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
14、S1
15、S2
16、S3
17、S4
18、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)作业四：试用树文法生成单位边长的立方体，定义三
19、个基元为立方体的三种方向的边。答案：对于该树状结构。可以对应有一个上下文无关文法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=>$
20、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)=>
21、($(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
22、->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->a
23、bc,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:
