2.1 设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及A+和A*. x0=(aaa)0=ε | x0|=0 xx=aaaaaa |xx|=6 x5=aaaaaaaaaaaaaaa | x5|=15 A+ =A1∪A2∪ …. ∪A n∪…={a,aa,aaa,aaaa,aaaaa…}
A* = A0 ∪A1 ∪ A2 ∪ …. ∪ A n ∪…={ε,a,aa,aaa,aaaa,aaaaa…}
2.2 令∑={a，b，c}，又令x=abc，y=b，z=aab，写出如下符号串及它们的长度：xy，xyz，（xy）3
xy=abcb |xy|=4 xyz=abcbaab |xyz|=7 (xy)3=(abcb)3 =abcbabcbabcb | (xy)3 |=12 2.3
设有文法G[S]：S∷=SS*|SS+|a，写出符号串aa+a*规范推导，并构造语法树。 S => SS* => Sa* => SS+a* => Sa+a* => aa+a*
S S S * S a S a + a 2.4 已知文法G[Z]：Z∷=U0∣V1 、 U∷=Z1∣1 、 V∷=Z0∣0 ,请写出全部由此文法描述的只含有四个符号的句子。
Z=>U0=>Z10=>U010=>1010
Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z01=>U001=>1001 Z=>V1=>Z01=>V101=>0101
2.5 已知文法G[S]： S∷=AB A∷=aA︱ε B∷=bBc︱bc , 写出该文法描述的语言。
A∷=aA︱ε描述的语言: {an|n>=0} B∷=bBc︱bc描述的语言：{bncn|n>=1} L(G[S])={anbmcm|n>=0,m>=1}
2.6 已知文法E∷=T∣E+T∣E-T 、 T∷=F∣T*F∣T/F 、 F∷=(E)∣i，写出该文法的开始符号、终结符号集合VT、非终结符号集合VN。
开始符号：E
Vt={+, - , * , / ,（ , ）, i} Vn={E , F , T}
2.7 对2.6题的文法，写出句型T+T*F+i的短语、简单短语以及句柄。 短语：T+T*F+i T+T*F i i T T*F 简单短语：i T*F T 句柄：T
2.8 设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？
E E E T + T + T * F T F i
S S * S S S + S S + S a a S * S a a a a
根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。
2.9 写一文法，使其语言是奇正整数集合。 A::=1|3|5|7|9|NA N::=0|1|2|3|4|5|6|7|8|9
2.10给出语言{anbm|n,m≥1}的文法。 G[S]: S::=AB A::=aA|a B::=bB|b
3.1 有正则文法G[Z]：Z::=Ua|Vb，U::=Zb|b，V::=Za|a ，画出该文法的状态图，并检查句子abba是否合法。
解：该文法的状态图如下：
S a b U b a V b a Z
句子abba合法。
3.2 状态图如图3.35所示，S为开始状态，Z为终止状态。写出相应的正则文法以及V，Vn和Vt。
S b a b Z A a 图3-35状态图
解： 左线性文法G[Z]: 右线性文法G’[S]:
Z::=Ab|b S::=aA|b
A::=Aa|a A::=aA|b
V={Z,A,a,b} V={S,A,a,b} Vn={Z,A} Vn={S,A} Vt={a,b} Vt={a,b}
3.3 构造下列正则表达式相应的NFA： 1(1|0)*|0
1(1010*|1(010)*1)*0 解：正则表达式：1(1|0)*|0 1、
S 2、
1(1|0)*|0 Z 0 S 1(1|0)* 3、
Z
S 1 4、
0 0 A 1 ε Z q0 1 正则表达式：1(1010*|1(010)*1)*0
0 0,1 q2 q1
0 1 1 1 3 ε 0 8 6 0 1 0 1 4 5 7 0 3.4
将图3.36的NFA M确定化
1 1 0 2 a a 图3.36 状态图 解： q0={0} a {0,1} b {1} 0 a,b 1