Rekursive Sprache - LinkFang.de





Rekursive Sprache


Eine Formale Sprache [math]L \subseteq \Sigma^*[/math] heißt rekursiv (entscheidbar), wenn eine Turingmaschine M existiert, die auf allen Eingaben [math]w \in \Sigma^*[/math] hält, d. h. [math]H_M = \Sigma^*[/math], und jede Eingabe [math]w \in \Sigma^*[/math] genau dann akzeptiert, wenn [math]w \in L[/math] ist.

Die Nicht-Rekursivität einer Sprache kann man mittels Satz von Rice nachweisen.

Wenn es keine Turingmaschine gibt, die ein solches Entscheidungsproblem löst, so gibt es nach der Churchschen These überhaupt keinen Algorithmus für das Problem. Man beschränkt sich bei dieser Definition auf Entscheidungsprobleme, also auf Probleme, deren Antwort nur Ja oder Nein sein kann. Es stellt sich aber heraus, dass sie trotz dieser Einschränkung meist ausreichend ist, da die zu Entscheidungsproblemen gehörenden Berechnungsprobleme meist nicht schwieriger zu lösen sind.

Der Vorteil ist, dass man alle Entscheidungsprobleme auf Sprachen zurückführen kann; diese können u. a. durch (Chomsky-) Grammatiken beschrieben werden: Eine Eingabe w ist für ein Entscheidungsproblem P genau dann eine Lösung, wenn w in der zu P gehörigen Sprache L liegt (Wortproblem). Somit besteht eine Brücke zwischen dem erzeugenden Grammatik-Modell und dem akzeptierenden Automaten-Modell. In der Tat kann man zu jeder Chomsky-Grammatik-Klasse eine Automatenklasse finden, die genau die Sprachen der jeweiligen Klasse akzeptiert und umgekehrt (Chomsky-Hierarchie).

Die Menge der rekursiven Sprachen ist echte Teilmenge der Chomsky-Typ-0- (oder rekursiv aufzählbaren) Sprachen und echte Obermenge der Chomsky-Typ-1-Sprachen:

  • Das Halteproblem ist rekursiv aufzählbar (Typ 0), aber nicht rekursiv
  • Es gibt Sprachen, die rekursiv, aber nicht kontextsensitiv (Typ 1) sind.

Die Menge der rekursiven Sprachen stimmt mit allen bisher vorgeschlagenen Berechenbarkeitsmodellen überein. Hierzu gehören insbesondere die Goto-Berechenbarkeit und die While-Berechenbarkeit welche aus den gängigsten Programmierkonstrukten am Computer hervorgehen. Diese Übereinstimmungen sind Ausgangspunkt für die Churchsche These.

(Beachte: Die durch primitive Rekursion erzeugten Sprachen bilden nur eine echte Teilmenge der rekursiven Sprachen; man kann zeigen, dass dies dann die gleichen Sprachen sind, die auch durch die Loop-Berechenbarkeit erzeugt werden.)

Der Unterschied zu den rekursiv aufzählbaren Sprachen ist definitionsgemäß, dass eine Turingmaschine für eine rekursive Sprache immer halten muss, während eine für eine rekursiv aufzählbare Sprache nur halten muss, wenn das Wort in der Sprache liegt.


Kategorien: Sprachtyp | Compilerbau | Theorie formaler Sprachen

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Rekursive Sprache (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.