Design of Sequential Machines from Their Regular Expressions

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.

REFERENCES

• 1: KLEENE, S C Reahzation of events in nerve nets and finite automata. In Automata Studies, C E. Shannon and J. McCarthy, Eds., Princeton University Press, 1956, pp. 3-41
• 2: HARING, D. R The sequential transmission expression for flow graphs. M. I. T. Electronic Systems Laboratory, Technical Memorandum No. 7848-TM-3, Nov. 1960.
• 3: McNAUGHTON, R. F., AND YAMADA, H. Regular expressions and state graphs for automata. IRE Trans. EIectromc Comp. EC-9 (Mar. 1960) 39-47.
• 4: RABIN, M. O., AND SCOTT, D. Finite automata and their decismn problems. IBM J. Res. Dev. 3 (Apr. 1959), 114-125.
• 5: MINSKY, M.L. Notes for M72. M. I. T., Spring Term 1959.
• 6: MEALY, G. H. A method of synthesizing sequential circuits. Bell System Tech. J. 84 (Sept. 1955), 1045-1079.
• 7: HUFFMAN, D. A. The synthesis of sequential switching Networks. J. Frankhn Inst. (Apr. 1954), 161-190, 275-303.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Connectionism and neural nets

General Terms:
Design, Theory, Verification