Java Reference
In-Depth Information
Algorithm 2.2 -closure(s) for a State s
Input: a state, s
Output: -closure(s)
Set S.add(s) // S = fsg
return -closure(S)
Returning to our example, from the start state s
0
, and scanning the symbol a, we shall
want to go into a state that reflects all the states we could be in after scanning an a in the
NFA: 2, and then (via -moves) 5, 6, 7, 9, and 10. Thus,
m(s
0
;a) = s
1
; where
s
1
= -closure(2) = f2; 5; 6; 7; 9; 10g:
Similarly, scanning a symbol b in state s
0
, we get
m(s
0
;b) = s
2
; where
s
2
= -closure(4) = f4; 5; 6; 7; 9; 10g:
From state s
1
, scanning an a, we have to consider where we could have gone from the
states f2; 5; 6; 7; 9; 10g in the NFA. From state 7, scanning an a, we go into state 8, and
then (by -moves) 7, 9, and 10. Thus,
m(s
1
;a) = s
3
; where
s
3
= -closure(8) = f7; 8; 9; 10g:
Now, from state s
1
, scanning b, we have
m(s
1
;b) = s
4
; where
s
4
= -closure(11) = f11g
because there are no -moves out of state 11.
From state s
2
, scanning an a takes us into a state reecting 8, and then (by -moves) 7,
9, and 10, generating a candidate state, f7; 8; 9; 10g.
But this is a state we have already seen, namely s
3
. Scanning a b, from state s
2
, takes
us into a state reecting 11, generating the candidate state, f11g.
But this is s
4
. Thus,
m(s
2
;a) = s
3
; and
m(s
2
;b) = s
4
:
From state s
3
we have a similar situation. Scanning an a takes us back into s
3
. Scanning
a b takes us into s
4
. So,
m(s
3
;a) = s
3
; and
m(s
3
;b) = s
4
:
There are no moves at all out of state s
4
. So we have found all of our transitions and all
of our states. Of course, the alphabet in our new DFA is the same as that in the original
NFA.
But what are the final states? Because the states in our DFA mirror the states in our
original NFA, any state reflecting (derived from a state containing) a final state in the NFA
Search WWH ::
Custom Search