Design of Sequential Machines from Their Regular Expressions
- 1 October 1961
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 8 (4), 585-600
- https://doi.org/10.1145/321088.321097
Abstract
Procedures are given to convert any regular expression into a state diagram description and neural net realization of a machine that recognizes the regular set of sequences described by the given expression. It is established that any regular expression with a finite number of connectives describes a regular set of sequences that can be recognized by a finite state machine. All the procedures given are guaranteed to terminate in a finite number of steps, and a generalized computer program can be written to handle the entire conversion. An incidental result of the theory is the design of multiple output sequential machines. The potential usefulness of regular expressions and a long neglected form of a state diagram are demonstrated.Keywords
This publication has 5 references indexed in Scilit:
- Regular Expressions and State Graphs for AutomataIEEE Transactions on Electronic Computers, 1960
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959
- Representation of Events in Nerve Nets and Finite AutomataPublished by Walter de Gruyter GmbH ,1956
- A method for synthesizing sequential circuitsBell System Technical Journal, 1955
- The synthesis of sequential switching circuitsJournal of the Franklin Institute, 1954