A taxonomy of finite automata construction algorithms
Bruce W. Watson · 1993
This paper presents a taxonomy of finite automata construction algorithms. Each algorithm is classified into one of two families: those based upon the structure of regular expressions, and those based upon the automata-theoretic work of Myhill and Nerode. Many of the algorithms appearing in the literature are based upon the structure of regular expressions. In this paper, we make this term precise by defining regular expressions as a \\Sigma-term algebra, and automata constructions as various \\Sigma-algebras of automata. Each construction algorithm is then presented as the unique natural homomorphism from the \\Sigmaterm algebra of regular expressions to the appropriate \\Sigma-algebra of automata. The concept of duality is introduced and used to derive more practical construction algorithms. In this way, we successfully present (and relate) algorithms given by Thompson, Berry and Sethi, McNaughton and Yamada, Glushkov, and Aho, Sethi, and Ullman. Efficient implementations (including thos...