清华大学：《编译原理》课程教学资源_作业及answer

习题 构造正规式1(0|1)*101相应的DFA 将图416确定化: [讲义图416] 3把图417的最小化 [讲义图417] 4构造一个DFA,它接收Σ={0,1}上所有满足如下条件的字符串:每个1都有 0直接跟在右边。并给出该语言的正规式。 参考答案 1.解 0 c 确定化 A ABY AC 重新命名,令AB为B、AC为C、ABY为D A B C B C DFA:

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

2.解 QU QuZ QuZ QuZ Z 重新命名,令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。 E D E E DFA: 0.1 0 3.解 初始分划得I0:终态组{0},非终态组{1,2,3,4,5} 对非终态组进行审查 {1,2,3,4,5}ac{0,1,35} 而{0,1,3,5}既不属于{0},也不属于{1,234,5} ∵{4}ac{0},所以得新分划 对{1,2,3,5}进行审查 15}b∈{4} 2,3}bc{1,2,3,5},故得新分划 Ⅱ2:{0},{4},{1,5},{2,3}

2．解： 0 1 S VQ QU VQ VZ QU QU V QUZ VZ Z Z V Z QUZ VZ QUZ Z Z Z 重新命名，令 VQ 为 A、QU 为 B、VZ 为 C、V 为 D、QUZ 为 E、Z 为 F。 0 1 S A B A C B B D E C F F D F E C E F F F DFA： 0,1 0 0,1 C F 0 0 1 1 1 E 1 0 0 3．解： 初始分划得Π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}，故得新分划 Π2：{0}，{4}，{1, 5}，{2,3} {1, 5} a {1, 5} S A B D

2,3}ac{1,3},故状态2和状态3不等价,得新分划 ∏l3:{0},{2},{3},{4},{1,5} 这是最后分划了 最小DFA b b 4.构造一个DFA,它接受Σ={0,1}上所有满足如下条件的字符串:每个1都有0直接跟 在右边,并写出相应的正规式和正规文法。 解:按题意相应的正规表达式是0+(0110)*0*或0*(100+)*0* 构造相应的DFA,首先构造NFA为 用子集法确定化 X,01,3,Y}|{0,1,3,Y 0,1,3,Y} 0,1,3,Y} 2} 2 1,3,Y} 3 1,3,Y DFA为

{2,3} a {1,3}，故状态 2 和状态 3 不等价，得新分划 Π3：{0}，{2}，{3}，{4}，{1, 5} 这是最后分划了 最小 DFA： a b b 0 b a a a b b a 4．构造一个 DFA，它接受Σ＝{0,1}上所有满足如下条件的字符串：每个 1 都有 0 直接跟 在右边，并写出相应的正规式和正规文法。 解：按题意相应的正规表达式是 0*(0 | 10)*0*或 0*( 100*)*0* 构造相应的 DFA，首先构造 NFA 为 0 0 0 ε ε ε ε Y 1 0 用子集法确定化 I I0 I1 S 0 1 {X,0,1,3,Y} {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} 1 2 3 4 2 2 4 4 3 3 3 DFA 为 0 1 0 2 1 1 0 1 4 0 2 3 4 1 X 0 1 3 2 3

可最小化,终态组为{1,2.,4},非终态组为{3},{1,2.4}c{12,4},{1,2,4}c{3},所以 ,2,4为等价状态,可合并

可最小化，终态组为{1,2,4}，非终态组为{3}，{1,2,4}0  {1,2,4}，{1,2,4}1  {3}，所以 1,2,4 为等价状态，可合并。 0 1 1,2,4 0 3