Accession Number : AD0707685

Title :   SOME RELATIONSHIPS BETWEEN REGULAR EXPRESSIONS AND THE STRUCTURE OF SEQUENTIAL MACHINES

Corporate Author : ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

Personal Author(s) : Winslow,Alan Kent

Report Date : MAY 1970

Pagination or Media Count : 52

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.

Descriptors :   (*DIGITAL COMPUTERS, MATHEMATICAL MODELS), AUTOMATA, ALGEBRA, MATHEMATICAL LOGIC

Subject Categories : Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE