Ist diese Grammatik tatsächlich monoton? (Wiederholung)

Question

Leider gab es keine aufklärende Antwort auf die vor drei Tagen gestellte Frage, daher nochmal:

Ist die hier gegebene Grammatik tatsächlich monoton, wie in der Aufgabenstellung angegeben?

Dass S auch auf der rechten Seite steht sollte dabei kein Problem darstellen (entgegen der Regel), da meiner Auffassung nach jede Ableitung von S nach Lambda auf eine Konstellation mit aSBBCCC ins Leere läuft, da nun das erste B nicht mehr in Terminalsymbole überführt werden kann.

Wie wird jetzt aber die Existenz von S -> lambda hinsichtlich der Montonie bewertet bzw. was gilt für diese Veranstaltung?

Streng genommen wäre auch diese Regel nicht monoton, da die Ableitung verkürzt.

Wikipedia beschreibt beides als möglich, abhängig von der Definition.

Während die Vorlesungsfolien diese Regel als Sonderform in der Montonie erlaubt:

Eine Chomsky-Grammatik G = (N, T, P, S) heißt monoton, wenn abgesehen von S -> lambda nur Regeln der Form   j -> y   mit   |j| <= |y|   existieren.

wird im Tutorium 3 Aufgabe 8 b) die Tabelle aus der Klausur 2014-H-03 als Lösung angegeben, wobei die Sonderform S -> lambda bei der Monotonie als verboten gilt.

Liegt das daran, dass in dieser Aufgabe unklar ist, ob sonst noch ein S auf einer rechten Seite stehen könnte?

Sonst stellt dies in meinen Augen einen Widerspruch dar.

Was ist nun die richtige Definition in dieser Lehrveranstaltung, vorausgesetzt, ich irre mich mit dem Widerspruch nicht?

Lg

Answer 1

Die Grammatik in der Klausur ist nicht monoton, Sie haben das richtig erkannt und wir haben bei der Aufgabe missformuliert. 

Allerdings ist die Grammatik fast monoton, in dem Sinne, dass man sie einfach durch Einführung eines neuen Startsymbols in eine monotone Grammatik überführen kann. Uns war damals wichtig, dass nicht von einer allgemeinen Grammatik ausgegangen werden sollte - aber natürlich hätten wir das zusätzliche Startsymbol angeben müssen.

Sie können ja mal selber versuchen, eine entsprechende monotone Grammatik anzugeben - für die Klausur wird selbstverständlich erwartet, dass Sie so etwas können.

Wenn man eine Regel $S \rightarrow \lambda$ isoliert betrachtet, ist diese natürlich nicht monoton, denn Monotonie heißt, dass die Regeln nicht kürzer werden dürfen. Wir erlauben in ansonsten monotonen Grammatiken eine nicht monotone Zusatzregel $S \rightarrow \lambda$, wenn $S$ auf keiner rechten Seite vorkommt - aus dem einzigen Grund, weil sonst $\lambda$ nicht Teil einer monotonen Sprache sein könnte, aber das ist eine Ausnahme und bezieht sich nur auf vollständige Grammatiken.

Comments

Vielen Dank!

Answer 2

Hallo urdsc!

Wenn in den Vorlesungsfolien eine monotone Chomsky-Grammatik wie von dir oben zitiert definiert wird, dann ist passt doch hier alles:  S-> lamda ist damit als Regel erlaubt, solange für alle anderen Regel gilt, dass die rechte Seite mindestens genauso lang ist wie die linke. Das ist hier für die gegebene Grammatik erfüllt, deshalb ist sie nach der Definition aus der Vorlesung monoton!

Bei der Aufgabe aus Tutorium 3 wurden explizit darauf hingewiesen , dass man "die einzelnen Regeln hier unabhängig voneinander betrachten soll". Das heißt nicht als komplette Grammatik, sondern jede Regel für sich. In dem Fall ist S-> lambda natürlich keine monotone Regel, da die Regel verkürzend ist (innerhalb einer monotonen Grammatik ist diese Regel aber eben als Sonderfall erlaubt).

Ich hoffe, das beantwortet deine Frage!

Viele Grüße,
Janine (Tutorin)

Comments

Hallo Janine,

vielen Dank für die schnelle Antwort. Den ersten Teil hätte ich so erwartet und das löst somit auch den Widerspruch.

Allerdings habe ich den Teil zur Tutoriums Aufgabe nicht ganz verstanden. S -> lambda müsste doch auch unabhängig von allen anderen Regeln erlaubt sein, sofern S das Startsymbol ist. Die verkürzende Eigenschaft wird ja hierbei ausgesetzt.
Liegt in dem Fall nicht die Begründung eher in dem mangelnden Wissen über die Existenz des Startsymbols auf der rechten Seite jeder beliebigen anderen Regel?
Lg urdsc

---

Tut mir Leid, aber ich verstehe deine Rückfragen nicht:

" S -> lambda müsste doch auch unabhängig von allen anderen Regeln erlaubt sein, sofern S das Startsymbol ist." => Wo steht denn, dass diese Regel verboten ist? Es werden hier doch nur Eigenschaften von Regeln überprüft?

"Die verkürzende Eigenschaft wird ja hierbei ausgesetzt." =>Was meinst du denn damit? Natürlich handelt es sich bei S -> lambda um eine verkürzende Regel, schließlich überführst du von einem Wort der Länge 1 (S) auf ein Wort der Länge 0 (lambda)

"Liegt in dem Fall nicht die Begründung eher in dem mangelnden Wissen über die Existenz des Startsymbols auf der rechten Seite jeder beliebigen anderen Regel?" =>Nein, wie betont soll man hier die Regel UNABHÄNGIG von einander betrachten. Dh für die Monotonie ganz einfach: rechte Seite immer länger oder gleich lang wie die linke Seite .. ganz egal welche Buchstaben (Startsymbol oder nicht) in der Regel vorkommen

---

Hallo ihr beiden.

Ich verstehe schon was der Kommilitone/die Kommilitonin meint.
In der Vorlesung wird erwähnt, dass die Regel S -> lambda bei kontextsensitivität / monotonie nur erlaubt ist, wenn S außerdem noch auf S' abgebildet wird, sofern S auf einer rechten Seite steht.
Da wir die Regeln unabhängig von einander betrachten sollen, wissen wir also nicht ob S auch auf S' abgebildet wird.

Die Frage des Kommilitonen/der Kommilitonin ist jetzt, ob die Regel S-> lambda nicht erlaubt ist, weil
A) wir nicht wissen, ob S irgendwo auf einer rechten Seite steht,
oder
B) weil S -> lambda eine verkürzung ist und die Grundidee der Monotonie somit doch greift.
Wenn es B sein sollte, dann ist das ein Widerspruch zur Vorlesung und er/sie möchte wissen wie wir es in der Klausur handhaben sollen.

---

Kannst du bitte kurz sagen, in welchem Kapitel und auf welcher Folie das mit dem S' steht? Ich finde es leider gerade nicht ..

---

Kapitel 4 Folie 2 wird erwähnt, dass es nicht auf der rechten seite stehen darf. Auf Folie 7 wird gezeigt, warum L2 eine Teilmenge von L1 ist. Dort wird auch erwähnt, dass man S wenn es auf einer rechten Seite vorkommt auch in S' umwandeln darf und S auf das leere Wort.

---

Ok, vielen Dank fürs Nachschauen!

Also, ich kann es gerne nochmal mit anden Worten versuchen zu erklären, vllt wird es dadurch verständlicher:

1. Allgemein: Monoton und Kontextsensitiv ist nicht dasselbe!! z.B. ist die Regel "AkGtKL -> jjjTZedFFRx"eine Regel vom Typ 0, da sie keine der Vorschriften zur Regelbildung von Typ1, Typ 2 oder Typ 3 Sprachen erfüllt. Sie ist also insbesondere nicht kontextsensitiv (Typ1). Nichts desto trotz ist sie monoton (da linke Seite <= rechte Seite)!! Das bedeutet also, dass nicht jede monotone Grammatik automatisch kontextsensitiv ist (ein anderes Gebenbeispiel wäre AB->BA; ebenfalls monoton, aber nicht kontextsensitiv).

2. Bei Kontextsensitiven Grammatiken ergibt es sich nun aus der Definition (Kap 4, Folie 2), dass alle Regeln monoton sind, da der Kontext erhalten bleibt (also insbesondere nicht kürzer wird) und das A auf ein Psi überführt wird, das ungleich des leeren Wortes ist. Nun will man aber vermeiden, dass alle kontextsensitiven Sprachen automatisch das leere Wort nicht enthalten. Daher ist die Regel S->lambda (obwohl sie nicht monoton ist) sozusagen als "Ausnahmeregel" doch erlaubt. Allerdings muss man dann zusätzlich fordern, dass S auf keiner rechten Seite mehr vorkommt, denn sonst könnte es nachträglich doch zu einer Verkürzung kommen. Betrachte zB. den Fall, dass die Regelmenge besteht aus:
P={S-> ASB | lambda;
      A -> a;
      B -> b}  

Dann könnte man folgende Ableitungfolge bilden:
S => ASB => AB => aB => ab
Hier kommt es also zu einer (bei kontextsensitiven Grammatiken) unzulässigen Verkürzung von ASB nach AB, da in diesem Schritt die Regel "S -> lambda" angewendet werden kann, da S eben nicht nur auf der linken, sondern auch auf der rechten Seite einer Regeldefinition vorkommt.
Dh. wenn die Regel S->lambda angewendet wird, dann nur, um das leere Wort selbst zu erzeugen, dh. die Regel darf nur als aller erster und einziger Ableitungsschritt geschehen, danach ist die Ableitungsfolge beendet.

---

Also ich habe es so verstanden, bzw. gelesen:

Also zu allererst steht auf den Vorlesungsfolien Kap.4 S31, dass Monotone Grammatiken Typ 1 Sprachen sind und nicht monotone, Monotone Grammatiken haben auch regeln und somit sind sie aus dem typ 1 und nicht typ 0

2. Kontextsensitive Grammatiken sind auch Typ 1 wie schon geschrieben. nur dass halt links Kürzer als rechts und kein direktes vertauschen erlaubt ist.

3. Für sowohl Monotone als auch Kontextsensitive Grammatiken sind Verkürzungen nicht erlaubt.

S-->aSb|lambda kann S-->aSb-->ab als Wort ausführen. damit wäre es keine monotone Grammatik mehr.
das lässt sich auf die oben genannte Klausur dann übertragen, und bedeutet, dass es ein Formulierungsfehler sein müsste.

Oder Wo liegt mein Denkfehler?

Die Grammatik ist dennoch eine Typ 0 Sprache.