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

第四章1.设字母表={0，1}，给出上的正规式r=(0|10)*，请完成以下任务：1)构造NFAM`，使得L（M`）=L（r）；2)将NFAM`确定化、最小化，得到最简DFAM，使得L（M）=L（M`）。解：1）M`为：(0|10)*⇨①④0εε⇨①②④01③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},ε-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))=ε,00⇨①③101②化简后为：0⇨①01②2.已知正规文法G1(S为开始符号)G1:S→0A|1BA→1S|1B→0S|01）该文法产生语言是什么？请用正规式表示；2）构造最简的确定有限自动机DFA，并画出状态转换图。解：1)S=0A|1BS=(0(1S|1))|(1(0S|0))S=(01(S|ε))|(10(S|ε))S=(01|10)(S|ε)S=(01|10)(01|10)*2)NFA为：ɛ0101②③④⑩⑪⑫ɛɛɛɛɛɛ①⑧⑨⑯⑰ɛ10ɛɛ10ɛ⑤⑥⑦⑬⑭⑮ɛ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(T1,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))={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(Move(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为：101②④⑥⑧0001①1110③⑤⑦⑨011化简后为：②001①④10③13.将R=a(a|d)*转换成相应的正规文法。解:令S是文法的开始符则S→a(a|d)*S→aAA→(a|d)BB→(a|d)BA→εB→ε进一步变换得：S→aAA→aBA→dBA→εB→aBB→dBB→ε正规文法G[S]为：({a,d},{S,A,B},S,{S→aA,A→aB,A→dB,A→ε,B→aB,B→dB,B→ε})4．将文法G[S]：1）S-aA2）S-a3）A-aA4）A-dA5）A-a6）A-d转换成相应的正规式。解：S=aA|aA=aA|dA|a|d=(a|d)A|(a|d)=(a|d)＊|(a|d)=(a|d)+则：S=a(A|ε)=a((a|d)+|ε)=a(a|d)＊