New Theoretical and Computational Results for Regular Languages
Abstract
We show how to turn a regular expression into an O(s) space representation of McNaughton and Yamada's NFA, where s is the number of NFA states. The standard adjacency list representation of McNaughton and Yamada's NFA takes up s+s 2 space in the worst case. The adjacency list representation of the NFA produced by Thompson takes up between 2r and 5r space, where r s in general, and can be arbitrarily larger than s. Given any set T of NFA states, our representation can be used to compute the set N of states one transition away from the states in T in optimal time O(jT j + jN j). McNaughton and Yamada's NFA requires \Theta(jT j \Theta jN j) in the worst case. Using Thompson's NFA, the equivalent calculation requires \Theta(r) time in the worst case. An implementation of our NFA representation confirms that it takes up an order of magnitude less space than McNaughton and Yamada's machine. An implementation to produce a DFA from our NFA representation by subset construction sho...
Recommended Citation
C. Chang and R. Paige, "New Theoretical and Computational Results for Regular Languages," Lecture Notes in Computer Science, New York University, May 1991.
Meeting Name
3rd Annual Symposium on Combinatorial Pattern Matching (1992: Apr. 29-May 1, Tucson, AZ)
Department(s)
Mathematics and Statistics
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 1991 New York University, All rights reserved.
Publication Date
01 May 1991
