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