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，画出了两棵不同的语法树，所以该文法是二义性文法。