Akzeptieren (Automaten- und Komplexitätstheorie)

Die Begriffe Akzeptieren und Entscheiden sind in der Automaten- und Komplexitätstheorie für viele in ihrer Wahrnehmung annähernd gleich. Sie sind es aber nicht genau. Aus diesem Wahrnehmungsunterschied haben Mathematiker folgenden formalen Unterschied konstruiert:

Es sei eine Menge von Eingaben gegeben. Von diesen möglichen Eingaben seien besondere herauszufiltern, die zu einer Menge A gehören.

Ein Algorithmus akzeptiert A, genau dann wenn er für genau die Elemente aus A terminiert und eine positive Antwort zurückliefert.

Ein Algorithmus entscheidet A, wenn er in jedem Falle eine Antwort liefert: ja im Fall, dass die Eingabe zu A gehört und nein sonst.

In den meisten Fällen ist es in der Automatentheorie unerheblich, zwischen Akzeptieren und Entscheiden zu unterscheiden. Nur in den Fällen, in denen nichtdeterministisch (siehe auch NP (Komplexitätsklasse)) gerechnet wird oder wenn es unendlich lange Berechnungen geben kann (siehe Rekursive Aufzählbarkeit), hier ist es sehr wohl von Bedeutung diesen sprachlich wahrgenommen Unterschied in unserer Definition zu nutzen.

Weblinks

Wiktionary Wiktionary: akzeptieren – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Wikimedia Foundation.

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

  • Akzeptieren — Akzeptanz (von lat. „accipere“ für annehmen, billigen, gutheißen) ist eine Substantivierung des Verbes akzeptieren, welches verstanden wird als annehmen, anerkennen, einwilligen, hinnehmen, billigen, mit jemandem oder etwas einverstanden sein.… …   Deutsch Wikipedia

  • Kontextfrei — In diesem Artikel oder Abschnitt fehlen folgende wichtige Informationen: OMA Verständlichkeit bei den Beispielen ausbauen Du kannst Wikipedia helfen, indem du sie recherchierst und einfügst. Als Kontextfreie Sprache ( …   Deutsch Wikipedia

  • Akzeptanz — (von lat. „accipere“ für gutheißen, annehmen, billigen) ist eine Substantivierung des Verbes akzeptieren, welches verstanden wird als annehmen, anerkennen, einwilligen, hinnehmen, billigen, mit jemandem oder etwas einverstanden sein.… …   Deutsch Wikipedia

  • Kontextfreie Grammatiken — Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ 2 Grammatiken der Chomsky Hierarchie. Inhaltsverzeichnis 1 Definition 2 Normalformen 3 Von G erzeugte Sprache 4 Eigenschaften …   Deutsch Wikipedia

  • Typ2-Grammatik — Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ 2 Grammatiken der Chomsky Hierarchie. Inhaltsverzeichnis 1 Definition 2 Normalformen 3 Von G erzeugte Sprache 4 Eigenschaften …   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

Share the article and excerpts

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