Automat (Informatik)

Grundidee und Bedeutung

Ein Automat, auch abstrakte Maschine genannt, ist ein Modell eines digitalen, zeitdiskreten Rechners. Dabei ist zunächst unerheblich, ob sich die Maschine tatsächlich bauen lässt. Durch die vereinfachten Fähigkeiten kann man ihr Verhalten leichter beschreiben, untersuchen und mit dem anderer Automaten vergleichen.

Automaten bilden in der theoretischen Informatik eine Grundlage für Berechenbarkeits- und Komplexitätstheorie. In der praktischen Informatik werden sie unter anderem im Compilerbau eingesetzt. In der Digitaltechnik dienen sie zur Steuerung digitaler und hybrider Systeme, etwa in Rechnerarchitekturen, Rechnernetzen und reaktiven Systemen.

Zustände und Übergänge

Ein Automat erhält von außen eine Eingabe in Form einer Folge von Zeichen und befindet sich jeweils in einem bestimmten Zustand. Trifft ein Eingabezeichen ein, kann sich aus diesem Zeichen und dem gegenwärtigen Zustand ein neuer Zustand ergeben. Dieser heißt Folgezustand; der Wechsel wird Zustandsübergang oder Transition genannt.

Die Menge aller möglichen Zustandsübergänge legt das Verhalten des Automaten fest und kann als sein Programm verstanden werden.

Determinismus, Akzeptanz und Ausgabe

Bei einem deterministischen Automaten ist für jedes Paar aus gegenwärtigem Zustand und Eingabezeichen genau ein Folgezustand festgelegt. Bei einem nichtdeterministischen Automaten können dagegen mehrere Folgezustände möglich sein, aus denen der Automat willkürlich einen auswählt. Nichtdeterminismus eignet sich, um eine nicht vollständig bekannte Umgebung zu modellieren („don’t know“) oder verschiedene mögliche Implementierungen offenzulassen („don’t care“). Häufig sind zusätzlich ε-Übergänge erlaubt: spontane Zustandsübergänge, die ohne Eingabezeichen stattfinden.

Automaten, die lediglich Zustandsübergänge ausführen, heißen Transitionssysteme. Ein Akzeptor besitzt darüber hinaus einen ausgezeichneten Startzustand und eine Teilmenge von Endzuständen. Führt ein Eingabewort vom Startzustand in einen Endzustand, akzeptiert der Automat dieses Wort. Die Menge aller akzeptierten endlichen Wörter bildet eine formale Sprache.

Automaten mit Ausgabe heißen Transduktoren. Beim Moore-Automaten ist jedem Zustand ein Ausgabezeichen zugeordnet. Beim Mealy-Automaten hängt das Ausgabezeichen von einem Paar aus Zustand und Eingabezeichen ab. Solche Automaten bilden Verarbeitungseinheiten.

Wichtige Automatenklassen

Automaten werden nach den verfügbaren Mitteln in Klassen oder Automatenmodelle eingeteilt. Zu jeder Klasse von Akzeptoren gehört eine Klasse formaler Sprachen. Die Beziehungen entsprechen der Chomsky-Hierarchie:

• Turingmaschinen (DTM/NTM) besitzen neben ihrem inneren Zustand ein unendliches Band mit einem beweglichen Schreib-/Lesekopf. Deterministische und nichtdeterministische Turingmaschinen akzeptieren die Typ-0-Sprachen, also die rekursiv aufzählbaren Sprachen: RE = NTM = DTM. Die Turingmaschine definiert außerdem den Begriff der Berechenbarkeit; hierzu gehört die Churchsche These.

• Linear beschränkte Automaten (DLBA/LBA) unterscheiden sich von Turingmaschinen dadurch, dass der zugängliche Bandabschnitt durch die Größe der Eingabe beschränkt ist. Nichtdeterministische LBA akzeptieren genau die Typ-1-Sprachen, also die kontextsensitiven Sprachen: CS = LBA ⊇ DLBA. Ob LBA ⊃ DLBA tatsächlich eine echte Inklusion ist oder beide Varianten dieselbe Sprachklasse akzeptieren, ist ein offenes Problem.

• Kellerautomaten (DPDA/PDA) besitzen endlich viele innere Zustände und zusätzlich einen Keller. Dieser Keller ist ein Stapel, auf dem Zeichen zur späteren Verarbeitung zwischengespeichert werden. Nichtdeterministische PDA akzeptieren die Typ-2-Sprachen, also die kontextfreien Sprachen: CF = PDA ⊋ DPDA. Deterministische DPDA akzeptieren die deterministisch kontextfreien Sprachen.

• Endliche Automaten (DFA/NFA) haben nur endlich viele Zustände. Deterministische und nichtdeterministische Varianten akzeptieren genau die Typ-3-Sprachen, also die regulären Sprachen: REG = NFA = DFA.

Ein Zweikellerautomat verfügt über zwei Keller. Mit diesem Kellerpaar lässt sich ein Turingband simulieren, sodass Zweikellerautomaten und Turingmaschinen gleichwertig sind. Syntaktische Beschränkungen dieses Modells charakterisieren Typ-1- und Typ-2-Sprachen.

Eine Registermaschine besitzt zusätzlich zum inneren Zustand eine Folge von Registern. Register sind Speicherzellen für natürliche Zahlen, auf denen elementare Rechenoperationen ausgeführt werden können. Registermaschinen sind ebenso mächtig wie Turingmaschinen.

Erweiterungen und Abgrenzungen

Nichtdeterministische Automaten sind von stochastischen Automaten zu unterscheiden. Stochastische Automaten ordnen ihren Zustandsübergängen Wahrscheinlichkeiten zu; nichtdeterministische Automaten beschreiben dagegen lediglich mögliche Übergänge. Deshalb eignen sich nichtdeterministische Automaten nicht für Wahrscheinlichkeitsaussagen.

Neben Modellen, die eine Eingabe nacheinander einlesen, gibt es weitere Automatentypen. Dazu gehören Turingmaschinen mit zweidimensionalem Band oder mehreren Bändern, zelluläre Automaten, ω-Automaten für unendliche Eingaben, neuronale Netze, Petri-Netze und algebraische Rechenmodelle.

Praktische Anwendungen

Für die Programmierung sind insbesondere endliche Automaten und Kellerautomaten wichtig, weil sich mit ihrer einfachen Struktur auch viele komplexe Probleme übersichtlich lösen lassen. Im Compilerbau werden sie beispielsweise zur Implementierung von Parsern verwendet. Ein Parser untersucht Eingaben nach vorgegebenen formalen Strukturen.

Implementierungen von Netzwerkprotokollen verwenden häufig einen endlichen Automaten, um ihren aktuellen Zustand darzustellen. Auch die möglichen Navigationsschritte in einem Wizard und Arbeitsabläufe im Workflow-Management lassen sich als endliche Automaten modellieren.

Bei der Umsetzung sequenzieller Hardware wird ebenfalls das Modell des endlichen Automaten eingesetzt. In diesem Bereich wird es meist als Finite State Machine (FSM) bezeichnet.