Изменения

Определим <b>детерминированный автомат с магазинной памятью, допускающий по пустому стеку</b>, как [[Детерминированные_автоматы_с_магазинной_памятью|детерминированный автомат с магазинной памятью]], у которого нет множества <tex>FT</tex> допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым. Определим для него множество допускающих слов <tex>N = \{\omega | (q_0,a_0,Z_0)\vdash^* (p,\epsilon,\epsilon)\}</tex>, где <tex>p</tex> {{---}} произвольное состояние.

Язык называется <b>беспрефиксным</b>, если для него верно следующее: для любой пары слов из этого языка ни одно из этих слов не является префиксом другого.