Изменения

Перейти к: навигация, поиск

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

899 байт добавлено, 23:48, 27 октября 2010
Недетерминированный автомат с магазинной памятью
==Недетерминированный автомат с магазинной памятью==
[[Изображение:PDA.png|thumb|left|Рис. 1. Автомат с магазинной памятью]]
На рис. 1 изображен '''автомат с магазинной памятью(автомат со стеком, push down automaton). ''' С ленты последовательно считываются символы входного алфавита (<tex>c_i</tex> --- текущий считываемый символ). Символ <tex>x</tex> снимается с вершины стека. Вместо него помещается строка <tex>\alpha</tex> таким образом, чтобы первый символ строки находился на вершине стека.  Обычно под автоматом со стеком подразумевается недетерминированный автомат. Заметим, что [[Совпадение множества языков МП-автоматов и контекстно-свободных языков|недетерминированные автоматы со стеком эквиваленты по выразительной мощности контекстно свободным грамматикам.]] Если речь пойдет о [[Автоматы с магазинной памятью#Детерминированный автомат с магазинной памятью|детерминированном автомате]], это будет указано отдельно. Заметим также, что [[Детерминированные автоматы с магазинной памятью|детерминированные и недетерминированные автоматы со стеком неэквивалентны.]]
По умолчанию будем считать автоматы с магазинной памятью недетерминированными. Если речь пойдет о детерминированном автомате, то это будет указано отдельно.
{{Определение
|definition= Автомат с магазинной памятью (автомат со стеком, push down automaton) --- это набор 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>\delta</tex> --- функция переходов.
}}
 
==Диаграммы переходов==
<div class="tleft" style="clear:none">[[Файл:Transition1.png|thumb|Рис. 2. Переход: с - символ, прочитанный с ленты; A - символ, вынутый из стека; <tex>\alpha</tex> - строка, помещаемая в стек]]</div>
57
правок

Навигация