The construction of finite automata from regular expressions is of central importance to a growing number of applications that include the compilation of communicating processes, string pattern matching, model checking, lexical scanning, and VLSI layout design. 40 years of algorithmic progress began with several theoretical results in the 1950's. Regular languages were characterized by Kleene (1956) both in terms of regular expressions and Deterministic Finite Automata (DFA's); Rabin and Scott (1959) characterized the regular expressions in terms of Nondeterministic Finite Automata; and Myhill (1957) and Nerode (1958) described the existence of a minimum-state DFA nonconstructively.
Rabin and Scott were the first to present an algorithmic solution to the transformation of regular expressions to NFA's, NFA's to DFA's, and DFA's to minimum state DFA's. The most efficient algorithms to solve all three transformations are due to Keller and Paige (1996) and Chang and Paige (1997). Most unusual about our solutions is that they were obtained by means of qualitative methods in theoretical programming languages. Program transformations and type theory played significant roles in the DFA minimization algorithm; Program transformations and Rule Induction (which is important to Formal Semantics) were crucial to the discovery and anaysis of the algorithm to turn regular expressions into compressed NFA's.
Click here to continue.