Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Formale Sprachen WS19/20 Kurs an der Universität Salzburg zu.
117213
Karteikarten
1519
Studierende
19
Lernmaterialien
Ist die Sprache SubsetSum NP Vollständig?
Ja
Definition Halteproblem
Das Halteproblem ist rekursiv aufzählbar
Das Halteproblem kann auf das Akzeptanzproblem reduziert werden. A ≤ Halteproblem
Das Halteproblem ist NICHT entscheidbar.
inf-Schule:
Das Halteproblem besteht darin, ein Programm (bzw. Algorithmus) zu entwickeln, mit dem man testen kann, ob ein übergebenes Programm bei der Verarbeitung übergebener Daten hält oder nicht.
Wikipedia:
Das Halteproblem beschreibt eine Frage aus der theoretischen Informatik.
Wenn für eine Berechnung mehrere Rechenschritte nach festen Regeln durchgeführt werden, entsteht eine Berechnungsvorschrift, ein sogenannter Algorithmus. Zur Ausführung von Algorithmen benutzt man in der theoretischen Informatik abstrakte Maschinen. Eine typische abstrakte Maschine ist die Turingmaschine. Das Halteproblem beschreibt die Frage, ob die Ausführung eines Algorithmus zu einem Ende gelangt. Obwohl das für viele Algorithmen leicht beantwortet werden kann, konnte der Mathematiker Alan Turing beweisen, dass es keinen Algorithmus gibt, der diese Frage für alle möglichen Algorithmen und beliebige Eingaben beantwortet. Diesen Beweis vollzog er an einer Turingmaschine. Das Halteproblem ist somit algorithmisch nicht entscheidbar. Das Resultat spielt eine grundlegende Rolle in der Berechenbarkeitstheorie. Der Begriff Halteproblem wurde nicht von Turing geprägt, sondern erst später durch Martin Davis in seinem Buch Computability and Unsolvability.[1]
Ist die Sprache Diag rekursiv aufzählbar?
Nein
Definition Klasse NP
NP ist die Klasse der Sprachen, die polynomiell verifizierbar sind.
Anders ausgedrückt: NP ist die Klasse der Sprachen, die von einer NTM mit polynomieller Lauftzeit entschieden werden.
P ist eine Teilmenge von NP.
Das Akzeptanzproblem ist auf 3-SAT reduzierbar
Nein
Ist die Sprache Clique NP-Vollständig
Ja
Definition Klasse P
Die Klasse P ist die Menge aller Sprachen, die von einer DTM in polynomieller Zeit entschieden werden können.
Die Sprache USEFUL ist rekursiv aufzählbar
Ja
Die Sprache USEFUL ist entscheidbar
Nein
Die Sprache USEFUL ist auf SAT reduzierbar
Nein
Definition von Rekursive Sprache(entscheidbare Sprache)
Eine Sprache L heißt rekursiv oder entscheidbar, falls es eine Turingmaschine M gibt, die L entscheidet
Eine rekursive Sprache ist auch immer rekursiv aufzählbar, aber gilt nicht in die Gegenrichtung.
Definition von Rekursiv aufzählbar
In der theoretischen Informatik ist eine rekursiv aufzählbare Sprache oder semientscheidbare Sprache L dadurch definiert, dass es eine Turingmaschine gibt,die alle Wörter aus L akzeptiert, aber keine Wörter, die nicht in L liegen. Im Unterschied zu rekursiven Sprachen (entscheidbare Sprachen) muss bei den rekursiv aufzählbaren Sprachen die Turingmaschine nicht halten, wenn ein Wort nicht in L liegt. Das heißt, unter Umständen muss man auf die Lösung unendlich lange warten. Alle rekursiven Sprachen (entscheidbare Sprachen) sind deshalb auch rekursiv aufzählbar.
Rekursiv aufzählbare Sprachen bilden die oberste Stufe der Chomsky-Hierarchie und heißen deshalb auch Typ-0-Sprachen; die entsprechenden Grammatiken sind die Typ-0-Grammatiken. Sie können somit auch als all die Sprachen definiert werden, deren Wörter sich durch eine beliebige formale Grammatik ableiten lassen.
Eines der wichtigsten Probleme, das rekursiv aufzählbar ist, aber nicht rekursiv, ist das so genannte Halteproblem. Eine Sprache L heißt rekursiv aufzählbar, falls es eine Turingmaschine M gibt, die L akzeptiert.
Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.
Jetzt loslegenFür deinen Studiengang Formale Sprachen WS19/20 an der Universität Salzburg gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!
