【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《构造正规式相应的DFA》，欢迎阅读！
构造正规式相应的DFA：1(0|1)*101 按照以下三步：
（1）由正规表达式构造转换系统（NFA）
（2）由转换系统（NFA）构造确定的有穷自动机DFA （3）DFA的最小化
答：（1）首先构造与正规式1（0|1）*101相应的NFA，然后再将NFA确定化。为正规式构造NFA的方法为“语法制导”法，即依据正规式的语法构造来构造。首先将正规式r=1（0|1）*101分解成r=r1,r2r3，其中：
r1=1，r2=（0|1）*，r3=101。 对于r1，有：
1
X
A
对于r2，有：
0,1
A
对于r3，有：
1
X
B
0
C
1
Y
因此，与正规式r=r1r2r3相对应的NFA如图所示为：
0,1
1
X
A
1
B
0
C
1
Y
展开为：
0
1
X
A1
ε
A2
ε
1
A3
B
0
C
1
Y
1
（2）将NFA转换成DFA 采用子集法，即DFA的每个状态对应NFA的一个状态集合。构造DFA的状态集C，假定C={T0，T1，…Ti}，集中T0=ε-closure（X），对于任何a∈∑Ti=ε-closure（Move（Ti，a））。 Ti
{A0} T0 {A1，A2，A3} T1 {A2，A3} T2 {A2，A3，A4} T3 {A2，A3，A5} T4 {A2，A3，A4，A6} T5
DFA的状态转换图
0 1
1
T1
Ti0 {}
{A2，A3}=T2 {A2，A3}=T2 {A2，A5，A3}=T4 {A2，A3}=T2 {A2，A5，A3}=T4
Ti1
{A1，A2，A3}=T1 {A2，A4，A3}=T3 {A2，A4，A3}=T3 {A2，A4，A3}=T3 {A2，A4，A6，A3}=T6 {A2，A4，A3}=T3
0
0
0
T2
T0
1
T3 T4
1
T5
0 1
1
（3）化简DFA：分割法，把DFA的状态集分成一些不想交的子集，使得不同的两子集的状态是可区别的，同一子集的状态是等价的。首先，将状态分成两个子集：一个由终态组成，一个由非态组成：{T0，T1，T2，T3，T4} {T5} {T0，T1，T2，T3} {T4} {T5} { T0，T1，T2} {T3} {T4} {T5} {T0} {T1，T2} {T3} {T4} {T5}
在等价状态子集{T1，T2}中选状态T2做代表，消去其他状态T1，把从消去状态T1射出和
本文来源：https://www.wddqxz.cn/35525a92f58a6529647d27284b73f242326c3113.html
2023-05-07
