Theoretische Informatik - Grammatik

Erste Frage Aufrufe: 347     Aktiv: 29.06.2020 um 23:22

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?

Diese Frage melden
gefragt

Punkte: 10

 

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

  ─   kowa 29.06.2020 um 23:22

Kommentar schreiben

0 Antworten