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.