Warum ist C -> Lambda notwendig?

Question

ich verstehen auch nicht, warum ein Lamda am Ende bei C sein muss. Ich dachte das ist nur bei einem * erlaubt.

 

Answer 1

Hallo,

Sie haben recht, dass das lambda hier überflüssig ist, es ist jedoch auch nicht falsch. Nur weil w in {0,1}+ ist heißt das ja nicht, dass nicht auch ein Nonterminalsymbol auf lambda abgebildet werden kann. Dies bedeutet nur, dass L nicht das leere Wort enthält, d.h. dass S->lambda nicht erlaubt wäre (oder S->A | A->lambda). Da aber S->1A|0S|1|0 immer mindestens ein Terminalsymbol erzeugt, erhalten wir mit C->lambda auf keinen Fall ein leeres Wort.

Freundliche Grüße
Friederike Pfeiffer