Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2015-H-03

Hauptklausur 2015 / CNF (A3)

Sun, 04 Feb 2018 15:37:51 +0000

Eine Frage zur Aufgabe 3b:

Kann man hier das S-> Lamda auch stehen lassen zur Umformung in die CNF, oder muss das immer genau so gemacht werden wie hier ? Denn ich meine, dass in der Begleitlektüre steht, dass man es nicht machen muss -

Meine Lösung sieht ohne das Lamda zu entfernen ganz anders aus !

Danke !

Beantwortet: Zustand D(0)

Sat, 11 Feb 2017 04:38:55 +0000

In der CNF darf man kein Nonterminalsymbol auf 3 Nonterminalsymbole ableiten. Deswegen der Zwischenschritt über D(0).

Beantwortet: Warum wird nach dem ersten Schritt F->A hinzugefügt?

Fri, 10 Feb 2017 20:47:49 +0000

Hallo,

"lambdafrei machen" bedeutet nicht, einfach nur die lambdas rauszustreichen. Du musst genau schauen, in welchem Zusammenhang lambda auftritt.

In diesem konkreten Beispiel: S -> lambda

Das heißt, dass in jedem Ausdruck, in dem S vorkommt, auch ein lambda abgeleitet werden kann.

So kannst du aus F -> SA über S -> lambda auch F -> A ableiten. Wenn du jetzt das lambda streichst, ist diese Ableitung nichtmehr möglich. Das müsst du beim "lambdafrei machen" berücksichtigen und fügst deshalb F -> A direkt hinzu.

So gehst du für jede Ableitung vor, in der S vorkommt. Das führt z.B. auch zu der Ableitung S -> ab, die man vorher nur als S -> aSb kannte.

Grüße

Beantwortet: CNF 1. Schritt

Sun, 14 Feb 2016 15:07:04 +0000

Hallo ugeil,

die Produktion S´ -> brauchen wir für das leere Wort, was ja Teil dieser Sprache ist. Die Lambda-Übergang ist bei der CNF also nur für das Startsymbol erlaubt. Ansonsten müssen alle anderen Lambda Übergänge, wie du richtig sagst, durch die jeweilige Produktion ersetzt werden

Viele Grüße

Gregor (Tutor)

Beantwortet: CNF erzeugen: Wie geht Schritt 3: Terminale isolieren?

Tue, 09 Feb 2016 10:14:19 +0000

Ja, aber die sind doch schon isoliert. Es geht ja nur darum, dass alle Regeln in CNF sind, und für alle Vorkommen der Terminale $c, \ldots, f$ gilt das schon, weil in all diesen Regeln nur auf diese Terminale abgebildet wird.

Beantwortet: Verständnis Greibach-Normalform HK 15 3d)

Tue, 02 Feb 2016 07:49:25 +0000

Eine $\lambda$-freie Grammatik ist so definiert, dass die Regel $S \rightarrow \lambda$ erlaubt ist, wenn $S$ auf keiner rechten Seite einer Regel vorkommt. Sonst sind aber keine $\lambda$-Regeln erlaubt.

Beantwortet: Ist Regel (S'→λ|S) nicht falsch?

Tue, 22 Sep 2015 12:41:43 +0000

Hallo,

die Regel S => Lambda wird ausnahmsweise zugelassen, wenn S auf keiner rechten Seite einer Regel auftritt. Damit kann das leere Wort Teil der Sprache sein, ohne dass i.A. Wörter während der Ableitung kürzer werden können.

Viele Grüße

Lukas König

EDIT: Rein Formal lässt Herr Schmeck auf den Folien diese Ausnahme bei der CNF allerdings nicht zu. Beachten Sie auch meinen Kommentar weiter unten.