Детерминированные автоматы с магазинной памятью, допуск по пустому стеку — различия между версиями
(Новая страница: «{{Определение |definition = Определим <b>детерминированный автомат с магазинной памятью, допуска…») |
м (rollbackEdits.php mass rollback) |
||
(не показано 12 промежуточных версий 6 участников) | |||
Строка 1: | Строка 1: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | Определим | + | Определим '''детерминированный автомат с магазинной памятью, допускающий по пустому стеку''' (англ. ''PDA accepting by empty stack''), как [[Детерминированные_автоматы_с_магазинной_памятью|детерминированный автомат с магазинной памятью]], у которого нет множества <tex>T</tex> допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым. |
}} | }} | ||
+ | Определим для него множество допускающих слов <tex>N = \{\omega \mid (q_0,a_0,Z_0)\vdash^* (p,\epsilon,\epsilon)\}</tex>, где <tex>p</tex> {{---}} произвольное состояние. | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | Язык называется | + | Язык называется '''беспрефиксным''' (англ. ''prefix-free''), если для любой пары слов из этого языка ни одно из этих слов не является префиксом другого. |
}} | }} | ||
{{Теорема | {{Теорема | ||
− | |statement=Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по пустому стеку | + | |statement=Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по пустому стеку тогда и только тогда, когда язык <tex>L</tex> допускается ДМП-автоматом, допускающему по допускающему состоянию и <tex>L</tex> {{---}} беспрефиксный. |
|proof= | |proof= | ||
<tex>\Rightarrow</tex><br> | <tex>\Rightarrow</tex><br> | ||
− | Допустим, что <tex>L</tex> не беспрефиксный. Тогда <tex>\exists \omega_1, \omega_2 \in L : \omega_2 = \omega_1 \alpha</tex>. Попробуем допустить слово <tex>\omega_2</tex>. Тогда автомат остановится сразу после префикса <tex>\omega_1</tex>, т.к. <tex>\omega_1 \in L</tex>. Стек будет пустой, однако до конца слова <tex>\omega_2</tex> мы не дойдем, поэтому оно не допустится, хотя содержится в <tex>L</tex>. Получили противоречие, значит <tex>L</tex> {{---}} беспрефиксный. | + | |
− | Построим по заданному ДМП-автомату с допуском по пустому стеку ДМП с допуском по допускающему состоянию.<br> | + | :Допустим, что <tex>L</tex> не беспрефиксный. Тогда <tex>\exists \omega_1, \omega_2 \in L : \omega_2 = \omega_1 \alpha</tex>. Попробуем допустить слово <tex>\omega_2</tex>. Тогда автомат остановится сразу после префикса <tex>\omega_1</tex>, т.к. <tex>\omega_1 \in L</tex>. Стек будет пустой, однако до конца слова <tex>\omega_2</tex> мы не дойдем, поэтому оно не допустится, хотя содержится в <tex>L</tex>. Получили противоречие, значит <tex>L</tex> {{---}} беспрефиксный. |
+ | |||
+ | Построим по заданному ДМП-автомату с допуском по пустому стеку ДМП с допуском по допускающему состоянию.<br> <br> | ||
[[Файл:ДМП1.png]]<br> | [[Файл:ДМП1.png]]<br> | ||
<tex>\Leftarrow</tex><br> | <tex>\Leftarrow</tex><br> | ||
− | + | :Пусть задан ДМП-автомат с допуском по допускающему состоянию, язык <tex>L</tex> {{---}} беспрефиксный. Если автомат в какой-то момент пришел в допускающее состояние, то дальше идти смысла нет, т.к. тогда бы слово, допускаемое этим состоянием было бы префиксом некоторого другого слова. Значит можем удалить все переходы из допускающих состояний и добавить переходы в очистку стека.<br> | |
[[Файл:ДМП2.png]] | [[Файл:ДМП2.png]] | ||
}} | }} | ||
+ | |||
+ | == См. также == | ||
+ | * [[Детерминированные автоматы с магазинной памятью]] | ||
+ | * [[Автоматы с магазинной памятью]] | ||
+ | * [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]] | ||
+ | * [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]] | ||
+ | * [[ДМП-автоматы и неоднозначность]] | ||
+ | |||
+ | ==Источники информации== | ||
+ | * ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. : ISBN 978-5-8459-1347-0 (рус.) | ||
+ | |||
+ | [[Категория: Теория формальных языков]] | ||
+ | [[Категория: Контекстно-свободные грамматики]] | ||
+ | [[Категория: МП-автоматы]] |
Текущая версия на 19:12, 4 сентября 2022
Определение: |
Определим детерминированный автомат с магазинной памятью, допускающий по пустому стеку (англ. PDA accepting by empty stack), как детерминированный автомат с магазинной памятью, у которого нет множества допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым. |
Определим для него множество допускающих слов
, где — произвольное состояние.Определение: |
Язык называется беспрефиксным (англ. prefix-free), если для любой пары слов из этого языка ни одно из этих слов не является префиксом другого. |
См. также
- Детерминированные автоматы с магазинной памятью
- Автоматы с магазинной памятью
- МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
- Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
- ДМП-автоматы и неоднозначность
Источники информации
- Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. : ISBN 978-5-8459-1347-0 (рус.)