HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/74
Title: Instruction computation in subset construction
Authors: Johnson, J. Howard
Wood, Derick
Issue Date: Jun-1996
Series/Report no.: Computer Science Technical Report ; HKUST-CS96-21
Abstract: Subset construction is THE method of converting a nondeterministic finite-state machine into a deterministic one. The process of determinization is an important one in any implementation of finite-state machines since nondeterministic machines are often easier to describe than their deterministic equivalents and the conversion of regular expressions to finite-state machines usually produces nondeterministic machines. We discuss one aspect of subset construction; namely, the computation of the instructions of the equivalent deterministic machine. Although the discussion is to some extent independent of any specific assumptions, we draw some conclusions within the context of INR and Grail, both packages for the manipulation of finite-state machines. The aim of the discussion is to present the problem and suggest some possible solutions; we do not intend to and cannot be definitive since much remains unknown.
URI: http://hdl.handle.net/1783.1/74
Appears in Collections:CSE Technical Reports

Files in This Item:

File Description SizeFormat
tr9621.pdf194KbAdobe PDFView/Open

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