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.)

Müsste die GNF nicht λ-frei sein?

+2 Punkte
59 Aufrufe

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

 

Gefragt 21, Sep 2015 in HU-2-4 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte

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)

 

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