NFA构造DFA的子集算法
n 输入：一个NFA N
n 输出：一个DFA D
n 方法：为D构造一个转换表Dtran。D的每一个状态是一组NFA状态的集合。以下是一些构造需要用到的函数。
|
操作
|
描述
|
|
ε-closure(s)
|
能够从NFA的状态s开始只通过ε转换到达的NFA状态集合
|
|
ε-closure(T)
|
UsєTε-closure(s)
|
|
move(T,a)
|
能够从T中某个状态S出发通过标号为a的转换到达的NFA状态的集合
|
Ø 构造D的状态集合DStates和D的转换函数Dtran
|
一开始,ε-closure(s)是DStates中的唯一状态，且没有被标记;
while (DStates中存在未被标识的状态T) {
标识T;
for(每个输入符号a) {
U = ε-closure(move(T,a));
if(U不再DStats中) 将U加入DStates，且没有标识;
Dtran[T,a] = U;
}
}
|
Ø 计算ε-closure(T)的算法
|
将T的所有状态压入堆栈中;
将ε-closure(T)的内容初始化为T;
while (堆栈非空) {
将栈顶元素t弹出;
for(每个满足如下条件的u：从t出发有一个标号为ε的转换到达状态u)
if(u不再ε-closure(T)中){
将u加入到ε-closure(T)中;
将u压入栈中;
}
}
|
Ø 附模拟一个NFA
|
S = ε-closure(s0);
c = nextChar();
while(c != eof) {
S = ε-closure(move(S,c));
c = nextChar();
}
if(S ∩ F != ø) return true;
else return false;
|
</script>