清华版编译原理课后答案——第四章参考答案

1、第四章参考答案第1题：(1) 0,1 1 1 0 1cbas z确定化：i0i1saaaababacabacaabz+abzacab s abc z重新命名，令ab为b、ac为c、abz为z其中s为初态，z为终态01saaabbcbcad+zcba,b(3)abzas aabb确定化：iaibsaaabazabababz+azabaz+abzababz 0 1 2 3 4重新命名，以0、1、2、3、4代替s,a, ab,az,abz得dfa其中0为初态，3，4为终态iaib01123224+323+424第2题：i0i1xzx+zxzy+xzxzxyyxyxyxyzx+xyzxyzxy a b

2、 c def重新命名，以a、代替x,z ,xz , y , xy ,xyz得dfa其中a为初态，为终态01aba+bcd+ccedeefa+ffe第3题：确定化：.i0i1svqquvqvzququvquz+vzzzvz.+quzvzquz+zzz a bcdefg重新命名，以a、代替s,vq ,qu , vz , v ,quz,z得dfa其中a为初态，d，f，g为终态.01abcbdccef+dggeg.+fdf+ggg第4题：(1)确定化：iaib+0011+0101110 a b c重新命名，以、代替0、01、1得其中a为初态，a，b为终态ab+abc+bbcca最小化：初始分划得终态组

3、a,b，非终态组c0：a,b，c 对终态组进行审查，判断a和b是等价的，故这是最后的划分重新命名，以a、c代替a,b、c得dfaab+aacca(2)这是dfa，直接最小化初始分划得：终态组0，非终态组1,2,3,4,50：0，1,2,3,4,5 对1,2,3,4,5进行审查： 4 输入a后到达0，1,2,3,5输入a后到达1,3,5，故得到新分划 0,1,3,5，41：0，4，1,2,3,5 对1,2,3,5进行审查：1,5 输入b后到达4，2,3 输入b后到达2,3，故得到新分划 1, 5，2,32：0，4，1, 5，2,3对1, 5，2,3进行审查：1, 5 输入a后到达1, 5 2 输

4、入a后到达1，3 输入a后到达3，故得到新分划2，33：0，2，3，4，1, 5 这是最后分划了重新命名，以0，2，3，4，1代替0，2，3，4，1, 5得dfa略 bbbbbabaasaaqbzabd第7题首先判断e，f为多余状态根据正则文法转化为nfa的方法构造nfa 确定化：iaib-absaq012aabz113qqdz224+bzqd+325+dzab+416dab516bqd6250123456最小化：初始分划得：终态组3,4，非终态组0,1,2,5,60：3,4,0,1,2,5,6对0,1,2,5,6进行审查：1,2输入b到达3,4，而0,5,6输入b到达2,5,6，故得到新分划

5、1,2,0,5,61：3,4,1,2,0,5,6 对0,5,6进行审查：0经过b到达，5,6经过b到达5,6，故得到新分划05,63：0，1,2，3,4，5,6 这是最后划分了。重新命名，以0，1，3，5代替0，1,2，3,4，5,6得dfa略第9题这是dfa，直接最小化初始分划得：终态组6,7，非终态组1,2,3,4,50：6,7,1,2,3,4,5对1,2,3,4,5进行审查：1,2输入b到达2，而3,4输入b到达6,7，5输入b不会有任何动作，故得到新分划1,2,3,4,51：6,7,3,4,5,1,21 35b6cab这是最后划分了。重新命名，以1，3，5，6代替1,2,3,4,5,6,7得dfaba d所识别的语言是b*a (c| da)*bb*第11题根据正则文法（左线性文法）转化为nfa的方法构造nfa：bz asaaa确定化：iaib-ab+zsaa+011aas12+asasa+221012重新命名，以0、1、2代替zs、a、as得dfa其中0为初态，0，2为终态b12aa,ba0所识别的语言是：| (a|b) a (ba|a)*第13题（1） 假设d a,b,y,z n 0,1,2,8