From an NFA to a DFA

• Problem: Executing an NFA needs backtracking , which is inefficient.
• We would prefer a DFA.
• Idea: Do all possible choices in parallel.
• Construct a DFA, which has a state for each possible set of NFA states.
• A DFA state is final if the set of its NFA states contains a final state.
• Since the number of states of an NFA is finite (say N), the number of possible sets of states is also finite (bounded by 2^N).
• Often the number of reachable sets of states is much smaller.