Verständnisfrage zum Ableiten auf Lambda bei Grammatiken

Question

[...]

 

Hierzu dann die Frage, warum geht vergleichsweiße in Aufgabe REC-AB dann die Regel C --> lamda obwohl die Sprache L da auch als "L = { w ∈ {0,1}+ | ...     definiert ist.. also woher weiß ich ob ich auf lamda abbilden darf oder nicht ? das ist mir nicht so ganz klar

Answer 1

Wenn das leere Wort nicht Teil der Sprache sein darf, dann darf man das Startsymbol weder direkt (z.b. S -> lambda) noch indirekt (S->A, A-> lambda) auf lambda abbilden. Das heißt aber nicht, dass man in diesem Fall A nicht auf lambda abbilden darf. In diesem Fall darf es dann nur keine Regel S->A geben. S->1A wäre aber ok, da das Wort dann ja nicht mehr leer sein kann.

Sven (Tutor)