The Second Colloquium on Automata, Languages and Programming is the successor of a similar Colloquium organized by IRIA in Paris, July 3-7, 1972. The present Colloquium which takes place at the Unl-- versity of Saarbrucken from July 29th to August 2nd, 1974, is spon- sored by the Gesellschaft fur. Informatik and organized in cooperation wlth the Special Interest Group on Automata and Computability Theory (SIGACT) and with the European Association for Theoretical Computer Science (EATCS). As its predecessor the present Colloquium is devoted to the theo- retical bases of computer science. This volume contains the text of the different lectures of the Colloquium whlch have been selected by the Program Committee out of about 130 submitted papers. About one third of the papers of this volume is concerned with formal language theory, one other third with the theory of computation and the rest with complexity theory, automata theory, programming languages, etc.

The present Lecture Notes evolved from a course given at the Technische Hogeschool Eindhoven and later at the Technische Hogeschool Twente. They are intended for computer science students; more specifically, their goal is to introduce the notions of computability and decidability, and to prepare for the study of automata theory, formal language theory and the theory of computing. Except for a general mathematical background no preliminary knowledge is presupposed, but some experience in programming may be helpful. While classical treatises on computability and decidability are oriented towards the foundation of mathematics or mathematical logic, the present notes try to relate the subject to computer science. Therefore, the expose is based on the use of strings rather than on that of natural numbers; the notations are similar to those in use in automata theory; in addition, according to a common usage in formal language theory, most of the proofs of computability are reduced to the semi-formal description of a procedure the constructivity of which is apparent to anybody having some programming experience. Notwithstanding these facts the subject is treated with mathematical rigor; a great number of informal comments are inserted in order to allow a good intuitive understanding. I am indebted to all those who drew my attention to some errors and ambiguities in a preliminary version of these Notes. I want also to thank Miss L.A. Krukerink for her diligence in typing the manuscript.

Dieses Buch behandelt Grundlagen von Programmiersprachen, deren Verknupfung mit realen Rechenmaschinen und - exemplarisch - Algorithmen. Das Ziel des Buches ist es, eine solide Basis fur das Studium der Informatik zu legen. Es ist ins besondere fur Studenten im Grundstudium des Studienganges Informatik gedacht. Ein Programm ist nur dann brauchbar, wenn es das gestellte Problem korrekt loest, und dies daruber hinaus mit der gewunschten Effizienz tut. Aussagen uber die Korrektheit und Effizienz eines Programms sind nur dann moeglich, wenn die verwendete Programmiersprache exakt definiert ist, d.h., wenn die Menge der Pro gramme (Syntax) und deren Bedeutung (Semantik) festliegen. Die Definition von Syntax und Semantik nimmt daher in diesem Buch einen wichtigen Platz ein. For male Definitionen werden erst dann lebendig, wenn sie auf einem guten intuitiven Verstandnis aufbauen, und wenn sie zu Folgerungen in der Form von Satzen fuhren. Daher enthalt dieses Buch eine grosse Anzahl von Beispielen, Satzen und Aufgaben. Die Grundlagen der Programmiersprachen werden eingefuhrt anhand einer spezifischen Programmiersprache, PROSA genannt (PROgrammiersprache SAar brucken). PROSA ist der Programmiersprache Pascal sehr ahnlich, weicht aber in einigen Punkten (z.B. dynamische Felder, geschachtelte Verbunde) aus didaktischen Grunden ab. Die Abweichungen dienen zum einen der Vereinfachung, und zum an deren der lllustration einiger Konzepte, die Pascal nicht kennt. Die Benutzung von Pascal in einem begleitenden Programmierpraktikum stellt aber keinerlei Problem dar.

Die Algorithmentheorie ist Ende der dreiBiger Jahre entstanden in Ver- bindung mit Problemen der mathematischen Logik. Hit dem Aufkommen einer wissenschaftlich fundierten Informatik hat sie, insbesondere in den letzten zwanzig Jahren, an Bedeutung und Tragweite gewonnen. Das wird begreiflich, wenn man bedenkt, daB ein Programm flir eine elektronische Rechenanlage im wesentlichen ein Algorithmus ist und daB Resultate der Algorithmentheorie deshalb auch auf Programme anwendbar sind. Insbeson- dere gibt es eine enge Verbindung zwischen der Algorithmentheorie und anderen flir die Informatik bedeutsamen Zweigen, wie der Automatentheorie, der Theorie der formalen Sprachen und der sich in den letzten Jahren heranbildenden Theorie der Programmierung. Wahrend die meisten Blicher liber Algorithmentheorie sich an Studenten der mathematischen Logik richten, ist dieses Buch flir Informatikstuden- ten bestimmt. Zwar wird das Thema mit mathematischer Scharfe behandelt, aber es werden keine besonderen mathematischen Kenntnisse vorausgesetzt und die zahlreichen Kommentare zielen daraufhin, ein gutes intuitives Verstandnis zu ermoglichen; auBerdem hebt das Buch regelmaBig die Be- deutung der Resultate flir die Informatik hervor. SchlieBlich sind die Notationen und bestimmte Beweismethoden der Automatentheorie und der Theorie der formalen Sprachen entnommen; insbesondere wird grundsatz- lich mit Worten statt mit natlirlichen Zahlen gearbeitet.