习题
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
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}
{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
可最小化，终态组为{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