第三章-子集构造法

Operations on NFA states

伪代码

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

使用子集构造法构造DFA。

例题

思路

从状态0开始，我们可以在不消耗任何输入的情况下移动到哪里？

这形成了一个新状态：0,1,2,4,7这个新状态定义了什么转换？

这给出了DFA的转换表Dtran：

Dtran

应用子集构造的结果

DFA

习题

该DFA识别的语言也是a（a | b）*b，求出DFA的转换图

NFA

Dtran

DFA

使用子集构造从NFA构造DFA。

b(a|b)${}^{+}^+$a

NFA

Dtran

DFA