搜索
Lecture5答案作业一：写出上下文无关文法，其终止符集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=$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: