Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Zusammenhang von monotonen und kontextsensitiven Grammatiken

+2 Punkte
65 Aufrufe
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!
Gefragt 22, Sep 2015 in SAA-1-3 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

+1 Punkt

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)

 

Beantwortet 22, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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)
...