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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

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

Автомат с магазинной памятью (автомат со стеком, англ. pushdown automaton) — это набор [math]A=\langle\Sigma,\Gamma,Q,s\in Q, T \subset Q, z_0 \in \Gamma, \delta : Q \times \Sigma \cup \{\varepsilon\} \times \Gamma \rightarrow 2^{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]c_i[/math] — текущий считываемый символ). Символ [math]x[/math] снимается с вершины стека. Вместо него помещается строка [math]\alpha[/math] таким образом, чтобы первый символ строки находился на вершине стека.

Обычно под автоматом со стеком подразумевается недетерминированный автомат. Заметим, что недетерминированные автоматы со стеком эквивалентны по выразительной мощности контекстно свободным грамматикам. Если речь пойдет о детерминированном автомате, это будет указано отдельно. Заметим также, что детерминированные и недетерминированные автоматы со стеком неэквивалентны.

Диаграммы переходов

Рис. 2. Переход: с — символ, прочитанный с ленты; A — символ, вынутый из стека; [math]\alpha[/math] — строка, помещаемая в стек.

Рис. 3. Переход по любому стековому символу, он же возвращается в стек.

Рис. 4. Переход по любому стековому символу, в стек кладется пустая строка.

По соглашению маркер дна всегда находится на дне (за исключением случая, когда автомат является автоматом с допуском по пустому стеку). То есть, для [math]\forall q \in Q,\forall c \in \Sigma \cup \{\varepsilon\} \Rightarrow \delta(q, c, z_0) \ni \langle p, \alpha \rangle [/math], где [math]p \in Q, \alpha \in \Gamma^*, \alpha = \alpha_1z_0[/math].

Основные определения

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

Мгновенное описание (англ. instantaneous descriptions) — это набор [math]\langle q, \alpha, \gamma \rangle[/math], где [math]q[/math] — текущее состояние, [math]\alpha[/math] — остаток строки, [math]\gamma[/math] — содержимое стека.

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

Переход за один шаг (англ. the "goes-to" relation) обозначается как [math]\langle q, \alpha, \gamma \rangle \vdash \langle r, \beta, \xi \rangle[/math], где [math]\alpha = c\beta[/math] (возможно, [math]c=\varepsilon[/math]), [math]\gamma = \chi\gamma', \xi = \eta\gamma'[/math], [math]\langle r, \eta \rangle \in \delta(q, c, \chi)[/math].

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

Язык автомата с магазинной памятью (англ. language of a pushdown automaton) [math]L(A)=\{\alpha \mid \langle s, \alpha, z_0\rangle \vdash^* \langle t, \varepsilon, \gamma \rangle, t \in T\}[/math].

Пример недетерминированного МП-автомата

Рис. 5. Недетерминированный МП-автомат для языка [math]0^n1^n[/math].

См. также

• Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
• ДМП-автоматы и неоднозначность

Источники информации

• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)