Wie gleichzeitig Typ 0 und Typ 3 Grammatik für "selbe Sprache"?

Question

Hallo, ich habe eine Frage:

In der oben genannten Klausur im Aufgabenteil 3c) finden wir heraus, dass weil wir den regulären Ausdruck formuliert haben, die Grammatik vom Typ 3 ist. Jedoch haben wir davor im Teil a) wegen der letzten Produktion herausgefunden, dass es eine Typ 0 Grammatik ist.

Jetzt bin ich etwas verwirrt. Beide Grammatiken stellen ja die gleiche Sprache dar. Heißt das, dass es für die gleiche Sprache verschiedene Grammatik-Typen gibt?

Besten Dank!

Answer 1

Hallo ueyfv,

einzelne Sprachen können mithilfe unterschiedlicher Grammatiken beschrieben werden (als Beispiel kannst du im Tut 1 Nr.1b) schauen). Die Regelmenge unterscheidet sich dabei etwas, wie hier bei der Aufgabe.
Welche Sprache da beschrieben wird, muss nicht unbedingt davon abhängen bzw. es gibt unterschiedliche Ansätze, wie man sie beschreiben kann.
Und eine Sprache vom Typ 3 ist automatisch auch eine Sprache vom Typ 0, da es nur mehr Einschränkungen gibt.

Aber man kann nicht jede Sprache vom Typ 0 auch als z.B. rechtslineare Sprache schreiben, also die Grammatik von Typ 0 ist deutlich Mächtiger als die Grammatik Typ 3 (und auch als 2 oder 1).

Falls noch etwas unklar ist, kannst du gerne noch einmal nachfragen