Akzeptieren (Automaten- und Komplexitätstheorie)
- 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
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