A56, Chomsky-Normalfom mit λ?

Question

Guten Abend,

mir erschließt sich leider die Verwendung des λ in der Chomsky-NF nicht. Diese ist ja schließlich unter anderem auch so definiert, dass eben jede kontextfreie Grammatik in der Chomsky-NF (und auch Greibach-NF) dargestellt werden kann, jedoch dann das λ fehlt. 

Wird hier also nicht gegen die λ-Freiheit verstoßen?

Comments

Mir ist noch nicht ganz klar, was Sie wissen möchten. Wir haben $\lambda$-Freiheit immer mit einer Ausnahme definiert, nämlich dass $S \rightarrow \lambda$ existieren darf, wenn $S$ auf keiner rechten Seite vorkommt. Diese Ausnahme voraussetzend lässt sich jede Typ-$i$-Grammatik für die Tpen $1$ bis $3$ $\lambda$-frei im selben Typ darstellen (bei Typ-$0$ bin ich mir gerade nicht ganz sicher). Alternativ könnte man auch sagen, wenn keine Ausnahme erlaubt ist, dass jede Sprache, die nicht $\lambda$ enthält durch eine $\lambda$-freie Grammatik des entsprechenden Typs dargestellt werden kann. Wenn in der CNF das $S \rightarrow \lambda$ also stehenbleibt, wird gegen die strenge Auslegung verstoßen, ja, aber wir gehen in der Vorlesung von der schwächeren Auslegung aus. Die CNF heißt bei uns also $\lambda$-frei, weil bis auf die $S$-Ausnahme keine Ableitungen auf $\lambda$ existieren. Falls das nicht Ihre Frage beantwortet, melden Sie sich bitte nochmal.

---

Guten Abend Herr König,

vielen Dank für Ihre schnelle Antwort. Leider scheinen sich die Definitionen aus Buch und Vorlesung zu widersprechen oder ich übersehe etwas.

In der Vorlesung haben wir λ-Freiheit folgendermaßen definiert:

-Definition: Eine kontextfreie Grammatik G = (N, T, P, S) heißt λ-frei, wenn es in -P keine Regeln der Form A -> λ mit A ∈ N gibt.

Da auch das Startsymbol S ∈ N, dürfte auch S nicht auf λ abbilden. Selbst bei Festlegung eines neuen Startsymbols ist dieses Problem nicht gelöst.

Zumal auch die Chomsky-NF so definiert ist, dass sie für kontextfreie Grammatiken nur zuverlässig existiert, wenn λ aus der Sprache ausgeschlossen wird:

-Zu jeder kontextfreien Grammatik G gibt es eine kontextfreie Grammatik G´ in  -Chomsky-Normalform mit L(G´) = L(G) \ {λ}.

Ist somit eine Abbildung der Form S -> λ zugelassen oder nicht? Mir geht es dabei hauptsächlich um die Handhabung in der Klausur.

Vielen Dank für Ihre Hilfe!

---

Natürlich ist diese Regel zugelassen; wenn ich das sage, können Sie mir ruhig glauben. Auf der CNF-Folie steht das tatsächlich in der strikten Form, aber das ist, wie ich oben erklärt habe, eine mathematische Spitzfindigkeit, mehr nicht. Es geht dabei nur um die Ableitung des leeren Wortes, und in der Praxis wäre es einfach nur unnötig umständlich, mit Grammatiken umgehen zu müssen, die das leere Wort nicht ableiten können. Rein mathematisch kann man es aber eleganter finden, ohne Ausnahmeregel für CNF, GNF, monotone Grammatiken usw. auszukommen. Das ist letztendlich Geschmackssache.

---

Damit wären alle Unklarheiten beseitigt. Vielen Dank!

---

Es ist gut, dass Sie so genau hinschauen - aber an dieser Stelle ist es nicht nötig :-)