Zusammenhang von monotonen und kontextsensitiven Grammatiken

Question

Habe ich das richtig verstanden?

Für jede einzelne Ableitung in meiner Grammatik muss nach dieser Aufgabenstellung gelten, dass sie ENTWEDER kontextsensitiv ODER monoton ist, denn auch mir sind hier Elemente aufgefallen, die in beiden Varianten nicht erlaubt wären.

Z.B. wie oben schonmal erwähnt die Vertauschungen von Nonterminalsymbolen als nicht kontextsensitiv und die Ableitung von S' --> lambda als nicht monoton.

Heißt das nun, dass man z.B. bei der Ableitung S'--> lambda zwar weiß, dass sie nicht monoton ist, sie aber mithilfe der kontextsensitiven "lambda-Ausnahmeregel" "aufgefangen" hat?

Danke euch für die Antwort!

Answer 1

Hallo,

Wie im Tutorium 3 besprochen (S.13) kannst du schon sehen, dass deine Aussage "entweder kontextsensitiv oder monoton", nicht stimmen kann, denn eine kontextsensitive Grammatik ist immer monoton, eine monotone Grammatik ist allerdings nicht immer kontextsensitiv, kann allerdings dazu umgewandelt werden.

Wie du aus den Vorlesungsfolien (Kap.4, 3. Folie) unschwer erkennen kannst, darf man auch bei monotonen Grammatiken als einzige Ausnahme S->Lambda abbilden, insofern du S nicht nocheinmal aufrufen kannst (hier wurde S' genommen, aber wie du siehst kannst du S' nicht auf S' abbilden).

Somit ist die in den Lösungen beschriebene Grammatik eine monotone Grammatik, denn (Faustregel:)"Die rechte seite ist nie kürzer als die Linke" (Vertauschungen bleiben ja gleichlang, sind also nicht kürzer). Der Ausnahmefall dass gleich zu Beginn bei S' auf Lambda abgebildet wird existiert und ist legitim.

Ich hoffe ich konnte dir weiterhelfen,

Viele Grüße,

Marc (Tutor)

 

Comments

Danke für Ihre ausführliche Antwort. Eine Frage habe ich allerdings noch dazu: Wieso wird in AU-3 Aufgabe 3b) gesagt, dass genau diese Regel weder kontextsensitiv, noch monoton ist?

---

Hey,

das hat mich auch erst verwirrt, hier geht es darum dass du nur einen Ausschnitt einer Grammatik betrachtest. Du weißt also nicht ob S nicht noch irgendwo rechts steht und kannst deshalb nicht davon ausgehen, dass es das nicht tut. Und das ist ja die Voraussetzung dafür, dass die Regel (ausnahmsweise) erlaubt ist.

Hoffe das hilft noch und: viel Erfolg!
Elisabeth (Tutor)