Theoretische Informatik - Grammatik


0

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?

 

gefragt vor 2 Wochen, 4 Tage
k
kowa,
Punkte: 10
 

Für alle, die die Antwort benötigen. P = { S -> 111S | 11 | 1 }

  -   kowa, kommentiert vor 1 Woche, 6 Tage
Kommentar schreiben Diese Frage melden
0 Antworten