53
правки
Изменения
исправлена вёрстка
{{Теорема
|statement=Классы языков, задаваемых МП-автоматами и ДМП-автоматами с допуском по допускающему состоянию не совпадают.
|proof=[[Файл:pda_1.png|320px|thumb|right|Автомат <tex>M</tex>]][[Файл:pda_2.png|320px|thumb|right|Автомат <tex>M''</tex>]]
Рассмотрим язык <tex>L=\left\{0^n1^n\right\} \cup \left\{0^n1^{2n}\right\}</tex>.
Очевидно, что язык <tex>L</tex> является контекстно-свободным. Пусть существует ДМП-автомат с допуском по допускающему состоянию <tex>M</tex>, распознающий его.
Полученное противоречие доказывает, что нет ДМП-автомата с допуском по допускающему состоянию, распознающего язык <tex>L</tex>. Но из того, что <tex>L</tex> — контекстно-свободный следует, что есть недетерминированный МП-автомат, распознающий его.
}}
