Wieso ist Übergang S->Lambda nötig?

Question

Hallo,

ich verstehe hier nicht, warum man im ersten Schritt (frei von Lambda machen), nicht einfach den Übergang S->Lambda weglässt? Muss man das immer so machen, wenn im Startzeichen ein Lambdaübergang ist, um zu gewährleisten, dass das leere Wort zulässig bleibt? Und ist das hier deswegen nicht unbedingt notwendig, weil man Lambda genausogut als übergang von S-> Lambda stehen lassen könnte (wäre dies auch als "lambda freie" lösung zugelassen)?

 

Ich kann das irgendwie nicht aus dem Algorithmus aus S. 3-30 rauslesen, deswegen wollte ich nochmal nachfragen.

 

Vielen Dank schonmal!

 

Answer 1

Hallo,

in diesem Fall wäre das auch in Ordnung. Unsere Vorgehensweise ist aber in dem Fall notwendig, wenn der Startzustand auch auf mind. einer rechten Seite vorkommt - wir müssen dann nämlich gewährleisten, dass zwar das leere Wort erzeugt, aber nicht in einem späteren Schritt abgeleitet werden kann.

Viele Grüße

Lukas König