Контекстно чувствителна граматика?

[drago]

Нека [tex]a[/tex] e някакъв символ. Разглеждаме езика [tex]L=\{a^n \,\mid \, n\in \mathbb{N},\, n[/tex] е точен квадрат [tex]\}[/tex] , където [tex]a^n[/tex] означава конкатенация от [tex]n[/tex] последователни [tex]a[/tex]-та.
Да се докаже, че:
1) езикът се генерира от някаква контекстно чувствителна граматика.
2) не съществува безконтекстна граматика, която поражда този език.

[drago]

Всъщност, не знам за какво постнах това тук ?
Като гледах някои сходни неща си спомних тази задача, дадена ми навремето, като упражнение, когато бях студент.
Всъщност точка 2) е по-стандартната част. Има стандартен инструмент за доказване, че даден език не се поражда от автоматна граматика или безконтекстна граматика- т.н. pumping lemma, може да я видите в google, едва ли се изучава някъде другаде освен във ФМИ на СУ.
По-творческата част е да се конструира контекстно чувствителна граматика, която поражда езика.