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.

Giammarresi, D., Ponty, J., Wood, D., Ziadi, D. (2004). A characterization of Thompson digraphs. DISCRETE APPLIED MATHEMATICS, 134, 317-337 [10.1016/S0166-218X(03)00299-3].

### A characterization of Thompson digraphs

#### Abstract

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.
##### Scheda breve Scheda completa Scheda completa (DC)
2004
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore INF/01 - INFORMATICA
English
Dyck strings; Regular expressions; Thompson digraphs and machines
Giammarresi, D., Ponty, J., Wood, D., Ziadi, D. (2004). A characterization of Thompson digraphs. DISCRETE APPLIED MATHEMATICS, 134, 317-337 [10.1016/S0166-218X(03)00299-3].
Giammarresi, D; Ponty, J; Wood, D; Ziadi, D
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/2108/30628`
• ND
• 12
• 12