Beispiel zu Chomsky-Normalform

Question

Hallo zusammen,

ich verstehe leider den ersten Schritt ("Mache G λ-frei") in dem Beispiel zur CNF nicht.

Geg.:     G = ({A.B,C,S}, {a,b}, P, S) mit

              P = { S →λ I C , A → a , B → b , C → AC I CB }

Nach dem ersten Schritt erhält man: 

S → B I AB I λ , A → a , B → a I BAb I ABb I Bb I ABAb .

 

Wie kommt man denn bitte darauf? Danke!

Comments

Hier kann man sehr gut den XWizard zur Veranschaulichung verwenden. Wer das beantwortet, sollte am besten ein oder mehrere passende XWizard-Skripte einbetten.

Answer 1

Hey,

ich vermute du hast die Beispielsgrammatik von Seite 229 als Ausgangsgrammatik angesehen. Auf Seite 230 ist allerdings die unten stehende Grammatik gegeben.
@[17490]@

Diese wird im ersten Schritt Lambda-frei gemacht, wobei die Produktion A -> lambda Probleme bereitet, da das Nonterminalsymbol A auf der rechten Seite auch auftaucht. Deshalb müssen diejenigen Fälle abgedeckt werden wo die Ableitung auf Lambda sich bemerkbar macht. Also wird die Produktion ersetzt durch:

S->B und B->BAb | ABb | Bb.

Wenn du beim XWizard Beispiel auf den Button "Epsilon-frei" klickst erhältst du die gleiche Lösung (allerdings wurde hier auch noch das Startsymbol ersetzt).

 

Ich hoffe ich konnte weiterhelfen.

Beste Grüße Marius Nagel (Tutor)