清华大学-编译原理作业及answer.doc

《清华大学-编译原理作业及answer.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、习题1.构造正规式1(0

2、1)*101相应的DFA.2.将图416确定化：[讲义图416]3把图417的最小化：[讲义图417]4构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。参考答案1．解：0,11101CBAXY确定化01XAAAABABACABACAABYABYACAB重新命名，令AB为B、AC为C、ABY为D01XAAABBCBCADDCBDFA：1011101CBAXD002．解：01SVQQUVQVZQUQUVQUZVZZZVZQUZVZQ

3、UZZZZ重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。01SABACBBDECFFDFECEFFFDFA：0,1A00,1CF0S01B11E10D03．解：初始分划得Π0：终态组{0}，非终态组{1,2,3,4,5}对非终态组进行审查：{1,2,3,4,5}a{0,1,3,5}而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5}∵{4}a{0}，所以得新分划Π1：{0}，{4}，{1,2,3,5}对{1,2,3,5}进行审查：∵{1,5}b{4}{2,3}b{1,2,3,5}，故得新分划Π

4、2：{0}，{4}，{1,5}，{2,3}{1,5}a{1,5}{2,3}a{1,3}，故状态2和状态3不等价，得新分划Π3：{0}，{2}，{3}，{4}，{1,5}这是最后分划了最小DFA：a32bb0baaa14bba4．构造一个DFA，它接受Σ＝{0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边，并写出相应的正规式和正规文法。解：按题意相应的正规表达式是0*(0

5、10)*0*或0*(100*)*0*构造相应的DFA，首先构造NFA为000310XεεεεY102用子集法确定化II0I1S01{X,0,1,3,Y

6、}{0,1,3,Y}{2}{1,3,Y}{0,1,3,Y}{0,1,3,Y}{1,3,Y}{1,3,Y}{2}{2}/{2}12342244333DFA为01021101340可最小化，终态组为{1,2,4}，非终态组为{3}，{1,2,4}0{1,2,4}，{1,2,4}1{3}，所以1,2,4为等价状态，可合并。0131,2,40