317
правок
Изменения
Нет описания правки
{{Определение
|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''), если для любой пары слов из этого языка ни одно из этих слов не является префиксом другого.
}}
{{Теорема
