Some Relationships Between Regular Expressions and the Structure of Sequential Machines

摘要

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.