Select your language

Suggested languages for you:
Log In Anmelden

Lernmaterialien für Formale Sprachen WS19/20 an der Universität Salzburg

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Formale Sprachen WS19/20 Kurs an der Universität Salzburg zu.

TESTE DEIN WISSEN

Ist die Sprache SubsetSum NP Vollständig?

Lösung anzeigen
TESTE DEIN WISSEN

Ja

Lösung ausblenden
TESTE DEIN WISSEN

Definition Halteproblem

Lösung anzeigen
TESTE DEIN WISSEN

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]

Lösung ausblenden
TESTE DEIN WISSEN

Ist die Sprache Diag rekursiv aufzählbar?

Lösung anzeigen
TESTE DEIN WISSEN

Nein

Lösung ausblenden
TESTE DEIN WISSEN

Definition Klasse NP

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

Das Akzeptanzproblem ist auf 3-SAT reduzierbar

Lösung anzeigen
TESTE DEIN WISSEN

Nein

Lösung ausblenden
TESTE DEIN WISSEN

Ist die Sprache Clique NP-Vollständig

Lösung anzeigen
TESTE DEIN WISSEN

Ja

Lösung ausblenden
TESTE DEIN WISSEN

Definition Klasse P

Lösung anzeigen
TESTE DEIN WISSEN

Die Klasse P ist die Menge aller Sprachen, die von einer DTM in polynomieller Zeit entschieden werden können.

Lösung ausblenden
TESTE DEIN WISSEN

Die Sprache USEFUL ist rekursiv aufzählbar

Lösung anzeigen
TESTE DEIN WISSEN

Ja

Lösung ausblenden
TESTE DEIN WISSEN

Die Sprache USEFUL ist entscheidbar

Lösung anzeigen
TESTE DEIN WISSEN

Nein

Lösung ausblenden
TESTE DEIN WISSEN

Die Sprache USEFUL ist auf SAT reduzierbar

Lösung anzeigen
TESTE DEIN WISSEN

Nein

Lösung ausblenden
TESTE DEIN WISSEN

Definition von Rekursive Sprache(entscheidbare Sprache)

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

Definition von Rekursiv aufzählbar

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
  • 117213 Karteikarten
  • 1519 Studierende
  • 19 Lernmaterialien

Beispielhafte Karteikarten für deinen Formale Sprachen WS19/20 Kurs an der Universität Salzburg - von Kommilitonen auf StudySmarter erstellt!

Q:

Ist die Sprache SubsetSum NP Vollständig?

A:

Ja

Q:

Definition Halteproblem

A:

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]

Q:

Ist die Sprache Diag rekursiv aufzählbar?

A:

Nein

Q:

Definition Klasse NP

A:

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.

Q:

Das Akzeptanzproblem ist auf 3-SAT reduzierbar

A:

Nein

Mehr Karteikarten anzeigen
Q:

Ist die Sprache Clique NP-Vollständig

A:

Ja

Q:

Definition Klasse P

A:

Die Klasse P ist die Menge aller Sprachen, die von einer DTM in polynomieller Zeit entschieden werden können.

Q:

Die Sprache USEFUL ist rekursiv aufzählbar

A:

Ja

Q:

Die Sprache USEFUL ist entscheidbar

A:

Nein

Q:

Die Sprache USEFUL ist auf SAT reduzierbar

A:

Nein

Q:

Definition von Rekursive Sprache(entscheidbare Sprache)

A:

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.

Q:

Definition von Rekursiv aufzählbar

A:

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.

Formale Sprachen WS19/20

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Formale Sprachen WS19/20 an der Universität Salzburg

Fü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!

Das sind die beliebtesten Formale Sprachen WS19/20 Kurse im gesamten StudySmarter Universum

Automaten und formale Sprachen

TU Darmstadt

Zum Kurs
Formale Sprachen und Automaten

Hochschule des Bundes für öffentliche Verwaltung

Zum Kurs
Formale Sprachen II

Duale Hochschule Baden-Württemberg

Zum Kurs
Automaten und Formale Sprachen

Hochschule Furtwangen

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Formale Sprachen WS19/20
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Formale Sprachen WS19/20