Converting an NFA into a DFA

Definitions:

• epsilon-closure of a state: subset of states you can reach from this state using zero or more epsilon transitions.
• c-transition-set of a state: subset of states you can reach from this state by following a singe c-transition.

Algorithm:

1. Find the epsilon-closure of the starting state of the NFA. Call the resulting subset of NFA states I.
2. Add I as a state to the DFA and make it the starting state.
3. While there are unprocessed states in the DFA, pick one such state, say S.
   1. For each character c:
      1. Find the c-transition-set of S, by taking the union of the c-transition-sets of the individual NFA states in S. Call the resulting subset of NFA states as S-.
      2. Find the epsilon-closure of S-, by taking the union of the epsilon-closures of the individual NFA states in S-. Call the resulting subset of NFA states S+.
      3. Make S+ a state of the DFA, unless it already exists.
      4. Add S → S+ as a c-transition to the DFA
   2. Mark S as processed
4. Mark all DFA states that contain a final state of the NFA as a final state of the DFA.