Das Buch bietet einen Einstieg in die theoretischen Grundlagen der Informatik. Es beschränkt sich auf die klassischen Themen: formale Sprachen, endliche Automaten und Grammatiken, Turing-Maschinen, Berechenbarkeit und Entscheidbarkeit, Komplexität. Das Konzept der Transformation zwischen den verschiedenen Formalismen zieht sich wie ein roter Faden durch das gesamte Buch.

Auf eine anschauliche Vermittlung der Begriffe und Methoden der theoretischen Informatik und ihre Vertiefung in Aufgaben und Programmierprojekten wird großer Wert gelegt. Auf der zu dem Buch gehörenden Website findet sich das Lernprogramm"Machines", mit dem endliche Automaten, Kellerautomaten, Grammatiken, reguläre Ausdrücke und Turing-Maschinen mit einer komfortablen grafischen Oberfläche realisiert und visualisiert werden können.

Der Autor

Prof. Dr. Rolf Socher ist Professor an der Fachhochschule Brandenburg. Er lehrt in den Gebieten Mathematik, Theoretische Informatik und Computergrafik. Er ist Autor mehrerer Bücher.

2 Endliche Automaten (S. 15-16)

2.1 Einführung

Viele Dinge des täglichen Lebens lassen sich als Automaten auffassen, die verschiedene Zustände einnehmen können. Betrachten wir etwa eine U-Bahn-Eintrittskontrolle mit drei stählernen Armen. Dieses Gerät befindet sich stets in einem der zwei Zustände„verriegelt" und„entriegelt". Im verriegelten Zustand lassen sich die Arme nicht drehen. Wirft man nun einen Chip ein, so gibt ein Mechanismus die Arme frei. Die Eingabe eines Chips bewirkt also denÜbergang vom verriegelten in den entriegelten Zustand. Durch Drehung der Arme geht das Gerät in den verriegelten Zustand zurück. Die beiden möglichen Aktionen sind das Einwerfen eines Chips und das Drehen der Arme.

Das Verhalten des Gerätes hängt offenbar sowohl von der Aktion (Chip einwerfen oder Arme drehen) als auch von seinem jeweiligen Zustand ab. Abbildung 2.1 zeigt die möglichen Zustandsübergänge: Im verriegelten Zustand bewirkt das Drehen der Arme nichts, während das Einwerfen eines Chips die Sperre entriegelt. Werden im entriegelten Zustand die Arme gedreht, so geht das Gerät in den verriegelten Zustandüber. Im entriegelten Zustand ist das Einwerfen eines weiteren Chips dagegen sinnlos, die Sperre bleibt entriegelt. Man bezeichnet ein solches Gerät, das in Abhängigkeit vom aktuellen Zustand und von der jeweiligen Aktion bzw. Eingabe in einen anderen Zustandübergeht, als Automaten. Aus dem Alltag sind Getränkeoder Zigarettenautomaten bestens bekannt, also Geräte, die bei Einwurf eines bestimmten Betrags eine Ware ausgeben.

In der Informatik werden Automaten hauptsächlich verwendet, um Zeichenfolgen auf ihre Plausibilität zu prüfen. Der in Abbildung 2.2 gezeigte Automat A P kann zur Paritätsprüfung verwendet werden. Die Eingabe besteht aus einer Reihe von Binärziffern. Der Automat prüft, ob diese eine gerade oder ungerade Anzahl von Einsen enthält. Der Ablauf beginnt im Zustand„gerade", weil am Anfang noch keine Einsen gelesen wurden und 0 eine gerade Zahl ist. Dies wird durch den Pfeil mit der Beschriftung„start" angedeutet. Liest der Automat eine Null, so bleibt er im jeweiligen Zustand („gerade" bzw.„ungerade"), liest er eine Eins, so wechselt er von„gerade" nach„ungerade" bzw. von„ungerade" nach„gerade".

Hat der Automat das Eingabewort vollständig gelesen, so zeigt der Zustand, in dem er sich dann befindet, ob das Eingabewort gerade oder ungerade Parität hat. Im Allgemeinen prüft man mit Hilfe eines Automaten, ob die Eingabe einer bestimmten Bedingung genügt (beispielsweise die Bedingung gerader Parität). Zu diesem Zweck führt man so genannte akzeptierende Zustände ein (auch Endezustände genannt), in unserem Beispiel den Zustand„gerade". In der graphischen Darstellung werden akzeptierende Zustände mit doppelt umrandeten Knoten gekennzeichnet. Befindet sich der Automat nach der Verarbeitung der Eingabe in einem akzeptierenden Zustand, so bedeutet dies, dass die Eingabe akzeptiert wird.

In den beiden genannten Beispielen kann die Eingabe als ein Wort, also als Folge von Zeichen aufgefasst werden. Im folgenden Abschnitt sollen zunächst die daraus resultierenden Grundbegriffe wie Zeichen, Wörter und Sprachen definiert werden.