DOC《第2章：》

第2章: 第3章: 1.

已知文法G[A],写出它定义的语言描述 如:G[A]: A → 0B|1C B → 1|1A|0BB C → 0|0A|1CC 答案:G[A]定义的语言由

0、1符号串组成,串中0和1的个数相同. 2.给出语言描述,构造文法. 如:构造一文法,其定义的语言是由算符+和运算对象a构成的算术表达式的集合. 答案1: G[E] E→E+T|T T→T*F|F F→(E)|a 答案2: G[E] E→E+E|E*E|(E)|a 有很多答案,可能都能达到目的,但普遍叙述不够简洁. 第4章:

1、叙述正规式(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*描述的语言. 所有由偶数个0和偶数个1构成的串.

2、写出语言"由偶数个0和奇数个1构成的所有0和1的串"的正规式. Even0even1 ( (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* Even0odd1 (

1 even0even1 | 0(00|11)*(01|10)even0even1

3、构造一个DFA,它接受∑={0,1}上0和1的个数都是偶数的字符串.

4、处于/* 和*/之间的串构成注解,注解中间没有*/.画出接受这种注解的DFA的状态转换图. 第5章P99 练习:

1、5 1.(1) S=>(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(S))=>(a,(a)) S=>(T)=>(T,S)=>(S,S)=>((T),S)=>((T,S),S)=>((T,S,S),S)=>((S,S,S),S)=>(((T),S,S),S) =>(((T,S),S,S),S)=>(((S,S),S,S),S)=>(((a,S),S,S),S)=>(((a,a),S,S),S)=>(((a,a),∧,S),S) =>(((a,a), ∧,(T)),S)=>(((a,a), ∧,(S)),S)=> (((a,a), ∧,(a)),S)=> (((a,a), ∧,(a)),a) (2)S=>a|∧|(T) T=>aB|∧B|(T)B B=>,S|e 5. ->beginend ->(a | if b then a | if b then a else )|B B->;

(a | if b then a | if b then a else )|e -> a | if b then a | if b then a else 第6章P122 练习

1、2 1.(1)FIRSTVT(S)={a,FIRSTVT(T)={a, LASTVT(S)={, , a, ∧,) } LASTVT={, , a, ∧,)} (4)符号栈 当前符号 剩余输入串 以进或规约 a, a) # 移进 # ( a , a)# 移进 # ( a , a)# 规约 # (N , a)# 移进 # ( N,a )# 移进 #( N, a 规约 # (N,N 规约 # (N 移进 #(N)规约 # N 分析成功

2 (1) S=>(T)=>(T,S)=>(T,(T))=>(T,(T,S))=>(T,(T, a))=>(T,(S, a ))=>(T,(a, a))=>(S,(a, a)) =>(a,(a, a)) (2) S=>(T)=>(T, S)=>(T, a)=>(S, a)=>(a , a) 第7章P166

2、

3、9 第8章P203

3、4 E E E E

2 E + E E * E

8 5

4 5 6