Автоматы с магазинной памятью

Эта статья находится в разработке!

Недетерминированный автомат с магазинной памятью

Определение:

Автомат с магазинной памятью --- это набор [math]\langle\Sigma,\Gamma,Q,s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma \rightarrow \cal P[/math][math](Q \times \Gamma^*)\rangle[/math], где [math]\Sigma[/math] --- входной алфавит на ленте; [math]\Gamma[/math] --- стековый алфавит; [math]Q[/math] --- множество состояний автомата; [math]s[/math] --- стартовое состояние автомата; [math]T[/math] --- множество допускающих состояний автомата; [math]z_0[/math] --- маркер дна стека; [math]\delta[/math] --- функция переходов.

Детерминированный автомат с магазинной памятью

Определение:

Если для автомата с магазинной памятью выполняются следующие условия: [math]\mathcal8 q \in Q, \mathcal8 c \in \Sigma, \mathcal8 X \in \Gamma[/math] [math]\left | \delta(q, c, X)\right | \le 1[/math]; [math]\delta(q,\varepsilon,X) \ne 0 \Rightarrow \mathcal8 c \in \Sigma : \delta(q, c, X) = \varnothing[/math], то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.