对于该语言，存在一个由以下产生式定义的上下文无关文法G[S]： S→AB
A→ε.aAbb B→ε.cB
（2）同样，要产生形如anbmc2m的串，可以分别产生形如an和形如bmc2m的串。对于该语
言，存在一个由以下产生式定义的上下文无关文法G[S]： S→AB A→ε.aA B→ε.bBcc
（3）考虑在先产生同样数目的a,b，然后再生成多余的a。以下G[S]是一种解法： S→aSb.aS.ε
（4）以下G[S]是一种解法： S→aSd.A.D A→bAd.B D→aDc.B B→bBc.ε
注：a不多于d时，b不少于c；反之，a不少于d时，b不多于c。前一种情形通过 对应A，后一种情形对应D。 （5）以下G[S]是一种解法： S→Ab A→BAB.a
B→a.b 问题9：
下面的文法G(S)描述由命题变量p、q，联结词∧（合取）、∨（析取）、.（否定）构 成的命题公式集合： S→S∨T.T T→T∧F.F F→.F.p.q
试指出句型.F∨.q∧p的直接短语（全部）以及句柄。 答案：
直接短语：p，q，.F 句柄：.F 问题10：
设字母表A={a}，符号串x=aaa，写出下列符号串及其长度：x0,xx,x5以及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…} 问题11：
令Σ={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 问题12：
已知文法G[Z]：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,请写出全部由此文 法描述的只含有四个符号的句子。 答案：
Z=>U0=>Z10=>U010=>1010 Z=>U0=>Z10=>V110=>0110 Z=>V1=>Z00=>U000=>1000 Z=>V1=>Z00=>V100=>0100 问题13：
已知文法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} 问题14：
已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i，写出该文法的开 始符号、终结符号集合VT、非终结符号集合VN。 答案：
开始符号：E
VT={+,-,*,/,（,）,i} VN={E,F,T} 问题15：
设有文法G[S]：S∷=S*S|S+S|(S)|a，该文法是二义性文法吗？ 答案：
根据所给文法推导出句子a+a*a，画出了两棵不同的语法树，所以该文法是二义性文法。 问题16：
写一文法，使其语言是奇正整数集合。 答案：
A::=1|3|5|7|9|NA
N::=N0|N1|N2|N3|N4|N5|N6|N7|N8|N9| N::=0|1|2|3|4|5|6|7|8|9 S S*S S+S a a a S S+S a S*S a a
第4章词法分析 第1题
构造下列正规式相应的DFA. （１）1(0|1)*101
（２）１(1010*|1(010)*1）*0 （３）a((a|b)*|ab*a)*b （４）b((ab)*|bb)*ab 答案：
(1)先构造NFA：
用子集法将NFA确定化 . 0 1 X . A A A AB AB AC AB AC A ABY ABY AC AB 除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA 的终态），所以D为终态。 . 0 1 X . A A A B B C B C
A D D C B
DFA的状态图：: (2)先构造NFA：
用子集法将NFA确定化 ε 0 1 X X T0=X A A ABFL T1=ABFL Y CG Y Y CG CGJ T2=Y T3=CGJ DH K DH DH K
ABFKL T4=DH EI EI
ABEFIL T5=ABFKL Y CG
T6=ABEFIL EJY CG EJY
ABEFGJLY
T7=ABEFGJLY EHY CGK EHY
ABEFHLY CGK
ABCFGJKL T8=ABEFHLY EY CGI EY
ABEFLY CGI CGJI
T9=ABCFGJKL DHY CGK DHY DHY
T10=ABEFLY EY CG
T11=CGJI DHJ K DHJ DHJ
T12=DHY EI
T13=DHJ EIK EIK
ABEFIKL
T14=ABEFIKL EJY CG X 1 A εB
1 C 0 D 1 E 0 ε
F 1 G 0 H 1 I 0 J 1 K L εε