A characterization of Thompson digraphs

A finite-state machine is called a Thompson machine if it can be constructed from an empty-free regular expression using the construction of Thompson as modified by Hopcroft and Ullman. We call the underlying digraph of a Thompson machine a Thompson digraph. We characterize Thompson digraphs and we give an algorithm that generates an equivalent regular expression from a Thompson machine that has size linear in the total number of states and transitions. Although the algorithm is simple, it is novel in that the usual constructions of equivalent regular expressions from finite-state machines produce regular expressions that have size exponential in the size of the given machine, in the worst case. The algorithm provides a tentative first step in the construction of small expressions from finite-state machines. © 2003 Elsevier B.V. All rights reserved.