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

Материал из Викиконспекты
Перейти к: навигация, поиск
Определение:
Определим детерминированный автомат с магазинной памятью, допускающий по пустому стеку (англ. PDA accepting by empty stack), как детерминированный автомат с магазинной памятью, у которого нет множества T допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым.

Определим для него множество допускающих слов N = \{\omega \mid (q_0,a_0,Z_0)\vdash^* (p,\epsilon,\epsilon)\}, где p — произвольное состояние.

Определение:
Язык называется беспрефиксным (англ. prefix-free), если для любой пары слов из этого языка ни одно из этих слов не является префиксом другого.
Теорема:
Язык L допускается ДМП-автоматом, допускающему по пустому стеку тогда и только тогда, когда язык L допускается ДМП-автоматом, допускающему по допускающему состоянию и L — беспрефиксный.
Доказательство:
\triangleright

\Rightarrow

Допустим, что L не беспрефиксный. Тогда \exists \omega_1, \omega_2 \in L : \omega_2 = \omega_1 \alpha. Попробуем допустить слово \omega_2. Тогда автомат остановится сразу после префикса \omega_1, т.к. \omega_1 \in L. Стек будет пустой, однако до конца слова \omega_2 мы не дойдем, поэтому оно не допустится, хотя содержится в L. Получили противоречие, значит L — беспрефиксный.

Построим по заданному ДМП-автомату с допуском по пустому стеку ДМП с допуском по допускающему состоянию.

ДМП1.png
\Leftarrow

Пусть задан ДМП-автомат с допуском по допускающему состоянию, язык L — беспрефиксный. Если автомат в какой-то момент пришел в допускающее состояние, то дальше идти смысла нет, т.к. тогда бы слово, допускаемое этим состоянием было бы префиксом некоторого другого слова. Значит можем удалить все переходы из допускающих состояний и добавить переходы в очистку стека.
ДМП2.png
\triangleleft

[править] Источники информации

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