- 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.