Sprache ist rekursiv?
Gefragt von: Aloys Bauer | Letzte Aktualisierung: 16. April 2022sternezahl: 4.1/5 (39 sternebewertungen)
In der theoretischen Informatik heißt eine formale Sprache L über einem Alphabet \Sigma rekursiv, wenn eine Turingmaschine M existiert, die auf allen Eingaben w\in \Sigma ^{*} hält und jede Eingabe w\in \Sigma ^{*} genau dann akzeptiert, wenn w\in L ist.
Wann ist eine Sprache rekursiv?
Wann heißt eine Sprache rekursiv/entscheidbar? Eine Sprache L über einem Alphabet Σ ist rekursiv, wenn es eine Turing- maschine gibt, die auf allen Eingaben anhält und genau die Eingaben aus L akzeptiert.
Ist jede Sprache rekursiv Aufzählbar?
Alle rekursiven 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.
Wann ist eine Sprache Aufzählbar?
Eine Sprache L ist aufzählbar, wenn es eine Turingmaschine M gibt, die L akzeptiert, also eine mit L(M) = L. 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 versteht man unter rekursion?
Als Rekursion (lateinisch recurrere ‚zurücklaufen') wird ein prinzipiell unendlicher Vorgang, der sich selbst als Teil enthält oder mithilfe von sich selbst definierbar ist, bezeichnet.
Berechenbarkeit #39 - Rekursive Aufzählbarkeit
33 verwandte Fragen gefunden
Wie funktioniert eine Rekursion?
Rekursion ist ein Programmierkonzept, bei der eine Funktion nur einen kleinen Teil der Arbeit macht und damit ein Problem ein bisschen verkleinter, und sich dann selbst aufruft um den Rest des Problems zu lösen. Das wird so lange fortgesetzt, bis das Problem auf einen sehr einfachen Fall reduziert ist.
Was ist eine rekursive Funktion?
Unter Rekursion versteht man in der Programmierung ein Verfahren, bei dem sich eine Methode selbst aufruft, sodass, ähnlich einer Endlosschleife, ein potentiell unendlicher Programmablauf entsteht.
Wie zeigt man dass eine Sprache entscheidbar ist?
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.
Wann ist eine Grammatik kontextfrei?
Eine kontextfreie Grammatik ist in der Greibach-Normalform (GNF), wenn sie nicht das leere Wort erzeugt und die rechten Seiten der Produktionen mit maximal einem Terminal-Symbol beginnen und sonst nur Nichtterminal-Symbole enthalten.
Ist das Halteproblem rekursiv Aufzählbar?
Beispiel: Das Halteproblem H ist rekursiv aufzählbar. Falls H ebenfalls rekursiv aufzählbar, so wäre H entscheidbar. Daher ist H nicht rekursiv aufzählbar. Beobachtung Wenn eine Sprache L rekursiv aufzählbar ist, so ist ihr Komplement L nicht notwendigerweise rekursiv aufzählbar.
Wann ist eine Sprache kontextsensitiv?
Definition. Eine formale Sprache ist genau dann kontextsensitiv, wenn eine kontextsensitive Grammatik existiert, die diese Sprache erzeugt. Eine kontextsensitive Grammatik ist eine, die in jeder Regel immer ein Nichtterminal in einem Kontext in eine nichtleere Folge von Zeichen (Nichtterminale oder Terminale) ersetzt.
Warum ist das Halteproblem nicht entscheidbar?
Die Church-Turing-These besagt, dass alles, was intuitiv berechenbar ist, auch von einer Turingmaschine berechenbar ist. Wenn diese Aussage wahr ist, kann das Halteproblem grundsätzlich nicht algorithmisch entschieden werden.
Was ist rekursion Linguistik?
[1] Linguistik: Eigenschaft einer Grammatik, mit dort formulierten Regeln (unendlich viele) Sätze bilden zu können. [2] Psychologie, Management, Kybernetik: Rückbezüglichkeit einer Handlung, eines Verhaltens. Herkunft: Ableitung (Suffigierung) vom Adjektiv rekursiv mit dem Derivatem (Ableitungsmorphem) -ität.
Wann ist eine Grammatik regulär?
Definition: Reguläre Grammatik
Eine Grammatik G = ( N , T , P , S ) G = (N,T,P,S) G=(N,T,P,S) heißt regulär, wenn in allen Produktionen jeweils genau ein Nichtterminal ersetzt werden kann durch genau ein Nichtterminal oder genau ein Terminal oder genau ein Nichtterminal verknüpft mit genau einem Terminal.
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.
Was ist eine Rechtslineare Grammatik?
Eine Grammatik (N, T, S, P) heiÿt rechtslinear, wenn alle Regeln/Produktionen die folgende Form haben: A → a oder A → aB wobei a ∈ T ∪ {ε} und A, B ∈ N. Eine durch eine rechtslineare Grammatik erzeugte Sprache heiÿt rechtslinear.
Wann ist etwas entscheidbar?
Eine allgemeinere Klasse als die entscheidbaren Mengen sind die rekursiv aufzählbaren oder semi-entscheidbaren Mengen, bei denen lediglich für „ja“ gefordert wird, dass die Berechnung in endlicher Zeit anhält. Wenn sowohl eine Menge als auch ihr Komplement semi-entscheidbar sind, dann ist die Menge entscheidbar.
Wann ist eine Turingmaschine entscheidbar?
T(w) bezeichnet die Ausgabe von T für Eingabe w. T heißt die transformierende Turingmaschine. Das Problem L sei unentscheidbar. Wenn L ⩽ K, dann ist auch K unentscheidbar.
Ist eine reguläre Sprache entscheidbar?
Für reguläre Sprachen sind all diese Fragen entscheidbar, d.h., man kann Algorithmen angeben, die diese Fragen immer eindeutig beantworten. 1.37 Satz Sei L eine reguläre Sprache, die durch einen der beschriebenen Formalismen spe- zifiziert ist, und sei w ein Wort.
Was ist eine rekursive Folge?
Das lateinische recurro bedeutet ” umkehren“ oder ” zurückgehen“. Grob gesprochen erhält man das Glied an einer rekursiven Folge, indem man an aus einer festen Anzahl vorhergehender Glieder berechnet, etwa an+2 = an+1 + an.
Was ist eine rekursive Darstellung?
Eine Möglichkeit der Darstellung einer Zahlenfolge ist die Angabe einer rekursive Bildungsvorschrift. Eine rekursive Bildungsvorschrift gibt an, wie man ein beliebiges Glied an + 1 einer Zahlenfolge aus seinem Vorgänger an oder auch aus mehreren Vorgängern an, an − 1 usw.
Warum rekursiv programmieren?
Welche Bedeutung hat die rekursive Programmierung? Mit Hilfe der Rekursion kann man viele Probleme elegant lösen. Das gilt speziell, wenn man die Berechnung dem Computer überlassen will. Dieses Leitprogramm stellt dir in den ersten drei Kapiteln die Rekursion als Technik und Programmierkonzept vor.
Wie nennt man eine Funktion die sich selbst aufruft?
In der Programmierung nennt man Funktion, die sich selbst aufrufen, rekursive Funktionen – ein Konzept, das es in nahezu allen Programmiersprachen gibt. Rekursionen wiederholen Anweisungen in einer immer wieder gleichen Art und Weise.
Ist Rekursion ein Algorithmus?
Ein Algorithmus ist rekursiv, wenn in seiner (endlichen) Beschreibung derselbe Algorithmus wieder aufgerufen wird. Ein rekursiver Algorithmus ist daher selbstbezüglich definiert In Java können rekursiver Algorithmen durch rekursive Methoden implementiert werden.
Wann ist eine Rekursion linear?
Lineare Rekursion: Eine rekursive Funktion bzw. Funktionsdeklaration heißt linear rekursiv, wenn in jedem Zweig einer if-then-else oder Pattern-Matching Anweisung höchstens ein Selbstaufruf der Funktion auftritt. Eine Funktion ist genau dann linear rekursiv, wenn ihre Aufruf- struktur linear ist.