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

Schöne Ferien!
 

 

CNF 1. Schritt

+1 Punkt
238 Aufrufe
ich dachte, dass lambda-frei machen bedeutet, dass es keine Produktion mehr geben darf, nach der ein Nonterminalsymbol auf lambda abgebildet wird. Wenn die Produktion B -> lambda auftritt, muss die schon mal wegfallen. Zusätzlich muss man jetzt für alle Produktionen, in denen ein B auftaucht, eine zusätzliche neue Produktion einführen, die den Fall abdeckt, dass B das leere Wort ist.

Kann ich so immer vorgehen? und warum muss dann aber auch noch S`-> eingeführt werden am Ende?
Gefragt 14, Feb 2016 in 2015-H-03 von ugeil ugeil Lernwillige(r) (1,170 Punkte)  

Eine Antwort

0 Punkte

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 14, Feb 2016 von uhdzw uhdzw Tutor(in) (102,490 Punkte)  
...