CMPUT 325 Special 8

Deterministic
Finite State Automata (DFA)

and/or Regular expressions are
used in many applications

e.g. string searching, pattern matching
and as

lexical analyzers for input to compilers.

Notice that they are efficient.

Basically, if a problem can be expressed
as a DFA

then each character causes at most
O(1) computational

effort => O(n) execution time.

To reduce the coefficient (in the O(n))
you can minimize the

DFA -- an interesting algorithmic
problem.