Please use this identifier to cite or link to this item:

Gluskov and Thompson constructions : a synthesis

Authors Giammarresi, Dora
Ponty, Jean-Luc
Wood, Derick
Issue Date 1998-10-07
Summary We reexamine the relationship between the two most popular methods for transforming a regular expression into a finite-state machine: the Glushkov and Thompson constructions. These methods have received more attention recently because of the Standard Generalized Markup Language (SGML) and a revival of interest in symbolic toolkits for regular and context-free expressions, grammars, and machines. We establish that: - Every Thompson machine is, in a sense we make precise, a Glushkov machine - Every Glushkov machine is hidden in the corresponding Thompson machine In addition, we establish that a number of other inductive constructions yield machines that have their corresponding Glushkov machine hidden in them.
Language English
Format Technical report
Files in this item:
File Description Size Format
199811.pdf 360558 B Adobe PDF