| aRo |
Kontextsensitive Grammatik finden
Hallo!
Ich möchte eine kontextsensitive Grammatik zu dieser Sprache finden:
![[latex] L = \{ a^{2^k} | k \geq 0 \} [/latex]](http://www.matheboard.de/latex2png/latex2png.php? L = \{ a^{2^k} | k \geq 0 \} )
Schwierigkeiten macht mir vor allem die Bedingung, dass linke Regelseiten höchstens so lang wie rechte Regelseiten sein dürfen.
Hier meine Idee:
S -> VXaH | a
Xa -> aaX
XH -> YH
aY -> Ya
VY -> VX
V -> epsilon
XH->epsilon
Erläuterung:
Die Grammatik basiert auf der Idee, dass ich jedes a, was schon vorhanden ist, verdoppeln muss, "um auf die nächste Stufe zu kommen".
Die Terminalsymbole V,H bezeichnen "Vorne" und "Hinten" im Wort, und sollen dafür sorgen, dass die Grammatik eindeutig ist.
Die Variable X wandert immer von links nach rechts und verdoppelt dabei alle as. Die Variable Y wandert nur zurück, falls man eine Ebene weiter will.
Das Problem ist, dass ich diese beiden Regeln mit Epsilon unten habe und ich dabei eine Bedingung von kontextsensitiven Sprachen verletze.
Jemand eine Idee, wie ich die wegkriege? |
