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

Материал из Викиконспекты
Перейти к: навигация, поиск
(изменены рисунки)
Строка 19: Строка 19:
 
[[Файл:ДМП2.png]]
 
[[Файл:ДМП2.png]]
 
}}
 
}}
 +
 +
==Источники==
 +
*Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд.. : Пер. с англ. — М. : Издательский дом "Вильямс", 2002.

Версия 08:47, 3 декабря 2011

Определение:
Определим детерминированный автомат с магазинной памятью, допускающий по пустому стеку, как детерминированный автомат с магазинной памятью, у которого нет множества [math]T[/math] допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым.

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

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

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

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

ДМП2.png
[math]\triangleleft[/math]

Источники

  • Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд.. : Пер. с англ. — М. : Издательский дом "Вильямс", 2002.