1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|definition =
Определим <b>'''детерминированный автомат с магазинной памятью, допускающий по пустому стеку</b>''' (англ. ''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 =
Язык называется <b>'''беспрефиксным</b>''' (англ. ''prefix-free''), если для любой пары слов из этого языка ни одно из этих слов не является префиксом другого.
}}
{{Теорема
[[Файл:ДМП2.png]]
}}
== См. также ==
* [[Детерминированные автоматы с магазинной памятью]]
* [[Автоматы с магазинной памятью]]
* [[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
* [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
* [[ДМП-автоматы и неоднозначность]]
==Источники информации==
