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