Diskussion:Rekursive Sprache

Einleitungssatz

Hallo, wie wärs mit einem Einführungssatz (Lead), wo auch mir wenigstens erklärt wird, um was es übersichtsweise geht? Einschätzung, was bedeutet es, woher kommt es? Müsste doch für so Superspezialisten kein Problem sein, oder? --Diftong 17:44, 20. Nov 2003 (CET)

Fehler in Beschreibung?

Hi,

kann ja sein, das ich das Thema nicht voellig verstanden habe, aber widerspricht der Text:

"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",

nicht der Aussage:

" Alle rekursiven Sprachen sind deshalb auch rekursiv aufzählbar" unter Rekursiv aufzählbare Sprache?

(Und letzteres ist denke ich definitiv richtig!)

Also muesste doch eigentlich die Menge der rekursiv-aufzaehlbaren Sprachen eine echte Teilmenge der rekursiven Sprachen sein und nicht wie hier beschrieben umgekehrt, oder?!

Um Erlaueterung wird gebeten.

MfG, MadDy

---

Hallo MadDy,

nein, die Beschreibung hier ist korrekt. Alle rekursiven Sprachen liegen in der Menge der rekursiv aufzählbaren Sprachen (bzw. in deren Sprachklasse). Das bedeutet ja nichts Anderes als "alle Elemente von REC (rekursive Sprachen) sind Element von RE (rekursiv aufzählbare Sprachen)" und somit REC ist eine Teilmenge von RE. Das entspricht auch wieder der Aussage "alle rekursiven Sprachen sind rekursiv aufzählbar".

Insofern sind die beiden oben genannten Aussagen bezüglich dieses Punktes äquivalent.

MfG, --92.224.253.100 18:47, 10. Jan. 2010 (CET)

Fehler in der Definition?

Hallo, muss es gleich am Anfang statt "die immer hält und Eingaben $w\in \Sigma$ genau dann akzeptiert" nicht eher "$w\in \Sigma ^{*}$" heißen?

--Dondon 16:02, 2. Jan 2006 (CET)

Erledigt. (Das sich so ein Fehler so lange hält? Hmm..) Gruss, --87.123.50.11 11:38, 29. Okt. 2006 (CET)

GOTO -und While berechenbar?

ich dachte da die rekursiven Sprachen eine echte Teilmenge der rekursiv aufzählbaren Sprachen ist (welche äquivalent zu den goto und loop berechenbaren Sprachen ist) kann die rekursive Sprache doch nicht äquivalenz zu den goto und loop maschinen sein? (nicht signierter Beitrag von 95.222.240.117 (Diskussion) 11:37, 5. Okt. 2011 (CEST))

Widerspruch?

Zitat >>

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.

<< Zitat Ende

Zweiter Aufzählungspunkt: Wie kann es Sprachen geben, die rekursiv, aber nicht vom Typ 1 sind, wenn nach dem ersten Satz (vor der Aufzählung) die rekursiven Sprachen eine echte Obermenge der Typ 1-Sprachen sind?

Zweiter Punkt: "Es ist kein Automatenmodell bekannt, welches genau die rekursiven Sprachen beschreibt." Äh... doch? Laut Einleitung gibt es ein solches Automatenmodell: Eine Turingmaschine, die auf allen Eingaben w in Sigma* hält und jede Eingabe w in Sigma* genau dann akzeptiert, wenn w in L liegt.

Oder ist mit "Automatenmodell" irgendwas ganz spezielles gemeint? --88.68.126.64 15:57, 6. Dez. 2011 (CET)

Erster Punkt: Ich sehe keinen Widerspruch. Überdenke bitte, was Teilmengen bzw. Teilklassen sind.

Zweiter Punkt: Ich finde den Satz auch widersprüchlich. Vielleicht war gemeint, dass man im Allgemeinen nicht bestimmen kann, ob eine TM zu denen gehört, die für Sigma* immer halten. Es ist also eine vage Teilmenge aller TMs. Den Satz habe ich jedenfalls entfernt.

--Zahnradzacken 21:06, 6. Dez. 2011 (CET)