子集构造转换为使用dfanfa.pdfVIP

EachstateoftheDFAisasetofstatesoftheNFA.

TheinitialstateoftheDFAistheε-closureoftheinitialstateoftheNFA.

CLOSE{0}={0,1,3}=S0

DeterminethetransitionfunctionoftheDFAonallinputs.

BeginwiththeinitialstateS0,anddeterminethetransitiononinputa.

CLOSE{0}={0,1,3}=S0

δ(S,a)=CLOSE{1,2}

0

Theε-closureoftheset{1,2}is{1,2,3}

ThisisanewstateintheDFA,callitS1.

CLOSE0=

{}{{0,1,3}=S00

δ(S,a)=CLOSE{1,2}={1,2,3}=S

01

WiththeinitialstateS,determinethetransitiononinputb.

0

CLOSE{0}={0,1,3}=S0

δδ(S(S,a)a)CLOSE{1CLOSE{1,2}2}{1{1,22,3}3}SS

0011

δ(S0,b)=CLOSE{3}

Theε-closureoftheset{3}is{1,3}.

ThisisanewstateintheDFA,callitS2.

CLOSE{0}={0,1,3}=S0

δ(S,a)=CLOSE{1,2}={1,2,3}=S

01

δ(S0,b)=CLOSE{3}{1,3}=S2

DeterminethetransitionfunctionoftheDFAfromstateSon

1

inputsaandb.OnathereisnowheretogointheNFA,sowe

createa“sink““tra”stateforDFA.

(p)

δ(S,a)=CLOSE{1,2}={1,2,3}=S

01

δ(S,b)=CLOSE{3}={1,3}=S

02

δδ(S,a)=CLOSE{}∅=S

13

DeterminethetransitionfunctionoftheDFAfromstateSon