Akzeptor (Informatik)
Ein Akzeptor ist in der theoretischen Informatik ein spezieller endlicher Automat. Er zeichnet sich dadurch aus, dass er im Gegensatz zu einem Transduktor keine Ausgabe erzeugt. Er liest ein Wort ein, indem er ein Eingabezeichen pro Verarbeitungsschritt entgegennimmt und nach jedem gelesenen Zeichen entweder im selben Zustand bleibt oder in einen neuen übergeht. Die Eingabe wird genau dann akzeptiert, wenn der Akzeptor in einem Finalzustand terminiert. Andernfalls wird das Wort verworfen.
Akzeptoren werden über ein Eingabealphabet, eine Zustandsmenge, einen Startzustand und Akzeptorzustände, sowie eine Zustandsüberführungsrelation definiert. Ist die Zustandsüberführungsrelation eine Funktion, handelt es sich um einen deterministischen endlichen Automaten, andernfalls um einen nicht-deterministischen endlichen Automaten.
Die Menge aller Wörter, die ein Akzeptor akzeptiert, ist eine formale Sprache. Mit Akzeptoren lassen sich also formale Sprachen beschreiben. Die Klasse der durch Akzeptoren beschriebenen Sprachen ist äquivalent zu der Klasse der durch reguläre Ausdrücke beschriebenen Sprachen, nämlich der regulären Sprachen.
Formal ist ein endlicher Akzeptor festgelegt durch:
- eine endliche Zustandsmenge ,
- einen Anfangszustand ,
- ein Eingabealphabet ,
- eine Zustandsüberführungsrelation ,
- eine Menge akzeptierender Zustände.
Bekannte Akzeptoren
- 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 (unbeschränkte Grammatiken)
Siehe auch
Literatur
- Renate Winter: Theoretische Informatik. Grundlagen mit Übungsaufgaben und Lösungen. Oldenbourg, 2002, ISBN 3-486-25808-7, S. 74 (eingeschränkte Vorschau in der Google-Buchsuche).