第03章 文法和语言 下载本文

内容发布更新时间 : 2024/3/29 0:45:32星期一 下面是文章的全部内容请认真阅读。

对于该语言,存在一个由以下产生式定义的上下文无关文法 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,画出了两棵不同的语法树,所以该文法是二义性文法。

S

S * S

S + S 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 a S * S

a a