Convert NFA into DFA

Convert the NFA into DFA
For each NFA we can find a DFA accepting the same language. The number of states of the DFA could be exponential in the number of states of the NFA, but in practice this worst case occurs rarely.
Algorithm. Constructing a deterministic finite automaton from a nondeterministic one.
Input: An NFA N.
Output: A DFA D accepting the same language.
Method: Each state of D is a set of states which N could be in after reading some sequence of input symbols. Thus D is able to simulate all possible moves N can make on a given input string. The initial state of D is the set consisting of S0, the initial state of N, together with all states of N that can be reached from S0 by means of ?-transition only. The accepting states of D are those sets of states that contain at least one accepting states of N.
Let us define the function ?-CLOSURE (s) to be the set of states of N built by applying the following rules:-
1- S is added to ?-CLOSURE (s).
2- If t is in ?-CLOSURE (s), and there is an edge labeled ? from t to u, then u is added to ?-CLOSURE (s) if u is not already there. Rule 2 is repeated until no more states can be added to ?-CLOSURE (s).
Thus, ?-CLOSURE (s) is just the set of states that can be reached from S on ?-transition alone. If T is a set of states, then ?-CLOSURE (T) is just the union over all states S in T of ?-CLOSURE (S).
The computation of ?-CLOSURE (T) is a typical process of searching a graph for nodes reachable from a given set of nodes. In this case the nodes of T are the given set, and the graph consists of the ?- labeled edge of the transition diagram only. A simple algorithm to compute ?-CLOSURE (T) is shown in fig (12)
Begin
Push all states in T onto STACK;
?-CLOSURE (T):=T;
While STACK not empty do
Pop S, the top element of STACK, off of stack;
For each state t with an edge from S to t labeled ? do
If t is not in ?-CLOSURE (T) then
Begin
Add t to ?-CLOSURE (T);
Push t onto STACK;
End
End
End
Fig (12) Computation of ?-CLOSURE
The states of D and their transition are constructed as follows. Initially, let ?-CLOSURE (S0) be a state of D. This state is the start state of D. We assume each state of D is initially "unmarked". Then perform the algorithm of Fig (13).

While there is an unmarked state x= (S1, S2... Sn) of D do
Begin
Mark x;
For each input symbol a do
Begin
Let T be the set of states to which there is a transition on a from some state Si in x;
y: = e-CLOSURE (T);
If y has not yet been added to the set of states of D then
Make y an "unmarked" state of D;
Add a transition from x to y labeled a if not already present
End
End

Fig (13) The Subset Construction








Example Convert the NFA shown in fig (14) into DFA








Fig (14) NFA N for (a?b)*abb.
Fig (14) shows NFA N accepting the language (a?b)*abb. The initial state of the equivalent DFA is e-CLOSURE (0), which is A= {0, 1, 2, 4, 7}, since these are exactly the states reachable from state 0 via a path in which every edge is labeled e. Note that 0 is reached from itself by such a path, the path having no edges.
The algorithm of fig (13) tell us to set x to A and compute T, the set of states of N having transitions on a from members of A. Among the states 0, 1 ,2, 4 and 7, only 2 and 7 have such transition, to 3 and 8,so
y= e-CLOSURE ({3,8})={1, 2, 3, 4, 6, 7, 8}
Let us call this set B. Among the states in A, only 4 has a transition on b to 5, so the DFA has a transition on b from A to
C= e-CLOSURE ({5})= {1, 2, 4, 5, 6, 7}
Then we have two transitions:-
A B
A C
We continue this algorithm for state B and C.
1- For set B
a- If the input is a symbol "a", then only state 2 and 7 give a transition on symbol "a" to state 3 and 8, therefore e-CLOSURE({3,8})=B, then we have this transition
B B
b- If the input is a symbol "b", then only state 4 and 8 give a transition on symbol "b" to state 5 and 9, therefore
e-CLOSURE ({5, 9}) = {1, 2, 4, 5, 6, 7, 9}
Let us call this set D. Because a state D not added to the state of DFA, then we add it, with transition:-
B D

2- For set C
a- If the input symbol is "a", then only state 2 and 7 have transition on "a" to state 3 and 8, therefore
e-CLOSURE ({3, 8}) = B, then the transition is:
C B
b- If the input symbol is "b", then only state 4 gives a transition on b to state 5, therefore
e-CLOSURE (5) =C, then the transition is:-
C C
3- For set D:-
a- If the input symbol is "a", then only state 2 and 7 gives a transition on "a" to state 3 and 8, therefore
e-CLOSURE ({3, 8}) = B, then the transition is
D B

b- If the input symbol is "b" then only state 4 and 9 gives a transition on "b"
to state 5, and 10, therefore:-
e-CLOSURE ({5, 10}) = {1, 2, 4, 5, 6, 7, 10}
Let us call this E, then the transition:-
D E

4- For set E
a- If the input symbol is "a", then only state 2 and 7 given a transition on "a" to state 3 and 8, therefore:-
e-CLOSURE ({3, 8}) = B, then the transition is
E B
b- If the input symbol is "b", then only state 4 gives a transition on "b" to
state 5, therefore
e-CLOSURE (5) =C, then the transition is:-
E C
The transition table for DFA is shown in fig (15), and the DFA equivalent to NFA of fig (14) is shown in fig (16). The final state is E because it contain the state 10 which is the final state for NFA in fig (14).?









Fig (16): DFA accepting (a?b)*abb.




State Input
a b
A B C
B B D
C B C
D
B E
E B C

Fig (15) Transition Table