Kontextfrei vs Kontextsensitiv

Question

Was ist denn allgemein der Unterschied zwischen einer kontextfreien Sprache (Typ-2) und kontextsensitiven Sprache (Typ-1)?

Bei Typ-1 darf man doch keine lamda-Übergang haben und bei Typ-2 schon, oder?

Aber dann könnte man ja mit einer Typ-1 Sprache die Sprache einfach definieren als mit einer Typ-2 Sprache...? (Zumindest wenn das der einzige Unterschied sein sollte)

 

 

Answer 1

Hallo.

Das ist teilweise richtig. Eine Typ-1-Grammatik heißt auch monotone Grammatik, da die Wörter nicht kürzer werden dürfen. Zudem darf kein λ-Übergang stattfinden, außer S→λ, wenn S sonst auf keiner rechten Seite auftritt. (S kann also nur als erste Regel ausgeführt werden).

Für den zweiten Teil deiner Frage gilt, dass jede Sprache vom Typ i auch vom Typ i-1, für i=1,2,3 ist.

Liebe Grüße,

Leonard (Tutor)