a): Typ 1 Grammatik - monoton und kontextsensitiv?

Question

Meine Frage (bezieht sich auf Aufgabenteil a) ) ist nun, ob eine monotone Grammatik vom Typ 1 ist oder ob eine Typ 1 Grammatik monoton und kontextsensitiv sein muss und deshalb die in der Aufgabenstellung beschriebene Grammatik nicht vom Typ 1 ist, da sie nur monoton aber nicht kontextsensitiv ist?

Answer 1

Hallo,

hier eine kurze Korrektur von unserer Seite:

Jede kontextsensitive Grammatik ist monoton, aber nicht jede monotone Grammatik ist kontextsensitiv. Jedoch ist es genau so, wie Tobias geschrieben hat, jede monotone Grammatik kann auch in eine kontextsensitive Grammatik umgewandelt werden.

Viele Grüße

Friederike Pfeiffer-Bohnen, Micaela Wünsche und Lukas König

 

Answer 2

Grundsätzlich: man muss zwischen dem Typ der Grammatik und dem Typ der Sprache unterscheiden, die die Grammatik erzeugt. Eine Grammatik kann von einem allgemeineren Typ sein als die Sprache, die sie erzeugt (man kann die Grammatik komplizierter machen als nötig)

Eine Grammatik vom Typ 1 muss kontextsensitiv sein (aber nicht unbedingt monoton). Eine Grammatik, die "nur" monoton, aber nicht kontextsensitiv ist, ist daher nicht vom Typ 1.

Laut Vorlesungsfolien kann man jedoch jede monotone Grammatik in eine kontextsensitive Grammatik umwandeln, d.h. jede monotone Grammatik erzeugt eine Sprache vom Typ 1.

Gruß,

Tobias (Tutor)