A characterization of Thompson digraphs

✍ Scribed by Dora Giammarresi; Jean-Luc Ponty; Derick Wood; Djelloul Ziadi

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 398 KB
• Volume: 134
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00299-3

✦ Synopsis

A ÿnite-state machine is called a Thompson machine if it can be constructed from an emptyfree regular expression using the construction of Thompson as modiÿed 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 ÿnite-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 ÿrst step in the construction of small expressions from ÿnite-state machines.