57
правок
Изменения
Новая страница: «{{В разработке}} ==Недетерминированный автомат с магазинной памятью== {{Определение |definition= А…»
{{В разработке}}
==Недетерминированный автомат с магазинной памятью==
{{Определение
|definition= Автомат с магазинной памятью --- это набор <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>Q</tex> --- множество состояний автомата;
*<tex>s</tex> --- стартовое состояние автомата;
*<tex>T</tex> --- множество допускающих состояний автомата;
*<tex>z_0</tex> --- маркер дна стека;
*<tex>\delta</tex> --- функция переходов.
}}
==Диаграмма переходов==
==Обозначения==
==Пример==
==Детерминированный автомат с магазинной памятью==
{{Определение
|definition=
Если для автомата с магазинной памятью выполняются следующие условия:
#<tex>\mathcal8 q \in Q, \mathcal8 c \in \Sigma, \mathcal8 X \in \Gamma</tex> <tex>\left | \delta(q, c, X)\right | \le 1</tex>;
#<tex>\delta(q,\varepsilon,X) \ne 0 \Rightarrow \mathcal8 c \in \Sigma : \delta(q, c, X) = \varnothing</tex>,
то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.
}}
==Недетерминированный автомат с магазинной памятью==
{{Определение
|definition= Автомат с магазинной памятью --- это набор <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>Q</tex> --- множество состояний автомата;
*<tex>s</tex> --- стартовое состояние автомата;
*<tex>T</tex> --- множество допускающих состояний автомата;
*<tex>z_0</tex> --- маркер дна стека;
*<tex>\delta</tex> --- функция переходов.
}}
==Диаграмма переходов==
==Обозначения==
==Пример==
==Детерминированный автомат с магазинной памятью==
{{Определение
|definition=
Если для автомата с магазинной памятью выполняются следующие условия:
#<tex>\mathcal8 q \in Q, \mathcal8 c \in \Sigma, \mathcal8 X \in \Gamma</tex> <tex>\left | \delta(q, c, X)\right | \le 1</tex>;
#<tex>\delta(q,\varepsilon,X) \ne 0 \Rightarrow \mathcal8 c \in \Sigma : \delta(q, c, X) = \varnothing</tex>,
то поведение автомата всегда определено однозначно и он называется детерминированным автоматом с магазинной памятью.
}}
