57
правок
Изменения
Нет описания правки
{{В разработке}}
==Недетерминированный автомат с магазинной памятью==
По умолчанию будем считать автоматы с магазинной памятью недетерминированными. Если речь пойдет о детерминированном автомате, это будет указано отдельно.
{{Определение
|definition= Автомат с магазинной памятью --- это набор A=<tex>\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</tex><tex>(Q \times \Gamma^*)\rangle</tex>, где
*<tex>\Sigma</tex> --- входной алфавит на ленте;
*<tex>\Gamma</tex> --- стековый алфавит;
==Обозначения==
*'''Мгновенное описание:''' <tex>\langle q, \alpha, \gamma \rangle</tex>, где <tex>q</tex> --- текущее состояние, <tex>\alpha</tex> --- остаток строки, <tex>\gamma</tex> --- содержимое стека.*'''Переход за один шаг:''' <tex>\vdash</tex>*'''Переход за ноль или более шагов:''' <tex>\vdash^*</tex>{{Определение|definition= Язык автомата с магазинной памятью <tex>L(A)=\{\alpha \mid \langle s, \alpha, z_0\rangle \vdash^* \langle t, \varepsilon, \gamma \rangle, t \in T\}</tex>}}
==Пример==
Рассмотрим автомат с магазинной памятью для языка <tex>0^n1^n</tex>.
==Детерминированный автомат с магазинной памятью==
