NFA转换为DFA 构造子集算法
如果需要将NFA转为DFA 需要如下几个步骤
1、消除ε-跃迁
2.在单个输入字符上从一个状态进行多次转换。
NFA状态的操作
| 操作 | 说明 |
|---|---|
| ε-closrue(s) | 仅在ε-跃迁上从NFA状态s可到达的NFA状态集。 |
| ε-closrue(T) | 仅在ε-跃迁上从T中的一些NFA状态可到达的NFA状态集。 |
| Move(T,a) | 输入符号a从T中的某些NFA状态转换到的NFA状态集合。 |
首先使用NFA a(b|c)* 为例子
从n0开始，我们需要输入一个a之后能不消耗任何输入的情况下移动到哪里
这形成了一个新状态：n1, n2, n3, n4, n6,n7,n8, n9
可以组合成如下的子集
q1= {n1, n2, n3, n4, n6, n9}
q2 = {n5, n8, n9, n3, n4, n6}
q3 = {n7, n8, n9, n3, n4, n6}
DFA的转换表Dtran
| Dstates | a | b | c |
| q0 | q1 | ||
| q1 | q2 | q3 | |
| q2 | q2 | q3 | |
| q3 | q2 | q3 |
如图
