 Chomsky-Hierarchie - Endlichkeit, Entscheidbarkeit |
dieAnna
Grünschnabel
Dabei seit: 30.01.2011
Beiträge: 5
 |
|
| 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:27 |
|
|
dieAnna
Grünschnabel
Dabei seit: 30.01.2011
Beiträge: 5
|
|
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?
|
|
|
01.02.2011 19:29 |
|
|
|
