Up: No Title
Previous: From a Regular Expression
- 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 2N).
- Often the number of reachable sets of states is much smaller.