You have learned all the tools to optimize the execution of a regular expression; therefore, this chapter acts as a summary for everything you have learned so far.
You learned that the execution of regexes can be modeled using two types of automata: deterministic and nondeterministic FSM.
The execution time of a nondeterministic automaton can be exponentially measured in the number of its steps. The complexity comes from the need for backtracking.
Creating a deterministic finite state automaton from a nondeterministic automaton also has exponential complexity.
In most execution environments, ...