---

Geschrieben von flamigo am 13.07.2016 um 21:29:

  kotextsensitive Grammatik für a^2^n

Meine Frage:
Hallo zusammen,

kann mir jemand bei der folgenden Aufgabe weiterhelfen:

Geben Sie eine kontextsensitive Grammatik an, die die Sprache L = {a^2^n | n >= 0} erzeugt.

Meine Ideen:
Die erzeugten Wörter sind a, aa, aaaa = a^4 , a^8 usw.
Grammatik G = ({a}, N, S, P).
P = { S -> A | aa | a,
A -> ....

---

Geschrieben von eulerscheZahl am 14.07.2016 um 07:15:

 

S -> a | AaB
Aa -> C | AA
Ca -> aaC
CB -> B
B -> epsilon

Die Erklärung lasse ich bewusst weg - du musst ja auch noch was tun

---

Geschrieben von flamigo am 14.07.2016 um 12:14:

 

Danke für die Hilfe. Allerdings ist irgendwo ein Fehler.
S => AaB => CB => B => epsilon
oder
S => AaB => AAB => AA
mehr ist nicht möglich. Oder übersehe ich was?

Folgendes müsste aber stimmen:

S -> AB | a,
A -> CA | a,
Ca -> aaC,
CB -> BB, zwei B, damit es kontextsensitiv ist
B -> epsilon

zweiter Aufgabenteil war irgendeine Grammatik mit nur 4 Regeln zu finden.
S -> ASB | a,
Aa -> aaA,
AB -> epsilon

Richtig?

---

Geschrieben von eulerscheZahl am 15.07.2016 um 11:32:

 

Ja, meine Grammatik ist falsch.
Aa -> Ca | AAa - so sollte es passen.

Aber deine Ansätzen sehen auch gut aus, habe es eben durchgespielt.

---

Geschrieben von flamigo am 15.07.2016 um 18:13:

 

Alles klar, danke.