Automat (Informatik)
Die Automaten sind meist ähnlich aufgebaut: Der Automat hat einen inneren Zustand und bekommt eine Eingabe, die (meistens) Zeichen für Zeichen gelesen werden. 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 in deterministischer und nichtdeterministischer Variante):
- Endliche Automaten: akzeptieren die Typ-3-Sprachen (Reguläre Sprachen)
- Kellerautomaten: akzeptieren die Typ-2-Sprachen (Kontextfreie Sprachen)
- Turingmaschinen: akzeptieren die Typ-0-Sprachen (und damit auch Typ-1-Sprachen). Durch die Turingmaschine wird außerdem der Begriff der Berechenbarkeit definiert. Siehe Churchsche These.
- Registermaschinen: sind genau so mächtig wie Turingmaschinen, bieten aber in einigen Fällen ein besseres Maß für die Zeitkomplexität.
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 Implementation von Parsern eingesetzt, die Umsetzungen von Netzwerkprotokollen 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.