But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity. I think it is worth saying that this is pos

But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst case time complexity. I think it is worth saying that this is possible because finite state automata have a set of useful, well-understood operations, like concatenation, union, intersection, negation, kleene closure, determinization, and minimization. This makes it possible to generate complex automata from basic building blocks and to make them deterministic and minimal.