The design of an efficient lexical analyzer

When building an automaton from a regular expression r (of length | r |) two options at least are possible.

• Apply Thompson's algorithm to build a NFAIT. Then the number of states is $\cal {O}$( | r | ).
• Apply Thompson's algorithm and the subset algorithm to build a DFA. Then the number of states is $\cal {O}$(2 ^{| r |} ).

Now given a word w of length $\ell$ deciding whether w is a member of L(r) (the language denoted by r) will cost

• $\cal {O}$($\ell$  | r | ) with the NFAIT and
• $\cal {O}$($\ell$) with the DFA.

We present now a method that minimizes the number of states of a DFA. So this method applies to improve the second option.