Грамматика, которая генерирует язык а ^ я ^2?

Question

Может ли anybode показать, какие производственные правила необходимы для построения грамматики языка

Можно ли это описать грамматикой?

РЕДАКТИРОВАТЬ:

Это похоже, но вид "более слабой" грамматики, так как вы не делаете полномочия, а умножаете на 2.

Это контекстно-зависимая грамматика, я не записал все правила, но идея имеет форму:

Вы умножаете X на Y, а затем удаляете Y на левой стороне. Я подумал, что, возможно, с помощью сил вы можете сгенерировать Y, идущий направо, а затем сгенерировать окончательный X, возвращающийся направо, но я думаю, что это не работает

Есть ли у вас какие-либо идеи?

Answer 1

Я нашел следующий ответ здесь: http://www.mersenneforum.org/showthread.php?t=11676

S→LAYR 
ZA→aAZ 
Za→aZ
ZR→AAYR 
aY→Ya 
AY→YA 
LY→LZ 
YR→X 
aX→Xa 
AX→Xa 
LX→ε 

Поскольку n^2 =\sum_{i=1}^{n} (2i-1), в любом случае, для n = i, мы имеем (i-1)^2 A и (2i-1) a. При n=i+1 все А конвертируются в А и продолжаются.

Хотя я не проверил это полностью.