Rekursiv aufzählbare Sprache - LinkFang.de





Rekursiv aufzählbare Sprache


In der theoretischen Informatik ist eine rekursiv aufzählbare Sprache oder semientscheidbare Sprache [math]L[/math] dadurch definiert, dass es eine Turingmaschine gibt, die alle Wörter aus [math]L[/math] akzeptiert, aber keine Wörter, die nicht in [math]L[/math] liegen. Im Unterschied zu rekursiven Sprachen (entscheidbare Sprachen) muss bei den rekursiv aufzählbaren Sprachen die Turingmaschine nicht halten, wenn ein Wort nicht in [math]L[/math] liegt. Das heißt, unter Umständen muss man auf die Lösung unendlich lange warten. 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. 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.

Ein nicht semi-entscheidbares Problem ist die so genannte Diagonalsprache [math]D[/math]: die Menge der Codierungen all derjenigen Turingmaschinen, die auf ihrer eigenen Codierung als Eingabe nicht halten.

D = {<M> | M hält nicht auf <M>}

Auch das Komplement des (semi-entscheidbaren) Halteproblems ist nicht semi-entscheidbar, während das Komplement der Diagonalsprache semi-entscheidbar ist. In der Tat ist das Komplement des Halteproblems eine Erweiterung der Diagonalsprache und das Komplement der Diagonalsprache ein Spezialfall des Halteproblems.

Ein Beispiel für eine Sprache, für die weder sie selbst noch ihr Komplement semi-entscheidbar ist, ist das Äquivalenzproblem für Turingmaschinen (Eq): die Menge von Paaren von zwei Turingmaschinen, die dieselbe Sprache akzeptieren.

Eq = {<M1>#<M2> | L(M1) = L(M2)}

Diese Eigenschaft der Nicht-semi-entscheidbarkeit folgt leicht daraus, dass das Halteproblem auf dieses Problem und auch auf dessen Komplement reduzierbar ist. Sie gilt allerdings bereits für deterministische Kellerautomaten anstelle von allgemeinen Turingmaschinen.

Allgemein gilt für eine Sprache [math]L[/math] und ihr Komplement [math]K(L)[/math] stets genau eine der folgenden drei Eigenschaften:

  • [math]L[/math] und [math]K(L)[/math] sind rekursiv (und somit auch rekursiv aufzählbar).
  • [math]L[/math] und [math]K(L)[/math] sind nicht rekursiv aufzählbar.
  • Genau eine der Sprachen [math]L[/math] und [math]K(L)[/math] ist rekursiv aufzählbar (aber nicht rekursiv), die andere ist nicht rekursiv aufzählbar.

Abgeschlossenheit

Die Menge der rekursiv aufzählbaren Sprachen ist gegenüber Kleenescher Hüllenbildung, Konkatenation, Schnitt und Vereinigung abgeschlossen, nicht jedoch gegenüber dem Komplement[1].

Beweise (skizzenhaft)

Konkatenation

Gegeben die Sprachen [math]L_1, L_2[/math] betrachten wir die Aufzählfunktionen [math]f_1[/math] und [math]f_2[/math], welche jeweils turingberechenbar sind. Wir setzen [math]f(i,j) = f_1(i) \cdot f_2(j)[/math] und haben damit eine surjektive Abbildung von einer abzählbaren Menge auf alle Konkatenation von einem Wort aus [math]L_1[/math] und einem Wort aus [math]L_2[/math]. Somit haben wir eine Aufzählfunktion für [math]L_1 \cdot L_2[/math]

Schnitt

Für die Sprachen [math]L_1[/math] und [math]L_2[/math] existiert jeweils eine Akzeptor-Turingmaschine. Wir konstruieren eine Turingmaschine, welche zuerst [math]L_1[/math], und dann [math]L_2[/math] simuliert. Diese hält für eine Eingabe genau dann, wenn diese Eingabe im Schnitt von [math]L_1[/math] und [math]L_2[/math] liegt.

Einzelnachweise

  1. Uwe Schöning: Theoretische Informatik – kurzgefasst. 5. Auflage. Spektrum, Heidelberg u. a. 2008, ISBN 978-3-8274-1824-1, (Spektrum-Hochschultaschenbuch), S. 81.

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Rekursiv aufzählbare 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.