1.构造正规式的DFA。 （1）1(0|1)*101
首先构造NFA：
ε 1 X A
NFA化为DFA： 状态转换表：
Q {X} A {ABC} B {BCD} C {BC} D {BCE} E {BCDY} Y
状态转换图：
A 1
初态
A B C D E Y 化简后得： 1 A B 0
0 B 1 ε C 1 D 0 E 1 Y 1 {ABC} B {BCD} C {BCD} C {BCD} C {BCDY} Y {BCD} C 1 0 C B 1 0 D 0 1 B C C C Y C 0 1 1 C 0 E1 0 1 Y 0 D E D D E 1 1 0 Y E 1 0
{BC} D {BCE} E {BC} D {BC} D {BCE} E 0 （2）(a|b)*(aa|bb)(a|b)*
a a 3
a a ε ε ε X 1 2 5 Y
b b b b 4 ？ NFA化为DFA： Q {X 1 2} {1 2 3} {1 2 4} {1 2 3 5 Y} {1 2 4 5 Y} {1 2 4 Y} {1 2 3 Y} {1 2 3} {1 2 3 5 Y} {1 2 3} {1 2 3 5 Y} {1 2 3 Y} {1 2 3 Y} {1 2 3 5 Y} a {1 2 4} {1 2 4 } {1 2 4 5 Y} {1 2 4 Y} {1 2 4 5 Y} {1 2 4 5 Y} {1 2 4 Y} b
a 所以，DFA为： a a b X 1 3 a a b b b b 2 4 a b 化简得： a 1 a a a b X Y b b 2
b
5 b a 6 0 （3）（0|11*0）* ε X A 1
B
ε
C
1 NFA到DFA： Q {X A Y} X {B C D} A {A Y} B {C D} Y 1 X 0
化简后得；
0 X
ε 0 D ε Y 1 {B C D} A {C D} Y {B C D} A {C D} Y 0 {A Y} B {A Y} B {A Y} B {A Y} B A 1 0 B 0 1 1 Y 0 1 0 A 1 2.将下图确定化和最小化。
a a 0 1 a,b
解: 首先取A=ε-CLOSURE({0})={0}, NFA确定化后的状态矩阵为:
A B C
Q’ {0} {0,1} {1} a {0,1} {0,1} {0} b {1} {1} NFA确定化后的DFA为：
A a b C
b a
a B 将A,B 合并得:
A
a a b C 3.构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟在后边。
解：按题意相应的正规表达式是0*(0 | 10)*0*
构造相应的DFA，首先构造NFA为
0 0 0
ε ε ε ε X 0 1 3
1 0
2
用子集法确定化 I {X,0,1,3,Y} {0,1,3,Y} {2} {1,3,Y} I0 {0,1,3,Y} {0,1,3,Y} {1,3,Y} {1,3,Y} I1 {2} {2} / {2} S 1 2 3 4 0 2 2 4 4 1 3 3 3 Y
DFA为
0 1 0 2
1 1 0
1 4 3 0
编译原理 第2章习题课
