53
правки
Изменения
Новая версия
В отличие от [[Построение_по_НКА_эквивалентного_ДКА,_алгоритм_Томпсона|конечных автоматов]], для [[МП-автоматы,_допуск_по_пустому_стеку_и_по_допускающему_состоянию,_эквивалентность|МП-автоматов]] недетерминизм является существенным. [[Детерминированные_автоматы_с_магазинной_памятью|ДМП-автоматы]] распознают строгое подмножество языков, распознаваемых МП-автоматами или КС-грамматиками.
{{Теорема
|statement=Классы языков, задаваемых МП-автоматами и ДМП-автоматами с допуском по допускающему состоянию не совпадают.
|proof=[[Файл:pda_1.png|320px|thumb|right|Автомат <tex>M</tex>]]
Рассмотрим язык <tex>L=\left\{0^n1^n \cup 0^n1^{2n}\right\}</tex>.
Очевидно, что язык <tex>L</tex> является контекстно-свободным. Пусть существует ДМП-автомат с допуском по допускающему состоянию <tex>M</tex>, распознающий его.
В силу детерминированности автомата <tex>(s, z_0, 0^n1^{2n})\vdash^*(q_1, \gamma_1, 1^n)\vdash^*(q_2, \gamma_2, \varepsilon)</tex>, причём <tex>q_1, q_2 \in T</tex>. Рассмотрим также язык <tex>L'=\left\{0^n1^n2^n\right\}</tex>, который, как известно, контекстно-свободным не является. Построим на основе <tex>M</tex> недетерминированный МП-автомат, распознающий <tex>L' \cup L</tex>, который, в свою очередь, тоже не контекстно-свободен. Для начала построим по автомату <tex>M</tex> автомат <tex>M'</tex>, заменив все вхождения символа <tex>1</tex> на символ <tex>2</tex>. Далее объединим автоматы <tex>M</tex> и <tex>M'</tex> в автомат <tex>M''</tex>, соединив допускающие состояния <tex>\varepsilon</tex>-переходами (как показано на картинке).
Автомат <tex>M''</tex> является недетерминированным МП-автоматом, и принимает не контекстно-свободный язык <tex>L' \cup L</tex>.
Полученное противоречие доказывает, что нет ДМП-автомата с допуском по допускающему состоянию, распознающего язык <tex>L</tex>. Но из того, что <tex>L</tex> — контекстно-свободный следует, что есть недетерминированный МП-автомат, распознающий его.
}}
[[Файл:pda_2.png|320px|thumb|right|Автомат <tex>M''</tex>]]
{{Теорема
|statement=Классы языков, задаваемых МП-автоматами и ДМП-автоматами с допуском по допускающему состоянию не совпадают.
|proof=[[Файл:pda_1.png|320px|thumb|right|Автомат <tex>M</tex>]]
Рассмотрим язык <tex>L=\left\{0^n1^n \cup 0^n1^{2n}\right\}</tex>.
Очевидно, что язык <tex>L</tex> является контекстно-свободным. Пусть существует ДМП-автомат с допуском по допускающему состоянию <tex>M</tex>, распознающий его.
В силу детерминированности автомата <tex>(s, z_0, 0^n1^{2n})\vdash^*(q_1, \gamma_1, 1^n)\vdash^*(q_2, \gamma_2, \varepsilon)</tex>, причём <tex>q_1, q_2 \in T</tex>. Рассмотрим также язык <tex>L'=\left\{0^n1^n2^n\right\}</tex>, который, как известно, контекстно-свободным не является. Построим на основе <tex>M</tex> недетерминированный МП-автомат, распознающий <tex>L' \cup L</tex>, который, в свою очередь, тоже не контекстно-свободен. Для начала построим по автомату <tex>M</tex> автомат <tex>M'</tex>, заменив все вхождения символа <tex>1</tex> на символ <tex>2</tex>. Далее объединим автоматы <tex>M</tex> и <tex>M'</tex> в автомат <tex>M''</tex>, соединив допускающие состояния <tex>\varepsilon</tex>-переходами (как показано на картинке).
Автомат <tex>M''</tex> является недетерминированным МП-автоматом, и принимает не контекстно-свободный язык <tex>L' \cup L</tex>.
Полученное противоречие доказывает, что нет ДМП-автомата с допуском по допускающему состоянию, распознающего язык <tex>L</tex>. Но из того, что <tex>L</tex> — контекстно-свободный следует, что есть недетерминированный МП-автомат, распознающий его.
}}
[[Файл:pda_2.png|320px|thumb|right|Автомат <tex>M''</tex>]]
