Akzeptor (Informatik)

Aufgabe und Funktionsweise

Ein Akzeptor ist in der theoretischen Informatik ein spezieller endlicher Automat. Anders als ein Transduktor erzeugt er keine Ausgabe. Er liest ein Wort Zeichen für Zeichen: In jedem Verarbeitungsschritt nimmt er genau ein Eingabezeichen entgegen und bleibt danach entweder im bisherigen Zustand oder wechselt in einen neuen Zustand.

Ein Wort wird akzeptiert, wenn der Akzeptor nach dem vollständigen Lesen der Eingabe in einem Finalzustand terminiert. Endet die Verarbeitung nicht in einem solchen Zustand, wird das Wort verworfen.

Die Gesamtheit aller akzeptierten Wörter heißt formale Sprache. Akzeptoren dienen damit dazu, formale Sprachen zu beschreiben. Die von Akzeptoren beschreibbaren Sprachen sind genau die regulären Sprachen; diese Klasse ist äquivalent zu der Klasse der Sprachen, die durch reguläre Ausdrücke beschrieben werden.

Formale Bestandteile und Arten

Ein endlicher Akzeptor wird formal als A = (Z, z₀, X, f, F) angegeben. Dabei ist Z eine endliche Zustandsmenge, z₀ ∈ Z der Anfangszustand, X das Eingabealphabet, f ⊆ Z × X × Z die Zustandsüberführungsrelation und F ⊆ Z die Menge der akzeptierenden Zustände.

Ist die Zustandsüberführungsrelation f eine Funktion, liegt ein deterministischer endlicher Automat vor. Andernfalls ist der Automat nichtdeterministisch.

Bekannte Akzeptoren

Bekannte Akzeptoren und die zugehörigen Sprachklassen sind:

• Endliche Automaten für reguläre Sprachen (Chomsky Typ 3).
• Kellerautomaten für kontextfreie Sprachen (Chomsky Typ 2).
• Deterministische Kellerautomaten für deterministisch kontextfreie Sprachen.
• Linear beschränkte Turingmaschinen für kontextsensitive Sprachen (Chomsky Typ 1).
• Turingmaschinen für Typ-0-Grammatiken, also unbeschränkte Grammatiken.