Published October 1967
| public
Journal Article
Programming Language for Automata
- Creators
- Knuth, Donald E.
- Bigelow, Richard H.
Abstract
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.
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.Additional details
- Eprint ID
- 72126
- DOI
- 10.1145/321420.321421
- Resolver ID
- CaltechAUTHORS:20161117-130320052
- NSF
- Carnegie Corporation
- Created
-
2016-11-17Created from EPrint's datestamp field
- Updated
-
2021-11-11Created from EPrint's last_modified field