资源描述：
《编译原理(习题课)(二).pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编译原理朱雪峰博士计算机科学与技术系Tel:89733787(O)Email:xuefeng.zhu@cup.edu.cn1第六题（P36第11题）解：分析L，要求b和c的个数一样多，因此可以使用一个非2终结符去生成bncn串，而用另外一个非终结符去生成ai，因此，可以模拟L使用一个非终结符去生成bncn，而用1另外一个非终结符去生成ai。L的文法：2S→ABA→aA
2、εB→bBc
3、bc2第六题（P36第11题）解：分析L，可以将anbnambm分成两段考虑，即anbn和ambm，3然后使用两个非终结符分别去产生它们。L的文法：3S→ABA→aAb
4、εB→aBb
5、ε3第六题（P
6、36第11题）解：L不能采用分段处理的方式，它要求中间的0和1的个数4相同，而且一前一后的1和0的个数相同。对于这种文法我们可以采用从里向外扩展的方式进行，即先用一个非终结符生成处于中间的m个0和m个1，然后，使用另外一个非终结符在该串的基础上扩充前后的n个1和n个0。L:4A→0A1
7、εS→1S0
8、A4第七题（P64第7题）7.构造下列正规式相应的DFA①1(0
9、1)*101②1(1010*
10、1(010)*1)*0③0*10*10*10*④(00
11、11)*((01
12、10)(00
13、11)*(01
14、10)(00
15、11)*)*5第七题（P64第7题①）6第七题（P64第7题①）状态
16、01{X}0ø{1,2,3}1{1,2,3}1{2,3}2{2,3,4}3{2,3}2{2,3}2{2,3,4}3{2,3,4}3{2,5,3}4{2,3,4}3{2,3,5}4{2,3}2{2,3,4,Y}5{2,3,4,Y}5{2,5,3}4{2,4,3}37状态01{X}0ø{1,2,3}1第七题（P64第7题①）{1,2,3}1{2,3}2{2,3,4}3{2,3}2{2,3}2{2,3,4}3{2,3,4}3{2,5,3}4{2,3,4}3{2,3,5}4{2,3}2{2,3,4,Y}5{2,3,4,Y}5{2,5,3}4{2,4,3}38第七题（P64第7题①）ł初
17、始划分：{{0,1,2,3,4},{5}}，{0,1,2,3,4}={2,4,_},0{0,1,2,3,4}={1,3,5}。由于0不能接受字符0，需要把状态10划分出来；另外，只有状态4读入字符1后进入状态5，因此将状态4划分出来，划分的结果为4个集合：{{0},{1,2,3},{4},{5}}。ł对于集合{1,2,3}，由于{1,2,3}={2,4}，因此需要对0{1,2,3}进一步划分，划分结果为5个集合：{{0},{1,2},{3},{4},{5}}。检查集合{1,2}，由于{1,2}0={2},{1,2}1={3}，不需要进一步的划分。所以最终划分结果为5个集合：{{
18、0},{1,2},{3},{4},{5}}9第七题（P64第7题①）10第七题（P64第7题②）1(1010*
19、1(010)*1)*011第七题（P64第7题②）状态01状态01{1}ø{2}{4,7,9}ø{5,8,2}{2}{9}{3,6}{5,2,9}{5,2,9}{3,6}{9}øø{3,6,8}{4,7,6}{2}{3,6}{4,7}{2}{4,7,6}{7}{5,8,2}{4,7}ø{5,8,2}{7}ø{8}{5,8,2}{5,2,6,9}{3,6}{8}{6}ø{5,2,6,9{5,2,7,9}{3,6,2}{6}{7}{2}{5,2,7,9}{5,2,9}{3
20、,6,8}{3,6,2}}{4,7,9}{3,6,2}12第七题（P64第7题②）13第七题（P64第7题③）0*10*10*10*14第七题（P64第7题④）(00
21、11)*((01
22、10)(00
23、11)*(01
24、10)(00
25、11)*)*15第七题（P64第7题④）状态01{1}{2}{3}{2}{1,4}ø{3}ø{1,4}{1,4}{2,5}{3,7}{2,5}{1,4}{6}{3,7}{6}{1,4}{6}{8,10}{9,12}{8,10}{6}{11,4}{9,12}{11,4}{6}{11,4}{13,5}{14,7}{5,13}{11,4}{6}{14,7}{
26、6}{11,4}16第七题（P64第7题④）17第八题（P64第8题）8.给出下面正规表达式：①以01结尾的二进制数串；②能被5整除的十进制整数；③包含奇数个1或奇数个0的二进制数串；④英文字母组成的所有符号串，要求符号串中的字母依照字典序排列；⑤没有重复出现的数字的数字符号串的全体；⑥最多有一个重复出现的数字的数字符号串的全体；⑦不包含子串abb的由a和b组成的符号串的全体。18第八题（P64第8题）解：（1）本题要求的是二进制串，即由0和1构成的串，并且必须以01结尾，所以本题可以分两部
