Regular Expressions and Subset-Specified Sequential Machines.
Abstract
The relationship between regular expressions and subset-specified sequential machines is derived through the use of a specialized machine, the subset-specified tape acceptor. This machine is described by two regular expressions, one of which represents the set of sequences which is an upper bound to the set accepted by the machine, and the other, the lower bound. An inverse procedure is presented which starts with two regular expressions, one which represents a set of sequences that must be accepted, and another which represents a set that may or may not be. From these, a subset-specified sequential machine is derived which can be reduced by the method of Purnhagen to a completely specified machine which accepts the required set of sequences. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1972
- Accession Number
- AD0742435
Entities
People
- Edward Stephen Hinton
Organizations
- Air Force Institute of Technology