Akzeptor (Informatik)

Ein Akzeptor ist in der theoretischen Informatik ein spezieller endlicher Automat. Akzeptoren zeichnen sich dadurch aus, dass sie im Gegensatz zu Transduktoren keine Ausgabe erzeugen. Sie lesen ein Wort ein und akzeptieren oder verwerfen es.

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.

Weblinks

Literatur


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Akzeptor — (Empfänger) steht für: in der Chemie: Protonenakzeptor Elektronenakzeptor Akzeptor (Physik), eine Störung in einem Halbleiter Akzeptor (Informatik), ein spezieller endlicher Automat Akzeptor (Pränatalmedizin), der größere Zwilling beim… …   Deutsch Wikipedia

  • Automat (Informatik) — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • Akzeptoren — Akzeptor (Empfänger) steht für: in der Chemie: Protonenakzeptor Elektronenakzeptor Akzeptor (Festkörperphysik), eine Störung in einem Halbleiter Akzeptor (Informatik), ein spezieller endlicher Automat Akzeptor (Pränatalmedizin), der größere… …   Deutsch Wikipedia

  • Abstrakte Maschine — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • Abstrakter Automat — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • Automatenmodell — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • Maschinenmodell — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • Rechnermodell — Ein Automat oder eine abstrakte Maschine ist in der Informatik das Modell eines digitalen, zeitdiskreten Rechners. Ob es möglich oder sinnvoll ist, eine solche Maschine tatsächlich zu bauen, ist dabei zunächst unerheblich. Die Vereinfachung der… …   Deutsch Wikipedia

  • Medvedev-Automat — In der theoretischen Informatik versteht man unter einem Medwedew Automaten einen endlichen Automaten, der keine Ausgabe hat. Als Indikator dienen die Zustände, wobei bei manchen Automaten Akzeptanzzustände (Endzustände) existieren, ein solcher… …   Deutsch Wikipedia

  • Finite-State-Machine — Abb.1 Beispiel eines EA Ein endlicher Automat (EA, auch Zustandsmaschine, englisch finite state machine (FSM)) ist ein Modell des Verhaltens, bestehend aus Zuständen, Zustandsübergängen und Aktionen. Ein Automat heißt endlich, wenn die Menge der… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”