Warum ist dieses eine Typ1-Sprache?

Question

zu Teilaufgabe c):

Kontextfreie Sprachen, also Typ-1-Sprachen, dürfen doch eigentlich den Lambda-Übergang nur als aller ersten Übergang enthalten und sonst nicht.
Warum ist es bei der c) dann trotzdem eine Typ-1-Sprache?

Bei 2010-H-01 a ist es nämlich keine Typ-1-Sprache.

Vielen Dank und liebe Grüße!

 

Answer 1

Hallo,

ersteinmal entsprechen den Typ-1-Sprachen die kontextsensitiven Sprachen. Weiter musst du hier Sprachen und Grammatiken unterscheiden. Da sowohl S als auch Lambda auf der rechten Seite auftreten, kann dies schonmal keine kontextsensitive Grammatik sein. Das heißt aber nicht, dass die Sprache der Grammatik nicht auch kontextsensitiv ist.

Max (Tutor)