|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/715
|
| 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. |
| URI: | http://hdl.handle.net/1783.1/715 |
| Appears in Collections: | CSE TCSC Research Reports
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| 199811.pdf | | 352Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
