Grammatik L1

Question

Frage zu der Grammatik von L1: der Stern nach der Mengenklammer in der Beschreibung der Sprache bedeutet ja, dass das leere Wort auch mit der Grammatik produziert werden kann oder? Müsste dann nicht der erste Punkt S -> 0B/1A/lambda heißen? Im moment kann man sonst nicht das leere Wort generieren oder habe ich da etwas übersehen? Würde man den ersten Punkt der Produktion allerdings durch lambda erweitern könnte man folgende Schritte machen:

S -> 1A -> 11S -> 11 was eine gerade Anzahl an 1er erhält.

vielleicht stehe ich auch nur auf dem Schlauch ;)

 

Answer 1

Das leere Wort ist nicht erlaubt, da es null Einsen hätte und null ist eine gerade Zahl. Der blöde Stern ist hier also nur Verwirrung. Du kannst auch in Mathe schreiben N mit 0, und dann wieder die 0 ausschließen.