文库摘要：

4）{w#wr# | w?{0,1}*,wr是w的逆序排列}
  解：G(S) = ({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S)
 （5）任何不是以0打头的所有奇整数所组成的集合
  解：G(S) = ({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e, I→J|2|4|6|8, Jà1|3|5|7|9},S)
 （6）所有偶数个0和偶数个1所组成的符号串集合
  解：对应文法为 S→0A|1B|e，A→0S|1C B→0C|1S C→1A|0B
3.描述语言特点
 （1）S→10S0S→aAA→bAA→a
  解：本文法构成的语言集为：L(G)={(10)nabma0n|n, m≥0}。
 （2）S→SS S→1A0A→1A0A→ε
  解：L(G)={1n10n11n20n2 … 1nm0nm |n1,n2,…,nm≥0；且n1,n2,…nm不全为零}该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。
 （3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε 内容来自www.wkfxw.com
  解：本文法构成的语言集为：L(G)={1p1n0n|p≥1,n≥0}∪{1n0n0q|q≥1,n≥0}，特点是具有1p1n0n 或1n0n0q形式，进一步，可知其具有形式1n0mn,m≥0,且n+m>0。
 （4）S→bAdcA→AGSG→εA→a
  解：可知，S=>…=>baSndc n≥0
  该语言特点是：产生的句子中，是以ba开头dc结尾的串,且ba、dc个数相同。
 （5）S→aSSS→a
  解：L(G)={a(2n-1)|n≥1}可知：奇数个a
4.解：此文法产生的语言是：以终结符a1 、a2 …an 为运算对象，以∧、∨、~为运算符，以[、]为分隔符的布尔表达式串
5.   5.1解：由于此文法包含以下规则：AA→e，所以此文法是0型文法。
     5.2证明：略
6.解：
（1）最左推导：
<程序>T<分程序>T<标号>：<分程序>TL：<分程序>