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+s2 space in the worst case. The adjacency list representation of the NFA produced by Thompson takes up between 2r and 5r space, where r is greater or equal to 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 form the states in optimal time O(|T| + |N|). McNaughton and Yamada's NFA requires Theta(|T| x |N|) 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 an DFA from our NFA representation by subset construction shows linear and quadratic speedups over subset construction starting from both Thompson's and McNaughton and Yamada's NFA's. It also shows that the DFA produced from outr NFA is as much as one order of magnitude smaller than the DFA's constructed from the two other NFA's.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 14, 1991
- Accession Number
- AD1020194
Entities
People
- Chia-hsiang Chang
- Robert Paige
Organizations
- New York University