article

Free access

Programming Language for Automata

Authors:

Donald E. Knuth,

Richard H. BigelowAuthors Info & Claims

Journal of the ACM (JACM), Volume 14, Issue 4

Pages 615 - 635

https://doi.org/10.1145/321420.321421

Published: 01 October 1967 Publication History

PDF eReader

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.

References

[1]

GINSBURG, SEYMOUR, GREIBACg, SIELA A., AND HARRISON, MICAE A. Stack automata and compiling. J. ACM I (1967), 172-201.

Crossref

Google Scholar

[2]

CURTIS, M. W. A Turing machine simulator, J, ACM 12 (1965), 1-13

Crossref

Google Scholar

[3]

NAUR, PETER, Ed. Report on the Algorithmic Langmge ALGOL 60. Comm. ACM 3 (1960), 299-314.

Crossref

Google Scholar

[4]

KURODA, S. Y. Classes of lauguages and linear bounded automata. Inf. Coat. 7 (1964), 202-223.

Google Scholar

[5]

CAINE, STEPHEN H. Reference manual for CIT 7090/7094 experimental macro assembly program (XMAP). California Institute of "Ichnology, Pasadena, Calif. April 2,4, 1964.

Google Scholar

[6]

GOLOMB, SOLOMON W., AND BAUMERT, LEONARD :D. Backtrack Programming. J. ACM 12 (1965), 516-524.

Crossref

Google Scholar

Cited By

View all

Cook S(2023)Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersLogic, Automata, and Computational Complexity10.1145/3588287.3588298(153-172)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3588287.3588298
Jordaan STimm NMarshall L(2023)AutomaTutor: An Educational Mobile App for Teaching Automata TheoryFormal Methods: Foundations and Applications10.1007/978-3-031-49342-3_8(131-140)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-49342-3_8
Martin AMagnaudet MConversy S(2021)Vers la complétude interactive: exigences pour une machine abstraite orientée interactionAdjunct Proceedings of the 32nd Conference on l'Interaction Homme-Machine10.1145/3451148.3458644(1-6)Online publication date: 13-Apr-2021
https://dl.acm.org/doi/10.1145/3451148.3458644
Show More Cited By

Index Terms

Programming Language for Automata
1. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages

Recommendations

On stateless multihead automata: Hierarchies and the emptiness problem

We look at stateless multihead finite automata in their two-way and one-way, deterministic and nondeterministic variations. The transition of a k-head automaton depends solely on the symbols currently scanned by its k heads, and every such transition ...
Interrupt Timed Automata: verification and expressiveness

We introduce the class of Interrupt Timed Automata (ITA), a subclass of hybrid automata well suited to the description of timed multi-task systems with interruptions in a single processor environment.

While the reachability problem is undecidable for ...
Non-regular unary language and parallel communicating WatsonCrick automata systems

In 2006, Czeizler et al. introduced parallel communicating WatsonCrick automata system. They showed that parallel communicating WatsonCrick automata system can accept the non-regular unary language L={an2,wheren>1} using non-injective complementarity ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 14, Issue 4

Oct. 1967

188 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321420

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1967

Published in JACM Volume 14, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
1,271
Total Downloads

Downloads (Last 12 months)138
Downloads (Last 6 weeks)17

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cook S(2023)Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersLogic, Automata, and Computational Complexity10.1145/3588287.3588298(153-172)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3588287.3588298
Jordaan STimm NMarshall L(2023)AutomaTutor: An Educational Mobile App for Teaching Automata TheoryFormal Methods: Foundations and Applications10.1007/978-3-031-49342-3_8(131-140)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-49342-3_8
Martin AMagnaudet MConversy S(2021)Vers la complétude interactive: exigences pour une machine abstraite orientée interactionAdjunct Proceedings of the 32nd Conference on l'Interaction Homme-Machine10.1145/3451148.3458644(1-6)Online publication date: 13-Apr-2021
https://dl.acm.org/doi/10.1145/3451148.3458644
Singh TAfreen SChakraborty PRaj RYadav SJain D(2019)Automata Simulator: A mobile app to teach theory of computationComputer Applications in Engineering Education10.1002/cae.2213527:5(1064-1072)Online publication date: 9-Jul-2019
https://doi.org/10.1002/cae.22135
Chakraborty PSaxena PKatti C(2011)Fifty years of automata simulationACM Inroads10.1145/2038876.20388932:4(59-70)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1145/2038876.2038893
Chakraborty PSaxena PKatti C(2011)Automata simulators: Classic tools for computer science educationBritish Journal of Educational Technology10.1111/j.1467-8535.2011.01243.x43:1Online publication date: 21-Dec-2011
https://doi.org/10.1111/j.1467-8535.2011.01243.x
Floyd RKnuth D(1990)Addition machinesSIAM Journal on Computing10.1137/021902219:2(329-340)Online publication date: 1-Apr-1990
https://dl.acm.org/doi/10.1137/0219022
Engelfriet JSlutzki G(1984)Extended macro grammars and stack controlled machinesJournal of Computer and System Sciences10.1016/0022-0000(84)90006-029:3(366-408)Online publication date: Dec-1984
https://doi.org/10.1016/0022-0000(84)90006-0
Feldman M(1979)An Application-Oriented Programming Language for Sequential Machine StudiesIEEE Transactions on Computers10.1109/TC.1979.167541728:8(582-586)Online publication date: 1-Aug-1979
https://dl.acm.org/doi/10.1109/TC.1979.1675417
McCloskey S(1975)Abstract families of length-preserving processorsJournal of Computer and System Sciences10.1016/S0022-0000(75)80009-210:3(394-427)Online publication date: 1-Jun-1975
https://dl.acm.org/doi/10.1016/S0022-0000%2875%2980009-2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

On stateless multihead automata: Hierarchies and the emptiness problem

Interrupt Timed Automata: verification and expressiveness

Non-regular unary language and parallel communicating WatsonCrick automata systems

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Share

Share this Publication link

Share on social media

Affiliations