Zusammenfassung
Es wird ein Automat mit Speicherband eingeführt und in seiner Eigenschaft als erkennender Automat untersucht. Er kann sein Arbeitsband nur als Puffer benutzen, d. h. was zuerst eingelesen wird, wird auch zuerst wieder ausgelesen. Es werden verschiedene Modifikationen des Grundmodells, insbesondere aber die deterministische, in Realzeit arbeitende Version betrachtet, sowohl hinsichtlich der Lage der durch den Automatentyp definierten Sprachklasse in derChomsky-Hierarchie, als auch das Verhalten dieser Sprachen gegenüber gewissen Operationen. Einige Resultate über Entscheidbarkeitsfragen werden zitiert.
Summary
A class of automata with tape has been defined and considered as recognition devices. Our automaton can use its working tape only as a buffer, i. e. in a “first-in-first-out” manner. Some modifications of the general model are considered, especially the deterministic, real-time version. The position in theChomsky hierarchy of the class of languages accepted by such automata and some operations with these languages have been investigated. Some results on decidability questions are cited.
Article PDF
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Literatur
Davis, M.: Computability and Unsolvability. New York-London: McGraw-Hill. 1958.
Vollmar, R.: Über einen Automaten mit Speicherband (Pufferautomat). Arbeitsberichte des Instituts für Mathematische Maschinen und Datenverarbeitung der Universität Erlangen-Nürnberg2, 1, (1969).
Ginsburg, S.: The Mathematical Theory of Context-Free Languages. New York-London: McGraw-Hill. 1966.
Shepherdson, J. C., andH. E. Sturgis: Computability of Recursive Functions. J. ACM10, 217–255 (1963).
Hermes, H.: Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit. Berlin-Göttingen-Heidelberg: Springer-Verlag. 1961.
Aho, A. V., andJ. D. Ullman: The Theory of Languages. Mathematical Systems Theory2, 97–125 (1968).
Chomsky, N.: On Certain Formal Properties of Grammars. Information and Control2, 137–167 (1959).
Händler, W.: Automatentheorie II (Vorlesungsausarbeitung). Hannover. 1966.
Ginsburg, S., andG. F. Rose: Preservation of Languages by Transducers. Information and Control9, 153–176 (1966).
Rabin, M. O.: Real Time Computation. Israel Journal of Math.1, 203–211 (1963).
Post, E. L.: A Variant of a Recursively Unsolvable Problem. Bull. Am. Math. Soc.52, 264–268 (1946).
Landweber, P. S.: Decision Problems of Phrase-Structure Grammars. IEEE Trans. on Electronic ComputersEC-13, 354–362 (1964).
Rabin, M. O., andD. Scott: Finite Automata and Their Decision Problems. IBM J. Res. Dev.3, 114–125 (1959).
Author information
Authors and Affiliations
Additional information
Mit 2 Abbildungen
Diese Arbeit wurde von der Deutschen Forschungsgemeinschaft (Az.:Ha 417/7) gefördert.
Rights and permissions
About this article
Cite this article
Vollmar, R. Über einen Automaten mit Pufferspeicherung. Computing 5, 57–70 (1970). https://doi.org/10.1007/BF02234250
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02234250