35
правок
Изменения
→Эквивалентность автоматов
*'''Доказательство:'''<tex>\Leftarrow</tex> Исходя из МП-автомата <tex>\mathcal{P}_{T}</tex>, допускающего язык <tex>L</tex> по пустому стеку, построим МП-автомат <tex>\mathcal{P_{N}}</tex>, допускающий <tex>L</tex> по заключительному состоянию.
[[Файл:EqualAllowAutomataPict.png|left]]
'''1.''' Добавим новый символ <tex>Z_1</tex>, не принадлежащий <tex>\Gamma</tex>, который будем маркером дна магазина нового автомата, позволяющий узнать, когда <tex>\mathcal{P_{N}}</tex> опустошает свой магазин. Если построенный автомат <tex>\mathcal{P}_{T}</tex> видит на вершине стека свой маркер, то он знает, что <tex>\mathcal{P_{N}}</tex> опустошает свой магазин на этом же входе.
'''2.''' Добавим новое допускающее состояние <tex>p</tex>, в которое автомат переходит, как только обнаруживает, что <tex>\mathcal{P_{N}}</tex> опустошил свой магазин. Таким образом допущенное слово по пустому стеку, будет допускаться и по заключительному состоянию, используя <tex>\varepsilon</tex> переходы в новое состояние.
'''3.''' Каждый переход <tex>\mathcal{P_{N}}</tex> есть и у автомата <tex>\mathcal{P}_{T}</tex>. Тогда, согласно введенным начальному и заключительному состоянию, автомат <tex>\mathcal{P}_{T}</tex> может совершить следующие действия: <tex>(s, w, Z_{1})\vdash (s_{0}, w, Z_{0} Z_{1})\vdash (q, \varepsilon, Z_{1})\vdash (p, \varepsilon,Z_{1}) </tex>, что означает <tex>\mathcal{P}_{T}</tex> допускает слово <tex>w</tex> по заключительному состоянию <tex>p</tex>.
</font>
