Hallöchen! Ich muss bis nächste Woche verschiedene Aufgaben lösen. Habe bis jetzt alles hinbekommen, aber eine Aufgabe bringt mich ins Grübeln.

Aufgabe: Geben Sie eine Grammatik mit drei Regeln an, welche die Sprache L:={ 1^n : n ist nicht durch 3 teilbar } erzeugt.

G = (N, T, P, S) N = {S, ...} und T = { 1 } mit den Regeln P = { S -> .... }

Naja, theoretisch müsste ich nur die Restklasse von 1 modulo 3 und die Restklasse 2 modulo 3 erzeugen. Also als erstes wird die 1 akzeptiert und dann bräuchte ich eine Regel die im Wechsel erst eine 1 hinzufügt und dann zwei 1-en. Habt Ihr vielleicht einen Tipp?