imported>T. Wirbitzki: Änderung 238846355 von 85.239.123.129 rückgängig gemacht; Plural hier grammatisch verkehrt und unnötig, da eine Relation bereits eine Menge von Tupeln ist

2023-11-06T19:22:34Z

Änderung 238846355 von 85.239.123.129 rückgängig gemacht; Plural hier grammatisch verkehrt und unnötig, da eine Relation bereits eine Menge von Tupeln ist

Neue Seite

Ein '''Akzeptor''' ist in der [[Theoretische Informatik|theoretischen Informatik]] ein spezieller [[endlicher Automat]]. Er zeichnet sich dadurch aus, dass er im Gegensatz zu einem [[Transduktor (Informatik)|Transduktor]] keine Ausgabe erzeugt. Er liest ein [[Wort (Theoretische Informatik)|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 [[Alphabet (Informatik)|Eingabealphabet]], eine Zustandsmenge, einen Startzustand und Akzeptorzustände, sowie eine [[Transitionsrelation|Zustandsüberführungsrelation]] definiert. Ist die Zustandsüberführungsrelation eine Funktion, handelt es sich um einen [[Deterministischer endlicher Automat|deterministischen endlichen Automaten]], andernfalls um einen [[Nichtdeterministischer endlicher Automat|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ärer Ausdruck|reguläre Ausdrücke]] beschriebenen Sprachen, nämlich der [[Reguläre Sprache|regulären Sprachen]].

Formal ist ein endlicher Akzeptor <math>A = (Z, z_0, X, f, F)</math> festgelegt durch:
* eine endliche Zustandsmenge <math>Z</math>,
* einen Anfangszustand <math>z_0 \in Z</math>,
* ein Eingabealphabet <math>X</math>,
* eine Zustandsüberführungsrelation <math>f \subseteq Z \times X \times Z</math>,
* eine Menge <math>F \subseteq Z</math> akzeptierender Zustände.

== Bekannte Akzeptoren ==
* [[Endlicher Automat|Endliche Automaten]], für [[reguläre Sprache]]n (Chomsky Typ 3)
* [[Kellerautomat]]en, für [[kontextfreie Sprache]]n (Chomsky Typ 2)
* [[Deterministischer Kellerautomat|Deterministische Kellerautomaten]], für [[deterministisch kontextfreie Sprache]]n
* [[Linear beschränkte Turingmaschine]]n, für [[kontextsensitive Sprache]]n (Chomsky Typ 1)
* [[Turingmaschine]]n, für [[Typ-0-Grammatik]]en (unbeschränkte Grammatiken)

== Siehe auch ==
* [[Transduktor (Informatik)|Transduktor]]
* [[Compiler]]
* [[Parser]]

== Literatur ==
* {{Literatur |Autor=Renate Winter |Titel=Theoretische Informatik |TitelErg=Grundlagen mit Übungsaufgaben und Lösungen |Verlag=Oldenbourg |Datum=2002 |ISBN=3-486-25808-7 |Seiten=74 |Online={{Google Buch |BuchID=EB7Cdjcw54QC |Seite=74}}}}

== Weblinks ==
* [https://www.philipphauer.de/info/info/akzeptor-erkennender-automat/ Der Akzeptor. Aufbau, Arbeitsweise und Sprache anschaulich illustriert.]

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Automatentheorie]]

Akzeptor (Informatik) - Versionsgeschichte

imported>T. Wirbitzki: Änderung 238846355 von 85.239.123.129 rückgängig gemacht; Plural hier grammatisch verkehrt und unnötig, da eine Relation bereits eine Menge von Tupeln ist