From regular expressions to deterministic automata.
01 January 1986
The main theorem allows an elegant algorithm to be refined into an efficient one. The elegant algorithm for constructing a finite automaton from a regular expression is based on "derivatives of" regular expressions; the efficient algorithm is based on "marking of" regular expressions.