SOME RELATIONSHIPS BETWEEN REGULAR EXPRESSIONS AND THE STRUCTURE OF SEQUENTIAL MACHINES
Abstract
It is the purpose of the report to develop techniques by which information concerning the number of states required in a sequential machine corresponding to a given regular expression may be obtained directly from that regular expression without generation of the state table description. Any such procedure, to justify its existence, must be relatively easy to use; otherwise it would be preferable to develop the state table description. Thus the report will attempt to develop tight upper bounds on the number of states in the corresponding sequential machine from an examination of the structure of a regular expression.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1970
- Accession Number
- AD0707685
Entities
People
- Alan Kent Winslow
Organizations
- University of Illinois Urbana–Champaign