Automat (Informatik)

]] Ein Automat ist in der Informatik eine gedachte Maschine (also ein abstraktes Modell einer Maschine), die sich gemäß bestimmter Regeln (nach einem Programm) verhält. Automaten dienen in der Theoretischen Informatik als Konstrukt, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen. Dabei werden die Automaten auf ihre grundlegenden Eigenschaften reduziert. – Ob es tatsächlich möglich oder sinnvoll wäre, eine solche Maschine zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der Fähigkeiten erlaubt es, das Verhalten eines Automaten leichter zu verstehen und zu vergleichen. Die Übertragung dieser Ergebnisse ist grundlegend für verschiedene Bereiche der Praktischen Informatik. Ein Beispiel dafür ist der Compilerbau.

Die Automaten sind meist ähnlich aufgebaut: Der Automat hat einen inneren Zustand und bekommt eine Eingabe, die (meistens) Zeichen für Zeichen gelesen wird. Eine Zustandsübergangstabelle definiert, abhängig vom aktuellen Zustand und dem gerade gelesenen Zeichen, den nächsten Zustand.

Automaten werden unter anderem in deterministische und nichtdeterministische unterschieden. Dabei ist bei nichtdeterministischen Automaten nicht eindeutig vorherbestimmt, welcher Zustand auf welchen anderen folgt.

Bekannte Typen von Automaten sind (jeweils mit Abkürzungen in deterministischer und nichtdeterministischer Variante):

• Turingmaschinen (DTM/NTM): akzeptieren die Typ-0-Sprachen (Rekursiv aufzählbare Sprache) und damit auch Typ-1-Sprachen. Durch die Turingmaschine wird außerdem der Begriff der Berechenbarkeit definiert. Siehe Churchsche These.
• linear beschränkte Automaten (DLBA/LBA): akzeptieren die Typ-1-Sprachen (kontextsensitive Sprachen)
• Kellerautomaten (DPDA/PDA): akzeptieren die Typ-2-Sprachen (Kontextfreie Sprachen)
• Endliche Automaten (DFA/NFA): akzeptieren die Typ-3-Sprachen (Reguläre Sprachen)
• Zweikellerautomat: ohne Einschränkung der Turingmaschine gleichwertig. Syntaktische Beschränkungen dieses Modells führen zur Charakterisierung der Typ-1- und Typ-2-Sprachen.
• Registermaschinen: sind genau so mächtig wie Turingmaschinen, bieten aber in einigen Fällen ein besseres Maß für die Zeitkomplexität.

Die Menge der Automaten stehen wie folgt mit den Mengen der Sprachklassen und Grammatiken in Beziehung (siehe auch Chomsky-Hierarchie):

Chomsky-Hierarchie	Sprachklasse		nicht deterministischer Automat		deterministischer Automat
Typ-0-Grammatik	$\{\backslash color\{blue\}\backslash mathcal\{RE\}\}$	$=$	$\{\backslash color\{blue\}\backslash mathcal\{NTM\}\}$	$=$	$\{\backslash color\{blue\}\backslash mathcal\{DTM\}\}$
Typ-1-Grammatik	$\{\backslash color\{blue\}\backslash mathcal\{CS\}\}$	$=$	$\{\backslash color\{blue\}\backslash mathcal\{LBA\}\}$	$\backslash supseteq$	$\backslash mathcal\{DLBA\}$
Typ-2-Grammatik	$\{\backslash color\{blue\}\backslash mathcal\{CF\}\}$	$=$	$\{\backslash color\{blue\}\backslash mathcal\{PDA\}\}$	$\backslash varsupsetneq$	$\backslash mathcal\{DPDA\}$
Typ-3-Grammatik	$\{\backslash color\{blue\}\backslash mathcal\{REG\}\}$	$=$	$\{\backslash color\{blue\}\backslash mathcal\{NFA\}\}$	$=$	$\{\backslash color\{blue\}\backslash mathcal\{DFA\}\}$

Die Mengeninklusion LBA ⊇ DLBA ist nur eine Vermutung, da bisher noch nicht bewiesen wurde, ob die DLBAs die gleiche Sprachklasse akzeptieren wie die LBAs. Die Gleichheit NTM = DTM steht im engen Zusammenhang mit dem P-NP-Problem (P≟NP).

Daneben gibt es weitere Automatentypen, die sich nicht am sequentiellen Einlesen einer Eingabe orientieren. Einige der bekannteren Automaten sind:

• Zelluläre Automaten
• Neuronale Netze
• Petri-Netze

Von praktischer Relevanz für die Programmierung sind vor allem Endliche Automaten und Kellerautomaten: sie bieten eine einfache Struktur, mit der sich viele komplexe Probleme übersichtlich lösen lassen. Im Compilerbau werden sie beispielsweise zur Implementierung von Parserenn eingesetzt, die Umsetzungen von Netzwerkprotokoll benutzen häufig einen endlichen Automaten, um ihren aktuellen Zustand zu modellieren. Auch die Navigationsmöglichkeiten in einem Wizard lassen sich sehr gut als endlicher Automat ausdrücken, und das Workflow-Management benutzt diese Konzepte zur Modellierung von Arbeitsabläufen.

Auch bei der Realisierung sequenzieller Hardware wird das Modell des Endlichen Automaten genutzt, dort meist als Finite State Machine (FSM) bezeichnet.

Siehe auch

• Automatentheorie
• Berechenbarkeitstheorie
• Komplexitätstheorie
• Formale Sprache
• Mathematische Maschine