a): S --> lamda nicht auch kontextsensitiv

Question

Müsste S --> lamda nicht auch kontextsensitiv sein, da S sonst auf keiner rechten Seite mehr auftaucht? Oder darf auch das lamda an sich nicht noch einmal auftreten? (Verhält es sich mit "monoton" in dem Fall genauso?)

Answer 1

Hallo,

hierzu kann ich Ihnen empfehlen sich in den Folien zum 3. Tutorium die Einführungsaufgabe zu Grammatiken anzusehen, dort steht genau aufgelistet welche Regeln für welchen Typ erlaubt sind. Bei Typ-1 Grammatiken ist S--> lambda ausgeschlossen, da dies eine verkürzende Regel ist.

Viele Grüße,

Janina (Tutorin)

 

Comments

Vorlesung Kapitel 4, Folie 4-2:

Ferner darf zusätzlich S --> lamda definiert sein; S darf dann aber sonst auf keiner rechten Seite auftreten.

Gilt das nicht?

---

Hallo,

der Vorlesungsaufschrieb gilt natürlich. S-> \( \lambda\) ist also erlaubt, allerdings nur, weil P vollständig in der Tabelle angegeben ist. Würde man jede Zeile gesondert als Bestandteil einer nicht vollständig angegebenen Produktionsmenge betrachten müsste man allerdings garantieren können, dass S auf keiner rechten Seite auftaucht, was man dann allerdings nicht kann.

Gruß, Alexander (Tutor)

---

Alles klar, danke!

Gilt das dann nur für kontextsensitiv oder auch für monoton?

Wäre S --> lamda in dem Fall also kontextsensitiv und monoton oder nur kontextsensitiv?

Und ist die Musterlösung für S --> lamda dann falsch?

---

Hallo,

in Foliensatz 4 Folie 4-3 steht, dass

"Eine Chomsky-Grammatik heißt monoton, wenn abgesehen von S → λ nur [nichtverkürzende Regeln] existieren."

Also sollten meiner Meinung nach beide Felder markiert sein, sofern natürlich die komplette Produktionsmenge P gegeben ist.

Gruß, Alexander (Tutor)