Next: Minimal automaton
Up: Lexical Analysis
Previous: The role of the lexical
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
(  r  ).
 Apply Thompson's algorithm and the subset algorithm
to build a DFA.
Then the number of states is
(2^{  r  }).
Now given a word w of length deciding whether
w is a member of L(r) (the language denoted by r)
will cost

(  r  ) with the NFAIT and

() 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.
Subsections
Next: Minimal automaton
Up: Lexical Analysis
Previous: The role of the lexical
Marc Moreno Maza
20041202