Was ist das wortproblem?
Gefragt von: Herr Prof. Hendrik Fritsch | Letzte Aktualisierung: 20. August 2021sternezahl: 4.2/5 (59 sternebewertungen)
Als Wortproblem einer formalen Sprache bezeichnet man in der Theoretischen Informatik das Entscheidungsproblem, zu einem gegebenen Wort festzustellen, ob dieses zur Sprache gehört, oder nicht.
Ist das Wortproblem Entscheidbar?
Das Wortproblem für Typ-0-Sprachen ist rekursiv aufzählbar und nicht entscheidbar. Das Wortproblem für Typ-1-Sprachen ist entscheidbar. Der Zeitbedarf ist höchstens exponentiell, die Platzkomplexität ist exakt linear. Damit ist insbesondere das Wortproblem für weiter eingeschränkte Sprachklassen ebenfalls entscheidbar.
Wann ist eine Sprache regulär?
Eine Sprache ist regulär, wenn: die Sprache von einer regulären Grammatik erzeugt wird; endliche Automaten sie akzeptieren; und die Sprache durch einen regulären Ausdruck dargestellt werden kann.
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.
Ist die Sprache L regulär?
Jeder reguläre Ausdruck r definiert eine reguläre Sprache, d.h. L(r) ∈ LREG(I) . 2. Jede reguläre Sprache L ∈ LREG(I) lässt sich durch einen regulären Ausdruck beschreiben, d.h. es existiert ein regulärer Ausdruck r ∈ LREX(I) mit L(r) = L.
Berechenbarkeit #47 - Das Wortproblem für Typ-1-Sprachen ist entscheidbar
20 verwandte Fragen gefunden
Ist das Halteproblem Semi entscheidbar?
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. ... Das Halteproblem ist somit algorithmisch nicht entscheidbar.
Was besagt der Satz von Rice?
Benannt wurde der Satz nach Henry Gordon Rice, der ihn 1953 veröffentlichte. Er besagt, dass es unmöglich ist, eine beliebige nicht-triviale Eigenschaft der erzeugten Funktion einer Turing-Maschine (oder eines Algorithmus in einem anderen Berechenbarkeitsmodell) algorithmisch zu entscheiden.
Wann ist der Satz von Rice nicht anwendbar?
Rice ist dagegen nicht anwendbar auf: • „Hat M mindestens zwei Zustände? “ (keine Eigenschaft von L(M)) • „Ist L(M) semi-entscheibar? “ (trivial) • ... Der Satz von Rice lässt sich sinngemäß auf alle Turing-mächtigen Formalismen übertragen.
Welche Sprachen sind 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.
Was ist Turingmächtig?
Mit Turing-Vollständigkeit eines Systems wird seine universelle Programmierbarkeit beschrieben. Für die Adjektivform Turing-vollständig wird synonym häufig auch turingmächtig verwendet. Der Name ist abgeleitet vom englischen Mathematiker Alan Turing, der das Modell der universellen Turingmaschine eingeführt hat.
Was besagt die Church Turing These?
Church-Turing-These, von Church 1936 aufgestellte These, die besagt, daß der intuitive Berechenbarkeitsbegriff adäquat durch den Begriff der Turing-Berechenbarkeit (Turing- Maschine, berechenbare Funktion) erfaßt wird.
Was bedeutet intuitiv berechenbar?
Intuitiv versteht man unter ” Berechenbarkeit“ alles, was sich algorithmisch lösen lässt.
Wann ist eine Funktion Turing berechenbar?
Eine (partielle) Funktion f : Σ∗ → Σ∗ heisst Turing-berechenbar, wenn eine DTM existiert, die f berechnet.
Wie funktioniert eine turingmaschine?
Eine Turingmaschine repräsentiert einen Algorithmus bzw. ein Programm. Eine Berechnung besteht dabei aus schrittweisen Manipulationen von Symbolen bzw. Zeichen, die nach bestimmten Regeln auf ein Speicherband geschrieben und auch von dort gelesen werden.
Ist SQL Turing-vollständig?
Eine gegebene Programmiersprache wird als Turing-vollständig bezeichnet, wenn gezeigt werden kann, dass sie einer Turing-Maschine rechnerisch äquivalent ist. Die TSQL ist Turing Complete, weil wir in TSQL einen BrainFuck- Interpreter erstellen können. ... Das ist Transact SQL, das vollständig ist.
Ist Excel Turing-vollständig?
Mit der neuen Formel-Funktion «LAMBDA» können Formeln in Excel nun automatisiert werden. Dies ermöglicht, dass persönlich definierte Vorgänge als Formeln verwendet werden können. Mit diesem Schritt wird Excel offiziell Turing-Vollständig.
Was kann die Turingmaschine?
Eine Turingmaschine kann das Zeichen der aktuellen Zelle auslesen oder auch überschreiben, den Lese-/Schreibkopf zur nächstliegenden entweder linken oder rechten Zelle des Datenbandes positionieren und den internen Zustand entsprechend den ausgelesenen Daten ändern.
Wann hält eine Turingmaschine an?
Ein Zustandsübergang für den Zustand 0 und das Zeichen b ist in der Turingtabelle nicht definiert. Dies führt dazu, dass die Turingmaschine hält, wenn sie im Zustand 0 ist und das Zeichen b liest. Da der Zustand 0 nicht der Endzustand ist, weist sie das Eingabewort in diesem Fall zurück.
Wann sind Turingmaschinen Äquivalent?
Zwei Turingmaschinen A und B heißen genau dann äquivalent, wenn sie die gleiche Sprache akzeptieren, d.h. L(A) = L(B) gilt. Zu jeder DTM A mit beidseitig unendlichem Arbeitsband gibt es eine äquivalente DTM B mit einseitig unendlichem Arbeitsband und umgekehrt.
Was ist eine totale Funktion?
Definition 12.3.1 (totale Funktion). Eine Funktion ist eine Relation R ⊆ M × N über dem Definitionsbereich M und dem Wertebereich N, welche folgende Eigenschaften hat: Jedes Element aus dem Definitionsbereich M ist mit höchstens einem Element aus dem Wertebereich N verbunden.
Ist Pi berechenbar?
Beispiele für solche Zahlen sind die Zahl Pi oder die Eulersche Zahl e = 2,7182818285.. . ... Es ist daher durchaus denkbar, dass man relle Zahlen mathematisch definieren kann, die nicht nur nicht-berechenbar sind, sondern die sogar Zufallszahlen sind (die also nicht komprimierbar sind).
Ist die Menge der berechenbaren und totalen Funktionen N nach N abzählbar?
In einem zweiten Schritt bestimmt man aus den Turingmaschinen die jeweils berechneten Funktionen. Beachte, dass nicht gefordert ist, dass diese Schritte algorithmisch durchgeführt werden müssen. Die Menge aller Turingmaschinen-berechenbaren Funktionen von N nach N ist abzählbar.
Was versteht man unter Berechenbarkeit?
Eine mathematische Funktion ist berechenbar (auch effektiv berechenbar oder rekursiv), wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann (Berechenbarkeitstheorie). ... In der Berechenbarkeitstheorie heißen genau die Funktionen berechenbar, die Turing-berechenbar sind.
Sind alle Sprachen entscheidbar?
Satz Jede kontextfreie Sprache ist entscheidbar! startet M die TM M auf der Eingabe 〈G,w〉.
Wann ist eine formale Sprache entscheidbar?
D.h. eine Sprache A heißt entscheidbar, wenn es eine Turingmaschine M mit A = L(M) gibt, die bei jeder Eingabe hält, wobei L(M) die von der TM M akzeptierte Sprache ist. Jede entscheidbare Sprache ist auch rekursiv aufzählbar, d.h. ist eine Sprache nicht rekursiv aufzählbar, dann ist sie auch nicht entscheidbar.