A Caltech Library Service

Programming Language for Automata

Knuth, Donald E. and Bigelow, Richard H. (1967) Programming Language for Automata. Journal of the ACM, 14 (4). pp. 615-635. ISSN 0004-5411.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The techniques of automatic programming are useful for constructive proofs in automata theory. A formal definition of an elementary programming language for a stack automaton is given, and it is shown how this may be readily adapted to other classes of automata. The second part of this paper shows how this programming language can be applied to automata theory, as we prove there are non-context-sensitive languages accepted by a stack automaton.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1967 ACM. Received February, 1967. The research reported in this paper was supported in part by the National Science Foundation and the Carnegie Corporation.
Funding AgencyGrant Number
Carnegie CorporationUNSPECIFIED
Issue or Number:4
Record Number:CaltechAUTHORS:20161117-130320052
Persistent URL:
Official Citation:Donald E. Knuth and Richard H. Bigelow. 1967. Programming Language for Automata. J. ACM 14, 4 (October 1967), 615-635. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72126
Deposited By: Kristin Buxton
Deposited On:17 Nov 2016 21:25
Last Modified:03 Oct 2019 16:14

Repository Staff Only: item control page