how to write lex (6)

NFA -> DFA
算法是子集构造法.下面是龙书上关于这个算法的描述

initially,ε-closure(s0) is the only state in Dstates and it is unmarked;

while there is an unmarked state T in Dstates do begin

mark T;

for each input symbol a do begin

U := ε-closure(move(T,a));

if U is not in Dstates then

add U as an unmarked state to Dstates

Dtran[T,a] : = U

end

end

几个很重要的概念:

• ε-closure  就是当前状态通过ε边可以到达的所有状态的集合
• 集合的ε-closure  就是集合中所有状态的ε-closure的并集
• move(T,a) 就是T中所有状态通过a边可以到达的状态的集合

在实现上可以用FIFO队列来模拟Dstates, 那个 marked 不是必须的.
每个状态的ε-closure 可以事先计算好,每次查表即可.
对于转换后的DFA 初态就是ε-closure(s0) , 所有含有NFA终态的DFA状态为终态.
算法中具体操作和使用数据结构有关.