Verständnis A3 b)

Question

Hallo

ich habe eine Frage zur Aufgabe 3 part b)

Ich verstehe nicht ganz wieso P keine monotone grammatik ist. Muss nur der übergang S->lamda entfernt werden um die Grammatik monoton zu machen ?

 

Vielen Dank im Voraus

Answer 1

Hallo,

 

bei monoten Grammatiken sind keine verkürzenden Regeln erlaubt. Bei G‘_L sind die Regeln A à λ und T à λ aus diesem Grund nicht erlaubt und müssen ersetzt werden.

Da diese beiden Regeln in den Lösungen der Aufgabe ersetzt werden, muss die Regel  S à λ noch hinzugefügt werden. Die Regel Sà λ ist bei monotonen Grammatiken nur dann erlaubt, wenn S auf keiner rechten Seite vorkommt. Diese Regel wird benötigt, da auch das leere Wort in der Sprache L enthalten ist und es somit auch eine Möglichkeit geben muss auf dieses direkt abzuleiten.

Ich hoffe das beantwortet deine Frage.

 

Viele Grüße,

Verena (Tutor)