ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Design of Sequential Machines from Their Regular Expressions
Full text PdfPdf (695 KB)
Source Journal of the ACM (JACM) archive
Volume 8 ,  Issue 4  (October 1961) table of contents
Pages: 585 - 600  
Year of Publication: 1961
ISSN:0004-5411
Authors
Gene Ott  Litton Systems, Inc., Waltham, Mass
Neil H. Feinstein  Developmental Engineering Corporation, Cambridge, Mass
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 37,   Citation Count: 2
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/321088.321097
What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.

CITED BY  2
Janusz A. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM (JACM), v.11 n.4, p.481-494, Oct. 1964
W. A. Woods, Transition network grammars for natural language analysis, Communications of the ACM, v.13 n.10, p.591-606, Oct. 1970

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

Collaborative Colleagues:
Gene Ott: colleagues
Neil H. Feinstein: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player