Was ist entscheidbar?
Gefragt von: Herr Dr. Hans-Jürgen Gerlach | Letzte Aktualisierung: 14. März 2021sternezahl: 4.2/5 (18 sternebewertungen)
In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar, wenn es ein Entscheidungsverfahren für sie gibt. Ein Entscheidungsverfahren ist ein Algorithmus, der für jedes Element der Menge beantworten kann, ob es die Eigenschaft hat oder nicht.
Wann ist eine Sprache entscheidbar?
Eine Sprache L ist entscheidbar genau dann, wenn L und L (das Komplement von L) aufzählbar sind. Beweis. (⇒) Ist L entscheidbar, dann ist L auch aufzählbar. Dreht man zudem die Ergebnisse einer TM, die L entscheidet, um, hat man eine TM, die L entscheidet.
Ist eine Sprache L Entscheidbar so ist auch jede Teilmenge von L entscheidbar?
Für jede rekursiv aufzählbare Sprache L gilt, dass L = Σ∗ − L. ... b) Sind L1 und L2 entscheidbare Sprachen, dann ist auch L1 ∪ L2 entscheidbar. c) Ist L nicht-regulär, so ist auch L (das Komplement von L) nicht-regulär. d) Ist L entscheidbar, so ist jede Teilmenge von L entscheidbar.
Ist das Halteproblem Semi Entscheidbar?
Eine typische abstrakte Maschine ist die Turingmaschine. Das Halteproblem beschreibt die Frage, ob die Ausführung eines Algorithmus zu einem Ende gelangt. ... Diesen Beweis vollzog er an einer Turingmaschine. Das Halteproblem ist somit algorithmisch nicht entscheidbar.
Wann hält eine turingmaschine an?
Wenn für jedes Paar, bestehend aus Zustand s und Zeichen a , höchstens ein solcher Zustandsübergang definiert ist, arbeitet die Turingmaschine deterministisch. Es kann auch sein, dass für einen Zustand s und ein Zeichen a kein Folgezustand definiert ist; in diesem Fall hält die Turingmaschine.
Entscheidbar, unentscheidbar, semi-entscheidbar?
22 verwandte Fragen gefunden
Sind alle Sprachen Entscheidbar?
Eine Sprache ist entscheidbar, wenn es eine Turingmaschine M gibt, die L akzeptiert und M zudem bei jeder Eingabe anhält. Wir haben dann verschiedene entscheidbare und aufzählbare Sprachen gesehen.
Ist die leere Sprache entscheidbar?
Die Entscheidbarkeit des Leerheitsproblems hängt von der Komplexität der zugrundeliegenden Grammatik ab: Für die Grammatiken vom Typ 2 oder höher in der Chomsky-Hierarchie ist das Leerheitsproblem entscheidbar, für die Grammatiken bis Typ 1 im Allgemeinen jedoch nicht. ...
Ist eine reguläre Sprache immer Kontextfrei?
Es gibt keine kontextfreie Sprache, die von einer regulären Grammatik erzeugt werden kann. Die Menge der kontextfreien Sprachen, die von einer regulären Grammatik erzeugt werden können, entspricht genau der Menge der regulären Sprachen.
Sind endliche Sprachen regulär?
Bei jeder Regelanwendung entsteht höchstens eine Varia- ble, und zwar am rechten Ende des Wortes. ... Zum Beispiel sind alle endlichen Sprachen regulär: Sei L eine Sprache mit endlich vielen Wörtern, also L = {w1,w2,...,wn}, dann kann man leicht eine rechtslineare Grammatik G für diese Sprache angeben.
Wann ist eine Sprache nicht regulär?
Reguläre Sprachen können von endlichen Automaten erkannt werden. ... Wenn also eine Sprache L={aib2i|i∈N} L = { a i b 2 i | i ∈ N } beschrieben wird, müsste gezählt werden, wie oft a vorkommt. a kann aber beliebig oft vorkommen. Das ist ein Indiz dafür, dass es sich nicht um eine reguläre Sprache handelt.
Wie nennt man eine turingmaschine die auf allen Eingaben im Zustand Accept oder Reject hält?
In der theoretischen Informatik ist eine alternierende Turingmaschine (ATM) eine nichtdeterministische Turingmaschine, welche die üblichen Regeln für die Akzeptanz einer Eingabe erweitert. Dabei werden die Zustände der Maschine in existentielle und universelle Zustände aufgeteilt.
Was sind häufige Kritikpunkte am Turing Test?
Der größte vorherrschende Kritikpunkt am Turing-Test ist der, dass dieser lediglich die Funktionalität eines Systems prüfe, jedoch nicht, ob der Intelligenz auch ein Bewusstsein oder eine Intentionalität zugrunde liegt. Eine der führenden Stimmen in diesem Kritikpunkt ist der Amerikanische Philosoph John Searle.
Wird die von einer turingmaschine akzeptierte Sprache L auch von einem endlichen Automaten akzeptiert?
Es ist nicht entscheidbar, ob eine Turingmaschine mehr als sieben Wörter akzeptiert. (Die Eigenschaft P ist also definiert durch P = {L | |L| ≥ 7}. ... Es ist nicht entscheidbar, ob eine Turingmaschine nur endlich viele Wörter akzeptiert (d. h. ob die von einer Turingmaschine akzeptierte Sprache endlich ist).
Wann ist eine Grammatik regulär?
Allgemein gilt: Jede Sprache, die endliche Automaten akzeptieren, wird von einer regulären Grammatik erzeugt.
Wann ist eine Grammatik eindeutig?
Eine Grammatik heißt eindeutig, wenn es für jedes Wort w ∈ L(G) genau eine Linksableitung gibt. Nicht eindeutige Grammatiken nennt man auch mehrdeutig. Eine Sprache L heißt eindeutig, wenn es für L eine eindeutige Grammatik gibt. Ansonsten heißt L mehrdeutig.
Wann ist eine Grammatik mehrdeutig?
gibt es zu einem Wort der Grammatik zwei verschiedene Rechts- oder zwei verschiedene Linksableitungsbäume, die nicht isomorph zueinander sind, dann heißt diese Grammatik mehrdeutig. ...
Was ist eine Grammatik Informatik?
Sie werden in der theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie, und im Compilerbau zum einen angewendet, um eindeutig festzulegen, ob ein Wort Element einer Sprache ist und zum anderen, um Eigenschaften dieser formalen Sprachen zu untersuchen bzw. ...