Формальная грамматика

[Pixar]

Надо построить магазинный автомат для языка: $L = \{a^nb^{2n+m}a^{m-1} | n,m\geqslant 1\}$
По правилам надо бы предложить свои действия, но я в ступоре. Мне очень трудно сообразить, какие состояния и какие переходы должны быть у автомата.
Ну, первое, что я могу предположить - это то, что на первом состоянии накручивается символ $a$, записываясь в стек. Дальше, нужно, как мне кажется, стирать из стека символ $a$, заменяя его $b$. Тут я уже не уверен. Дальше - хуже. Не представляю, как сосчитать $a^{m-1}$ на конце...

[Pixar]

Меня внезапно осенило, и я сотворил вот такую штуку:


Поясняю:
$q_0$ состояние служит для записи количества входных $a^n$ символов, но так как $b$ зависит от $a$ таким образом - $b^{2n}$-, следовательно в стек надо записывать по 2-а символа, чтобы при следующем проходе $b$ занулил все символы $a$ в стеке. Таким образом обеспечивается соответствие количества первых символов $a^n$ и зависимого от этого количества $b^{2n}$ символов.
$q_1$ состояние целиком служит для зануления в стеке символов $a$ силами символов $b$. Следовательно, по окончании этого цикла мы избавимся от зависимости $b$ и $a$(который в начале).
Теперь осталось проверить зависимость между $b^m$ и последними $a^{m-1}$. Следующий за состоянием $q_1$ переход соответствует понижению $b^m$ до $b^{m-1}$. Это облегчает дальнейшие действия так, что, после заполнения оставшихся $b^{m-1}$ символов, теперь осталось занулить весь стек, посредством следующих символов $a$ в состоянии $q_3$.
Если их не осталось, то стек должен быть пуст. Тогда входное слово принадлежит данному языку.
Если $a$ ещё остались, то ими надо занулить весь стек из $b$. Это должно получиться, так как в стеке их ровно столько, сколько должно быть символов $a$ в конце. Занулив стек, мы увидим дно и не должны больше встречать символов $a$, да и вообще больше символов быть не должно. Только в этом случае слово распознано и, следовательно, принадлежит языку (заключительное состояние $q_4$)

Вот так. Я написал это довольно спонтанно, так как с формальной грамматикой у меня большие проблемы и выстроить всё логично у меня не очень получается. То, что я написал выше - это "отражение" моих мыслей в виде слов, то есть - то, как я понимаю этот автомат :).
Если есть косяки, обязательно напишите! Буду очень признателен.

[Pixar]

Вот построил ещё КС-грамматику:
$\mathbf{S}\to\mathbf{T}b\mathbf{U}$
$\mathbf{T}\to a\mathbf{T}bb$
$\mathbf{T}\to abb$
$\mathbf{U}\to b\mathbf{U}a$
$\mathbf{U}\to ba$

Нормальная форма Хомского:
$\mathbf{S} \to \mathbf{A_{Tb}}\mathbf{U}$
$\mathbf{A_{Tb}} \to \mathbf{T}\mathbf{A_{b}}$
$\mathbf{T} \to \mathbf{A_{aT}}\mathbf{A_{bb}}$
$\mathbf{A_{aT}} \to \mathbf{A_{a}}\mathbf{T}$
$\mathbf{A_{bb}} \to \mathbf{A_{b}}\mathbf{A_{b}}$
$\mathbf{T} \to \mathbf{A_{a}}\mathbf{A_{bb}}$
$\mathbf{U} \to \mathbf{A_{bU}}\mathbf{A_{a}}$
$\mathbf{A_{bU}} \to \mathbf{A_{b}}\mathbf{U}$
$\mathbf{U} \to \mathbf{A_{b}}\mathbf{A_{a}}$
$\mathbf{A_{a}} \to a$
$\mathbf{A_{b}} \to b$

Не получается по формуле в вики: длина формы Хомского $2n-1$, где $n$ - длина исходной грамматики :)

ЗЫ: а почему тему переместили?
ЗЫЫ: как выровнять выражения по стрелочкам?

[arseniiv]

(Оффтоп)

Не знаю, есть ли какой-нибудь специальный для этого в $\TeX$ способ, а можете пока попробовать в следующих сообщениях использовать матрицу с тремя столбцами, во втором — стрелки, слева и справа выражения. Примерно так:

$$\begin{array}{rcl} aaaaaa & \to & b \\ c & \to & ddddd \\ eeee & \to & ffff \end{array}$$

Но думаю, всё же специальный способ есть.