 Thema: Chomsky-Hierarchie - Endlichkeit, Entscheidbarkeit |
|
|
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?
|
|
| Thema: 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
|
|
| Thema: NEA in DEA umwandeln |
|
|
Oh mist, jetzt hab ich den beitrag gelöscht, weil ich nich gesehen hab, dass du geantwortet hast und es mir inzwischen klar wurde.
vielen dank, trotzdem!
Ach und ich hätt da noch ne andere Frage, zur Automatenminimalisierung:
man stellt ja so eine Tabelle auf (siehe Schöning--> theoretische Informatik - kurzgefasst) in der alle zustandspaare auftauchen.
dann markiert man all die paare, die nen endzustand enthalten.
dann schaut man bei den restlichen nach, wo man landet, wenn man bei beiden (z.b.) ein a liest und checkt dann, ob die beiden zustände, in denen man landet bereits markiert sind. ist dies der fall, markiert man auch das zustandspaar, von dem man ausgegangen ist.
meine frage: wenn mein alphabet aus a und b besteht. muss ich dann von jedem zustandspaar den "test" machen?
Beispiel:
Zu überprüfen: (q1-q2)
Dann prüfe ich (q1, a) = ?
und (q2, a) = ??
Und schau dann, ob (? - ??) bereits markiert ist. falls ja: markiere ich auch (q1 - q2).
FALLS NEIN, versuche ich dasselbe mit "b" oder?
LG, dieANNA
|
|
| Thema: NEA in DEA umwandeln |
|
|
"b: Mit b kommst du von 1 nach 2 aber auch von 2 nach 1. Also muss auch hier eine Schlaufe hin." ---> genau das check ich nicht.
|
|
|
