1、 第 3章 文法和语言 第 1题 文法 G (A,B,S,a,b,c,P,S)其中 P为： SAc|aB Aab Bbc 写出 L(GS)的全部元素。 答案： L(GS)=abc 第 2题 文法 GN为： N D|ND D 0|1|2|3|4|5|6|7|8|9 GN的语言是什么？ 答案 : GN的语言是 V+。 V=0,1,2,3,4,5,6,7,8,9 N=ND=NDD. =NDDDD.D=D.D 或者：允许 0开头的 非负整数？ 第题 为只包含数字、加号和减号的表达式，例如 9-2 5， 3-1，等构造一个文法。 答案： GS: S-S+D|S-D|D D-0|1|2|3|4|5|6|7
2、|8|9 第 4题 已知文法 GZ： Z aZb|ab 写出 L(GZ)的全部元素。 答案： Z=aZb=aaZbb=aaa.Z.bbb= aaa.ab.bbb L(GZ)=anbn|n=1 第 5题 写一文法，使其语言是偶正整数的集合。 要求： (1) 允许 0打头； (2)不允许 0打头。 答案： (1)允许 0开头的偶正整数集合的文法 ENT|D TNT|D ND|1|3|5|7|9 D0|2|4|6|8 (2)不允许 0开头的偶正整数集合的文法 ENT|D TFT|G ND|1|3|5|7|9 D2|4|6|8 FN|0 GD|0 第 6题 已知文法 G： := := * :=（ ）
3、i 试给出下述表达式的推导及语法树。 （） i+(i+i) （） i+i*i 第 8题 文法 GS为： S Ac|aB A ab B bc 该文法是否为二义的？为什么？ 答案： 对于串 abc (1)S=Ac=abc (2)S=aB=abc 即存在两不同的最右推导。所以，该文法是二义的。 或者： 第 10题 文法 S S(S)S| (1) 生成的语言是什么？ (2) 该文法是二义的吗？说明理由。 答案： （） 嵌套的括号 （） 是二义的，因为对于（）（）可以构造两棵不同的语法树。 第 11题 令文法 GE为： ET|E+T|E -T TF|T*F|T/F F(E)|i 证明 E+T*F 是它的
4、一个句型，指出这个句型的所有短语、直接短语和句柄。 第 14题 给出生成下述语言的上下文无关文法： （ 1） anbnambm| n， m=0 （ 2） 1n0m 1m0n| n，m=0 （ 3） WaWr|W属于 0|a*， Wr表示 W的逆 答案： （） SAA AaAb| （） S1S0|A A0A1| （） S 0S0|1S1| 第 16题 给出生成下述语 言的三型文法： (1)an|n =0 (2) anbm|n,m=1 (3)anbmck|n,m,k=0 答案： (1) SaS| (2) SaA AaA|B BbB|b (3) AaA|B BbB|C CcC| 第 18题 解释下列
5、术语和概念： （） 字母表 （） 串、字和句子 （） 语言、语法和语义 答案： （） 字母表：是一个非空有穷集合。 （）语言：它是由句子组成的集合，是由一组记号所构成的集合。程序设计的语言就是所 有该语 言的程序的全体。语言可以看成在一个基本符号集上定义的，按一定规则构成的一切基本符号串组成的集合。 语法：表示构成语言句子的各个记号之间的组合规律。程序的结构或形式。 语义：表示按照各种表示方法所表示的各个记号的特定含义。语言所代表的含义。 附加题 问题 1： 给出下述文法所对应的正规式： S0A|1B A1S|1 B0S|0 答案： R = (01 | 10) ( 01 | 10 )* 问题
6、2： 已知文法 GA，写出它定义的语言描述 GA: A 0B|1C B 1|1A|0B B C 0|0A|1CC 答案 : GA定义的语言由 0、 1符号串组成，串中 0和 1的个数相同 . 问题 3： 给出语言描述，构造文法 . 构造一文法 ,其定义的语言是由算符 +, *, (,)和运算对象 a构成的算术表达式的集合 . 答案一： GE EE+T|T TT * F|F F(E)|a 答案二： GE EE+E|E * E|(E)|a 问题 4： 已知文法 GS: S dAB A aA|a B |bB 相应的正规式是什么？ GS能否改写成为等价的正规文法？ 答案： 正规式是 daa*b*； 相
7、应的正规文法为 (由自动机化简来 )： GS:S dA A a|aB B aB|a|b|bC C bC|b 也可为 (观察得来 ):GS:S dA A a|aA|aB B bB| 问题 5： 已知文法 G： EE+T|E -T|T TT*F|T/F|F F(E)|i 试给出下述表达式的推导及语法树 (1) i; (2) i*i+i (3) i+i*i (4) i+(i+i) 答案： (1)E=T=F=i (2)E=E+T=T+T=T*F+T=F*F+T=i*F+T=i*i+T=i*i+F=i*i+i (3)E=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i (4)E=E+T=T+T=F+T=i+T=i+F=i+(E)=i+(E+T)=i+(T+T)=i+(F+T) =i+(i+T)=i+(i+F)=i+(i+i)
