主观题：h0022. 求下列文法所描述的语言

分别求下列文法所描述的语言：
① G1[S]：
S→aaSbb | ε

② G2[S]：
S→10S0 | aA
A→bA | a

③ G3[S]：
S→SS | 1A0
A→1A0 | ε







答案：解答：
∵ S=>aaSbb=>aaaaSbbbb=> …
∴ L(G1[S])={a^(2n)b^(2n) | n≥0}---------------------3分

②
∵ S=>10S0=>1010S00=>…=>(10)^mS0^m=>(10)^m aA 0^m
A=>bA=>bbA=>…=>b^nA=> b^na
∴S=>…=>(10)^m aA 0^m =>(10)m a b^na 0m
L(G2[S])={ (10)^m a b^na 0^m | m≥0,n≥0}---------------------3分

③
解:
∵ S=>SS=>…=> SS^m=> SS^m=> 1A0(1A0)^m
A=>1A0=>11A00=>…=>1 ^m A0 ^m =>1^m A0^m=>1^m 0^m
∴ S=>1A0(1A0)^m =>11^m 0^m 0(11^ m 0^m 0)^n
L(G2[S])={ (1^m 0^m )^n | m≥1,n≥1}---------------------3分