Automatentheorie

Automatentheorie ist ein Teilgebiet der Theoretischen Informatik, das abstrakte Maschinen (Automaten) und formale Sprachen untersucht. Sie fragt, welche Sprachen von bestimmten Arten von Automaten erkannt oder erzeugt werden können, und wie formale Grammatiken deren Struktur beschreiben. Die Theorie verbindet Modelle der Berechnung mit der Struktur von Sprachen und liefert zentrale Ergebnisse zur Berechenbarkeit und zu Entscheidungsproblemen. In der Chomsky-Hierarchie werden Sprachenklassen wie reguläre, kontextfreie, kontext-sensitive und rekursiv aufzählbare Sprachen unterschieden; ihre Beziehungen werden durch Automatenmodelle wie endliche Automaten, Pushdown-Automaten und Turingmaschinen repräsentiert. Die Grundlagen gehen auf Arbeiten von Kleene, Chomsky, Turing und andere zurück.

Endliche Automaten umfassen deterministische (DFA) und nichtdeterministische (NFA) Varianten. Sie arbeiten mit einer endlichen Anzahl von Zuständen und akzeptieren Wörter durch einen gültigen Zustandsweg. Reguläre Sprachen lassen sich exakt durch DFA oder NFA beschreiben und durch reguläre Ausdrücke darstellen. Die Äquivalenz von DFA und NFA ist gegeben; Pumping-Lemma belegt grundlegende Eigenschaften regulärer Sprachen.

Pushdown-Automaten (PDA) erweitern endliche Automaten um einen Stack und ermöglichen die Erkennung kontextfreier Sprachen. PDAs modellieren verschachtelte Strukturen wie Klammerausdrücke. Kontextfreie Sprachen werden durch kontextfreie Grammatiken beschrieben und lassen sich mit PDAs erkennen; es besteht eine enge Verbindung zwischen Parsing-Verfahren und diesen Automaten.

Turingmaschinen bilden das allgemeinste mathematische Modell der Berechenbarkeit. Sie können jedes berechenbare Problem simulieren. Entscheidebar sind manche Probleme, andere nicht; das Halteproblem ist unentscheidbar. Die Church-Turing-These besagt, dass alle intuitive Modelle der Berechnung äquivalent sind. Rekursiv aufzählbare Sprachen umfassen alle Sprachen, die von einer Turingmaschine erkannt werden können.

Anwendungen der Automatentheorie finden sich im Compilerbau (Lexing, Parsing), in der Textverarbeitung, in der Software-Verifikation (Modellprüfung) und in der formalen Verifikation von Protokollen und Systemen.