Die Automatentheorie ist ein wichtiges Themengebiet der theoretischen Informatik; ihre Erkenntnisse zu abstrakten Rechengeräten – Automaten genannt – finden Anwendung in der Berechenbarkeits und der Komplexitätstheorie, aber auch in der praktischen Informatik (z.B. Compilerbau, Suchmaschinen, Protokollspezifikation, Software Engineering).
Automaten
Ausgangspunkt der Automatentheorie waren Überlegungen von Turing in den 30er Jahren zu der theoretischen Leistung einer Rechenmaschine. Er untersuchte dazu bestimmte abstrakte Rechengeräte, die sog. Turing-Maschinen; da diese Maschinen die Fähigkeiten der heutigen Computersysteme besitzen, gelten die Ergebnisse seiner Überlegungen auch für diese Systeme.
Weitere Wissenschaftler entwickelten und untersuchten andere Arten von Automaten, u.a. endliche Automaten, Moore-Automaten, Mealy-Automaten, nichtdeterministische endliche Automaten, Pushdown/Kellerautomaten.
Automaten verarbeiten eingegebene Zeichenketten/Wörter; verschiedene Automaten wie die Moore-Automaten und die Mealy-Automaten können auch Zeichen ausgeben. Der Ansatz der Automaten kann am Beispiel der endlichen (deterministischen) Automaten veranschaulicht werden; er besteht aus:
-
einer endlichen Menge von Eingabesymbolen/-zeichen,
-
einer endlichen Menge von Zuständen,
-
einer Menge von Endzuständen als Teilmenge der Zustandsmenge,
-
einer Zustandsüberführungsfunktion, die zu einem Argument bestehend aus Zustand und Eingabesymbol einen (neuen) Zustand als Ergebnis zurückgibt, und
-
einem Startzustand als Element der Menge der Zustände.
Die von dem Automaten erkannte Sprache umfasst alle Wörter/Zeichenketten, die als Eingabe den Automaten vom Startzustand durch sukzessive Anwendung der Überführungsfunktion auf den jeweils aktuellen Zustand und das nächste zu verarbeitende Zeichen nach der Verarbeitung des letzten Zeichens in einen Endzustand überführt. Beispielsweise kann mit einem solchen Automaten die Arbeitsweise eines Geldautomaten beschrieben werden: Durch Eingabe des Symbols „Auszahlung“ gelangt der Automat in den Zustand PIN-Eingabe, über die Zustände Erste PIN-Ziffer bis Vierte PIN-Ziffer in den Zustand PIN-Eingabe Erfolgt (jeweils durch Verarbeitung des Eingabesymbols Ziffer; wird ein anderes Symbol gelesen, wechselt der Automat in den Zustand Falsches PIN-Symbol) etc.
Grammatiken
Chomsky entwickelte eine Hierarchie formaler Grammatiken, die sog. Chomsky-Hierarchie. Grammatiken sind zwar eigentlich keine Maschinen, besitzen aber eine enge Verwandtschaft zu Automaten, indem über eine Grammatik eine Sprache definiert/erzeugt wird, und ein geeigneter Automat für Wörter feststellen kann, ob sie zu der Sprache gehören. Beispielsweise erkennen endliche Automaten reguläre Sprachen, Kellerautomaten kontextfreie Sprachen. Aus der Tatsache, dass formale Sprachen auch als „Probleme“ aufgefasst werden können, indem den Wörtern einer Sprache eine Semantik zugeordnet wird (z.B. Zahlen, logische Ausdrücke oder Graphen), ergibt sich der Zusammenhang zur Berechenbarkeit.
Bei den Sprachen, die durch Grammatiken definiert werden, handelt es sich insbesondere um die Programmiersprachen.
Eine Grammatik umfasst
-
ein Ausgangssymbol,
-
eine endliche Menge von Variablen, die nicht in den abgeleiteten Wörtern der Sprache enthalten sein dürfen,
-
ein Alphabet, d.h. eine Menge von Terminals als Symbole der Wörter der Sprache,
-
eine Menge von Ableitungsregeln, über die jeweils eine bestimmte Kombination aus Terminals und Variablen (in einer bestimmten Reihenfolge) in eine andere Kombination aus Terminals und Variablen umgeformt wird, in der die Variablen der Ausgangskombination jeweils durch eine Folge bestehend aus Variablen und Terminals ersetzt werden, und
-
einem Startsymbol als Element der Menge der Variablen.
Die erzeugte Sprache der Grammatik sind alle Wörter aus Terminals, die sich über die Ableitungsregeln aus dem Startsymbol erzeugen lassen. Die Klassen von Grammatiken entscheiden sich dahingehend, wie die Regeln beschaffen sind: Beim Typ 0 („rekursiv aufzählbar“) muss die linke Seite der Produktionsregeln mindestens eine Variable enthalten, beim Typ 1 („kontextsensitiv“) muss zusätzlich die rechte Seite der Regel genauso viele Elemente enthalten, wie die linke Seite; beim Typ 2 („kontextfrei“) ist die linke Seite der Produktion genau eine Variable („ohne Kontext“), beim Typ 3 („regulär“) schließlich muss zusätzlich die rechte Seite der Produktion ein Terminal, das leere Zeichen oder ein Terminal gefolgt von einer Variablen sein. Die Beschreibungsmächtigkeit nimmt in der Hierarchie vom Typ 0 bis zum Typ 3 sukzessiv ab.
Die wichtigste der durch Grammatiken bzw. Automaten darstellbaren Sprachklassen bilden die kontextfreien Sprachen; auch Programmiersprachen ordnen sich in diese Klasse ein. Backus und Naur entwickelten eine Notation zur kompakten Präsentation der Ableitungsregeln dieser Grammatiken und damit von Programmiersprachen, die sog. Backus-Naur-Form (BNF).
Literatur
Hollas, Boris: Grundkurs Theoretische Informatik mit Aufgaben und Prüfungsfragen. Heidelberg, Berlin : Spektrum Akademischer Verlag, 2007.
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey, D.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. Auflage. München : Pearson Studium, 2002.
Schöning, Uwe: Theoretische Informatik – kurzgefasst. Heidelberg, Berlin : Spektrum Akademischer Verlag, 2001.
