====== 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: - Find the epsilon-closure of the starting state of the NFA. Call the resulting subset of NFA states ''I''. - Add ''I'' as a state to the DFA and make it the starting state. - While there are unprocessed states in the DFA, pick one such state, say ''S''. - For each character ''c'': - 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-''. - 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+''. - Make ''S+'' a state of the DFA, unless it already exists. - Add ''S -> S+'' as a ''c''-transition to the DFA - Mark ''S'' as processed - Mark all DFA states that contain a final state of the NFA as a final state of the DFA.