形式语言与自动机的证明题1。给定文法G1=（V1，T1，P1，S1）G2=（V2，T2，P2，S2）试构造满足下列要求的文法G，并证明你的结论。L（G）=L（G1）L（G2）2。设文法G有如下产生式：S

Question

形式语言与自动机的证明题
1。给定文法
G1=（V1，T1，P1，S1）
G2=（V2，T2，P2，S2）
试构造满足下列要求的文法G，并证明你的结论。
L（G）=L（G1）L（G2）
2。设文法G有如下产生式：
S→aB|bA
A→a|aS|bAA
B→b|bS|aBB
证明：L（G）={w/w中含有相同个数的a和b，且w非空}。
（提示：对字符串w的长度施归纳，同时证明以下三个命题成立：
*
（1）S=＞w ＜=＞ w中含有相同个数的a和b，且w非空；
*
（2）A=＞w ＜=＞ w中含有a的个数比b的个数恰好多一个；
*
（3）B=＞w ＜=＞ w中含有a的个数比b的个数恰好少一个。）

Answer 1

【第一题答案】：令 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|bA
A→a|aS|bAA B→b|bS|aBB
L(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类似.