编译原理第四章典型习题答案

1、第四章1. 设字母表S=0，1，给出S上的正规式r=(0|10)*，请完成以下任务：1) 构造NFA M，使得L（M）=L（r）；2) 将NFA M确定化、最小化，得到最简DFA M，使得L（M）=L（M）。解：1）M为：(0|10)* 0 0 1 2) 1令T0=-closure(1)=1,2,4, T0未被标记，加入到子集族C中 2 标记T0，Move(T0,0)=2,-closure(Move(T0,0)=2,4=T1,T1未被标记，加入到子集族C中Move(T0,1)=3,-closure(Move(T0,1)=3=T2,T2未被标记，加入到子集族C中3 标记T1，Move(T1,0)

2、=2,-closure(Move(T1,0)=2,4=T1,Move(T1,1)=3,-closure(Move(T1,1)=3=T2,4标记T2，Move(T2,0)=2,-closure(Move(T2,0)=2,4=T1,Move(T2,1)= ,-closure(Move(T2,1)= , 0 0 1 0 1 化简后为： 0 0 1 2. 已知正规文法G1(S为开始符号) G1: S0A|1B A1S|1 B0S|0 1）该文法产生语言是什么？请用正规式表示；2）构造最简的确定有限自动机DFA，并画出状态转换图。解：1)S=0A|1B S=(0(1S|1)|(1(0S|0)S=(01(

3、S|)|(10(S|) S=(01|10)(S|)S=(01|10)(01|10)*2)NFA为： 0 1 0 1 1 0 1 0 NFA转化为DFA： 1令T0=-closure(1)=1,2,5, T0未被标记，加入到子集族C中 2 标记T0，Move(T0,0)=3,-closure(Move(T0,0)=3=T1,T1未被标记，加入到子集族C中Move(T0,1)=6,-closure(Move(T0,1)=6=T2,T2未被标记，加入到子集族C中3 标记T1，Move(T1,0)= ,-closure(Move(T1,0)= ,Move(T1,1)=4,-closure(Move(T

4、1,1)=4,8,9,10,13,17=T3,T3未被标记，加入到子集族C中4标记T2，Move(T2,0)=7,-closure(Move(T2,0)= 4,8,9,10,13,17=T4,T4未被标记，加入到子集族C中Move(T2,1)= ,-closure(Move(T2,1)= ,5标记T3，Move(T3,0)=11,-closure(Move(T3,0)=11=T5,T5未被标记，加入到子集族C中Move(T3,1)=14,-closure(Move(T3,1)=14=T6,T6未被标记，加入到子集族C中6标记T4，Move(T4,0)=11,-closure(Move(T4,0

5、)=11=T5,Move(T4,1)=14,-closure(Move(T4,1)=14=T6,7标记T5，Move(T5,0)= ,-closure(Move(T5,0)= ,Move(T5,1)=12,-closure(Move(T5,1)=9,10,12,13,16,17=T7,T7未被标记，加入到子集族C中8标记T6，Move(T6,0)=15,-closure(Move(T6,0)= 9,10,13,15,16,17=T8,T8未被标记，加入到子集族C中Move(T6,1)= ,-closure(Move(T6,1)= ,9标记T7，Move(T7,0)=11,-closure(Mo

6、ve(T7,0)=11=T5,Move(T7,1)=14,-closure(Move(T7,1)=14=T6,10标记T8，Move(T8,0)=11,-closure(Move(T8,0)=11=T5,Move(T8,1)=14,-closure(Move(T8,1)=14=T6,则DFA为： 1 0 1 0 0 0 1 1 1 1 0 0 1 1 化简后为： 0 0 1 1 0 1 3.将R=a(a|d)*转换成相应的正规文法。解:令S是文法的开始符则Sa(a|d)*SaA A(a|d)B B(a|d)B A B进一步变换得：SaA AaB AdB A BaB BdB B正规文法GS为：(a,d,S,A,B,S,SaA,AaB,AdB,A,BaB,BdB,B)4将文法GS：1）S-aA 2）S-a 3）A-aA 4）A-dA 5）A-a