HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >

Please use this identifier to cite or link to this item:
Title: Gluskov and Thompson constructions : a synthesis
Authors: Giammarresi, Dora
Ponty, Jean-Luc
Wood, Derick
Keywords: SGML
Thompson machine
Glushkov machine
Issue Date: 7-Oct-1998
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-1998-11
Abstract: 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.
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
199811.pdf352KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.