第三章-子集构造法

Operations on NFA states

alt

伪代码

put ε-closure({s0}) as an unmarked state into the set of DFA (DStates)
//ε-闭包（{s0}）是通过ε-跃迁从s0可以访问的所有状态的集合。
while (there is one unmarked S1in DStates) do 
	begin
    mark S1
    for each input symbol a do
    	begin
        	S2 ← ε-closure(move(S1,a))//set of states to which there is a transition on a from a state s in S1
            if (S2 is not in DStates) then
            	add S2 into DStates as an unmarked state
            transfunc[S1,a] ← S2
        end
    end

push all states in T onto stack;
initialize ε-closure(T) to T;
while stack is not empty do begin
	pop t, the top element, off the stack;
	for each state u with edge from t to u labeled ε do 
		if u is not in ε-closure(T) do begin
			add u to ε-closure(T) ;
			push u onto stack
	end
end