Rekursive Sprache - Recursive language

In Mathematik , Logik und Informatik , eine formale Sprache (eine Reihe von endlichen Folgen von Symbolen aus einem festen genommen Alphabet ) aufgerufen wird rekursiv , wenn es dich um eine rekursive Teilmenge der Menge aller möglichen endlichen Sequenzen über das Alphabet der Sprache. Äquivalent ist eine formale Sprache rekursiv, wenn es eine totale Turing-Maschine gibt (eine Turing-Maschine , die für jede gegebene Eingabe anhält), die eine endliche Folge von Symbolen als Eingabe akzeptiert, wenn sie zur Sprache gehört, und sie ansonsten ablehnt. Rekursive Sprachen werden auch als entscheidbar bezeichnet .

Das Konzept der Entscheidbarkeit kann auf andere Berechnungsmodelle ausgedehnt werden . Man kann zum Beispiel von Sprachen sprechen, die auf einer nichtdeterministischen Turingmaschine entscheidbar sind . Daher ist, wann immer eine Mehrdeutigkeit möglich ist, das Synonym für "rekursive Sprache" Turing-entscheidbare Sprache und nicht einfach entscheidbar .

Die Klasse aller rekursiven Sprachen wird oft mit R bezeichnet , obwohl dieser Name auch für die Klasse RP verwendet wird .

Dieser Sprachtyp war in der Chomsky-Hierarchie von ( Chomsky 1959 ) nicht definiert . Alle rekursiven Sprachen sind auch rekursiv aufzählbar . Alle regulären , kontextfreien und kontextsensitiven Sprachen sind rekursiv.

Definitionen

Es gibt zwei gleichwertige Hauptdefinitionen für das Konzept einer rekursiven Sprache:

1. Eine rekursive formale Sprache ist eine rekursive Teilmenge in der Menge aller möglichen Wörter über dem Alphabet der Sprache .
2. Eine rekursive Sprache ist eine formale Sprache , für die es eine existiert Turing - Maschine , die, wenn sie mit irgendwelchen endlichen Eingang präsentiert Zeichenfolge , hält an und akzeptiert , wenn die Zeichenfolge in der Sprache ist, und stoppt und Spuck anders. Die Turing-Maschine hält immer an: Sie wird als Entscheider bezeichnet und soll die rekursive Sprache entscheiden .

Nach der zweiten Definition kann gezeigt werden , dass jedes Entscheidungsproblem entscheidbar ist, indem man einen Algorithmus dafür aufzeigt, der auf allen Eingaben terminiert. Ein unentscheidbares Problem ist ein Problem, das nicht entscheidbar ist.

Beispiele

Wie oben erwähnt, ist jede kontextsensitive Sprache rekursiv. Ein einfaches Beispiel für eine rekursive Sprache ist also die Menge L={abc, aabbcc, aaabbbccc, ...} ; formeller, das Set

${\displaystyle L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ für einige }}n\geq 1\,\}}$

ist kontextsensitiv und daher rekursiv.

Beispiele für entscheidbare Sprachen, die nicht kontextsensitiv sind, sind schwieriger zu beschreiben. Für ein solches Beispiel ist eine gewisse Vertrautheit mit mathematischer Logik erforderlich: Presburger Arithmetik ist die Theorie erster Ordnung der natürlichen Zahlen mit Addition (aber ohne Multiplikation). Während die Menge wohlgeformter Formeln in der Presburger Arithmetik kontextfrei ist, hat jede deterministische Turingmaschine, die die Menge der wahren Aussagen in der Presburger Arithmetik akzeptiert, eine Laufzeit von mindestens , für eine Konstante c > 0 ( Fischer & Rabin 1974 ). Dabei bezeichnet n die Länge der angegebenen Formel. Da jede kontextsensitive Sprache von einem linear beschränkten Automaten akzeptiert werden kann und ein solcher Automat von einer deterministischen Turingmaschine mit maximaler Laufzeit im ungünstigsten Fall für eine Konstante c simuliert werden kann , ist die Menge der gültigen Formeln in der Presburger Arithmetik nicht kontextsensitiv. Auf der positiven Seite ist bekannt, dass es eine deterministische Turingmaschine gibt, die in der Zeit höchstens dreifach exponentiell in n läuft und die Menge der wahren Formeln in der Presburger Arithmetik bestimmt ( Oppen 1978 ). Dies ist also ein Beispiel für eine Sprache, die entscheidbar, aber nicht kontextsensitiv ist. ${\displaystyle 2^{2^{cn}}}$${\displaystyle c^{n}}$

Verschlusseigenschaften

Rekursiven Sprachen sind geschlossen unter den folgenden Operationen. Das heißt, wenn L und P zwei rekursive Sprachen sind, dann sind auch die folgenden Sprachen rekursiv:

• Der Kleene-Stern ${\displaystyle L^{*}}$
• Das Bild φ(L) unter einem e-freien Homomorphismus φ
• Die Verkettung ${\displaystyle L\circ P}$
• Die Union ${\displaystyle L\cup P}$
• Der Schnittpunkt ${\displaystyle L\cap P}$
• Die Ergänzung von ${\displaystyle L}$
• Der eingestellte Unterschied ${\displaystyle LP}$

Die letzte Eigenschaft ergibt sich aus der Tatsache, dass die Mengendifferenz durch Schnitt und Komplement ausgedrückt werden kann.

Siehe auch

• Rekursiv aufzählbare Sprache
• Rekursion

Verweise

• Michael Sipser (1997). "Entscheidbarkeit" . Einführung in die Rechentheorie . PWS-Publishing. S.  151–170 . ISBN 978-0-534-94728-6.
• Chomsky, Noam (1959). „Über bestimmte formale Eigenschaften von Grammatiken“ . Information und Kontrolle . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .
• Fischer, Michael J. ; Rabin, Michael O. (1974). "Superexponentielle Komplexität der Presburger Arithmetik" . Tagungsband des SIAM-AMS Symposiums in Angewandter Mathematik . 7 : 27–41.
• Oppen, Derek C. (1978). "A 2 ^{2 2 pn} Upper Bound on the Complexity of Presburger Arithmetic" . J. Computer. Syst. Sci . 16 (3): 323–332. doi : 10.1016/0022-0000(78)90021-1 .