Informatiker Board | Druckvorschau: Chomsky-Hierarchie - Endlichkeit, Entscheidbarkeit

Geschrieben von dieAnna am 01.02.2011 um 19:27:

Chomsky-Hierarchie - Endlichkeit, Entscheidbarkeit

Hallo,

ich habe jetzt mal folgende Beziehungen aufgestellt:

(statt Typ-0 schreibe ich nur 0, analog 1, 2, 3)

0 --> semientscheidbar = rek. aufzählbar --> es gibt Typ 0 Sprachen, die NICHT entscheidbar sind

Darüber hinaus:
1,2,3 --> entscheidbar

3 --> Komplement semientscheidbar

endlich --> 3 --> 2 --> 1 --> 0

So. Meine erste Frage lautet: stimmen diese Beziehungen.
Meine zweite lautet:
Gibt es endliche Sprachen, die NICHT Typ 2 sind? Sprich: gibt es endliche Sprachen, die Typ-0 oder Typ-1 sind?

Über eine Antwort und im besten Fall noch eine Erklärung würde ich mich sehr freuen! smile

Viele Grüße,

dieAnna

Geschrieben von dieAnna am 01.02.2011 um 19:29:

Wenn die Behauptung nämlich stimmt: endlich -> 3, dann heißt das ja, dass jede endliche Sprache regulär sein muss! Oder?

Also gibt es KEINE endliche Sprache, die NICHT kontextsensitiv ist. Denn regulär impliziert ja kontextsensitiv.

Das darf ich so folgern oder?