Automatenmodelle

Automatenmodelle sind formale mathematische Maschinen, die Eingaben verarbeiten, um eine Entscheidung oder eine Zugehörigkeit zu einer Sprache zu treffen. Typische Merkmale sind eine endliche Menge von Zuständen, ein Eingabealphabet, eine Übergangsfunktion, ein Startzustand und eine Menge von akzeptierenden Zuständen. Auf Basis dieser Definitionen werden verschiedene Arten von Automaten unterschieden, darunter deterministische und nichtdeterministische Modelle.

Ein deterministischer endlicher Automat (DFA) oder ein nichtdeterministischer endlicher Automat (NFA) verarbeitet eine endliche Eingabe, wobei der nächste Zustand eindeutig bestimmt ist (DFA) bzw. durch mögliche Pfade bestimmt wird (NFA). Endliche Automaten erkennen reguläre Sprachen. Pushdown-Automaten (PDA) erweitern das Modell um einen Stack und erkennen kontextfreie Sprachen. Turingmaschinen bilden ein wesentlich leistungsfähigeres Modell: Sie besitzen unendlichen Speicher, können jeden berechenbaren Prozess simulieren und definieren die Klasse der rekursiv aufzählbaren Sprachen. Eine linear-beschränkte Turingmaschine ist eine Spezialvariante, die den Speicher linear zur Eingabe beschränkt nutzt und die Entscheidungsprobleme der kontextsensitiven Sprachen adressiert.

Die Chomsky-Hierarchie ordnet Sprachklassen von regulär bis rekursiv aufzählbar. Reguläre Sprachen sind durch DFAs/NFAs beschreibbar; kontextfreie Sprachen durch PDAs; kontextsensitive Sprachen durch linear beschränkte Automaten; rekursiv aufzählbare Sprachen durch Turingmaschinen. Entscheidungsprobleme variieren je nach Modell; etwa ist die Leere- und Äquivalenzfrage bei regulären Sprachen entscheidbar, während das Halteproblem für Turingmaschinen unentscheidbar ist.

Automatenmodelle finden breite Anwendung in der Computerwissenschaft: Lexikalische Analyse, Mustererkennung, Netzwerk- und Protokollverifikation sowie Formale Verifikation und Modellprüfung. Erweiterungen umfassen probabilistische Automaten, die Wahrscheinlichkeiten in den Übergängen verwenden, zelluläre Automaten für komplexe dynamische Systeme sowie Quanten- und transduktive Automatenformen, die in der Forschung untersucht werden.