Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

1. Mathematische Grundlagen

Zusammenfassung
In diesem Kapitel wird der mathematische Apparat, der in den folgenden Kapiteln benötigt wird, kurz zusammengestellt. Die Darstellung ist weniger zum Erlernen als vielmehr zum Nachschlagen geeignet.
Peter Sander, Wolffried Stucky, Rudolf Herschel

2. Automaten

Zusammenfassung
Automaten umgeben uns im täglichen Leben überall, und jedermann hat eine mehr oder weniger präzise Vorstellung davon, was ein Automat ist. Irgendwie sind damit Begriffe wie „definierter Ablauf von Handlungen“, „selbsttätige Aneinanderreihung von Aktionen“, „determinierte Folge von Zuständen“ oder dergleichen verbunden. Die Beispiele für Automaten sind ungeheuer mannigfaltig, sie reichen vom Zigaretten-, Fahrkarten-, Getränke- und Geldwechselautomaten über den Münz- und Kartenfernsprecher bis zu Computern, den Rechenautomaten. Die Kompliziertheit der aufgeführten Beispiele ist sehr verschiedenartig. Es soll die Aufgabe des folgenden einführenden Abschnitts sein, die prinzipiellen Gemeinsamkeiten herauszuarbeiten. Dabei geht es insbesondere um die Frage, wie man die Arbeitsweise, das Verhalten eines Automaten losgelöst von seinen Bauelementen und seiner physikalischen Realisierung darstellen kann. Die sich dabei ergebenden Prinzipien und Begriffe bilden dann die Grundlage für eine mathematische Beschreibung in den folgenden Abschnitten.
Peter Sander, Wolffried Stucky, Rudolf Herschel

3. Formale Sprachen

Zusammenfassung
Im letzten Kapitel haben wir die Sprachen von endlichen Automaten und von Kellerautomaten kennengelernt. Dies sind im wesentlichen Wortmengen über einem festen Alphabet gewesen. Eine Wortmenge ist als Sprache eines gegebenen Automaten bezeichnet worden, falls der Automat genau die Worte dieser Menge akzeptieren konnte. Diese Definition für den Begriff „Sprache“ erscheint auf den ersten Blick etwas künstlich und technisch, da wir gewohnt sind, eher natürliche Sprachen — wie etwa Deutsch, Englisch, Russisch etc. — als Sprachen anzusehen. Allenfalls noch Personen, die im Umgang mit Computern geschult sind, kämen auf die Idee, künstliche Sprachen — z.B. Programmier- und Datenbanksprachen — unter diesen Oberbegriff einzuordnen.
Peter Sander, Wolffried Stucky, Rudolf Herschel

4. Turing-Maschinen, Algorithmen und berechenbare Funktionen

Zusammenfassung
Es hat sich im 2. Kapitel herausgestellt, daß die Leistungsfähigkeit von endlichen Automaten und von Kellerautomaten beschränkt ist, denn wir können jeweils Sprachen angeben, die durch diese Automatentypen nicht charakterisierbar sind. Wir werden in diesem Kapitel mit der Turing-Maschine einen Automatentyp kennenlernen, dessen Leistungsfähigkeit viel weiter reicht, d. h. es ist damit eine größere Menge von Sprachen akzeptierbar als beispielsweise mit Kellerautomaten.
Peter Sander, Wolffried Stucky, Rudolf Herschel

Backmatter

Weitere Informationen