Müsste die GNF nicht λ-frei sein?

Question

Guten Tag zusammen,

in der Lösung steht auf die Frage in welcher Nomalform es ist:

Typ 3 (rechtslinear); die Grammatik ist (wie jede Typ-3-Grammatik) in Greibach-Normalform

Dazu meine Frage: Müsste die GNF nicht λ-frei sein?

Laut Vorlesungsfolien gitl: L(G ́) = L(G) \ {λ} oder würfel ich da etwas durcheinander?

Grüße

 

Answer 1

Hallo,

das ist so nicht richtig. Die GNF darf auf das leere Wort abbilden (vgl. Vorlesungsfolie 3-34). In dieser Vorschrift steht, dass phi ein Element von N* sein muss und N* bedeutet beliebig viele Nonterminalsymbole, da ist die 0 mit dabei.

Die rechtslineare Grammatik darf nicht auf das leere Wort abbilden. Das heißt aber nicht, dass es keine Nonterminale geben darf, die auf das leere Wort abbilden. Wenn du dir die Grammatik noch einmal anschaust merkst du, dass jedes S auf ein Terminal- und ein Nonterminalsymbol abbildet, das leere Wort kann also nicht produziert werden. Eine Vorschrift

S --> lamda 

würde dieser Vorschrift widersprechen und daher wäre das keine rechtslineare Grammatik. Da das leere Wort nicht abgebildet werden kann, ist dieses Kriterium jedoch erfüllt.

Max (Tutor)

 

Comments

Hallo,

bei Max Antwort ist ein bisschen was durcheinander geraten, aber das liegt daran, dass wir uns in der Lösung zur Aufgabe vertan haben.

Erstens dürfen Regeln der GNF NICHT das leere Wort erzeugen, denn es sind Regeln der Form

\( A \rightarrow a\phi \)

Ein Terminal \( a \in T\) muss also immer auf der rechten Seite dabei sein, auch wenn \( \phi \in N^{\star} \) leer ist.

Zweitens sind in rechtslinearen Grammatiken Regeln, die das leere Wort erzeugen, erlaubt. Es ist also genau umgekehrt.

Was die vorangegangene Frage angeht, hat der Fragesteller Recht. Die Aussage müsste sein: "die Grammatik ist FAST in Greibach-Normalform (wie jede Typ-3-Grammatik) - das Lambda müsste aber noch eliminiert werden".

Viele Grüße

Lukas König, Friderike Pfeiffer-Bohnen und Micaela Wünsche