形式语言与自动机论文题目

【第一题答案】：令 L1 与 L2 是 context-free languages,而 G1 = (V1, T1, S1, P1) 与 G2 = (V2, T2, S2, P2) 是它们的 context-free grammars,假设 V1 V2 = ,令 G3 = ( V1 V2 {S3}, T1 T2, S3, P3),其中 P3 = P1 P2 {S3 → S1 | S2}.则 L(G3) = L1 L2.令 G4 = ( V1 V2 {S4}, T1 T2, S4, P4), 其中 P4 = P1 P2 {S4 S1S2},则 L(G4) = L(G1)L(G2).令 G5 = ( V1 {S5}, T1, S5, P5), 其中 P5 = P1 {S5 → S1S5 | λ},则 L(G5) = L(G1)*.【第二题答案】：设G=(VT={a,b},VN={S,A,B},S,P}P由下列产生式组成:S→aB|bAA→a|aS|bAA B→b|bS|aBBL(G)={w|w∈{a,b}+,且w中有相同个数的a和b}. 用归纳法证明下面结论(对w的长度) :(1)S w,当且仅当w中含有相同个数的a和b. (2)A w,当且仅当w中a的个数比b的个数多一个. (3)B w,当且仅当w中b的个数比a的个数多一个.归纳基础 当|w|=1,A a, B b, 不能从S导出长度 为1的终极行,则上述结论显然成立.设(1),(2)和(3)对于长度不超过k-1的所有w都成立.那么,证明对|w|=k也成立.对于(1),推导的第一步必是S aB或S bA,对于第一种情形,必有w=aw1且B w1, |w1|=k-1,它含的b个数比a多一个,因此,w中a,b的个数相等.推导的第一步是S bA,证明完全类似.反之,|w|=k, w中a,b的个数相等,要证S w.考虑的S推导,推导出的开始符号,或为a或为b.若S aB,B w1, |w1|=k-1, w1中b的个数比a多一个,w= aw1.若S bA,证明和类S aB类似.