Грамматика, генерирующая язык a^i^2?

Может anybode показать, какие правила производства необходимы для построения грамматики для языкаГрамматика, генерирующая язык a^i^2?

a^i^2 where^means power of

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

EDIT:

Это похоже, но своего рода «слабее» грамматики, так как вы не делаете силы, но кратные 2.

enter image description here

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

enter image description here

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

Есть ли у вас идеи?

источник

2015-05-02 martinerk0

Вы должны объяснить, что вы подразумеваете под «^». –

Я имел в виду мощность (латексная нотация) @MichaelDyck – martinerk0

По крайней мере, она не может быть описана контекстно-свободной грамматикой (а следовательно, и не регулярной грамматикой), поскольку она не удовлетворяет лемме о перекачке. Я не могу сказать, что для неограниченной грамматики. – Petr

Я нашел следующий ответ здесь: 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→ε 
Поскольку п^2 = \ sum_ {я = 1}^{п} (2i-1), в любом случае, для n = i, имеем (i-1)^2 A's и (2i-1) a. При n = i + 1 все A преобразуются в a, а идет вперед.

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

источник

2015-05-03 12:39:43 Petr

Грамматика, генерирующая язык a^i^2?

ответ

Смежные вопросы