Автомат с магазинной памятью. МП-автомат

Определение

МП - автоматом называется $M=(Q,\Sigma, Г, \delta, q_0, \gamma_0, F)$, где $Q$ - множество состояний $F$ - множество заключительных состояний $q_0$ - начальное состояние $\Sigma$ - входной алфавит $Г$ - стековый алфавит $\gamma_0$ - начальное содержание стека $\delta(q,B,a)$ - функция переходов

Важная пометка: «B» это не нетерминал. Обяснение: просто она так захотела (я не шучу).

1. перейдёт в состояние $q'$
2. Либо останется на месте(обозначение: $«-»$), либо сдвинуться вправо (обозначение: $«\to»$)
3. Всегда удаляется вершина стека, а потом добавляется цепочка $\gamma$

$[q_0, \varepsilon, a^2b^2]$ $\ \vDash \ [q_0, a, ab^2]$ $\ \vDash \ [q_0, aa, b^2]$ $\ \vDash \ [q, a, b]$ $\ \vDash \ [q, \varepsilon, \dashv]$ $\ \vDash \ [f, \varepsilon, \dashv]$

$q_0$ - состояние $\varepsilon$ - содержание стека $a^2b^2$ - необработанная часть строки

Определение

Конфигурацией МП-автомата называется $[q, B\gamma, au]$, где $q$ - сотояние, $au$ - необработанная часть цепочки, $B\gamma$ - содержание стека

$\delta(a,B,a)$ = $(p, \beta, \to)$ - случай 1

$\delta(a,B,a)$ = $(p, \beta, -)$ - случай 2

Случай 1

$[q, B\gamma, au] \vDash [p, \beta\gamma, u]$

Случай 2

$[q, B\gamma, au] \vDash [p, \beta\gamma, au]$

Определение

МП - автомат распознающий цепочку $w \in \Sigma^* \ [q_0, \gamma_0, w] \vDash^* [f,\gamma, \dashv]$

автомат описанный выше распознаёт слова $a^2b^2$

$L(M)$ - язык, который распознаёт МП-автомат т.е. все слова, которые распознает $M$