Chomsky-Hierarchie - Endlichkeit, Entscheidbarkeit |
| 01.02.2011, 19:27 | Auf diesen Beitrag antworten » |
| dieAnna | 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! 
Viele Grüße, dieAnna |
|
|
|
| 01.02.2011, 19:29 | Auf diesen Beitrag antworten » |
| dieAnna | 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? |
|
|
