Изменения

Рассмотрим язык <tex>L=\left\{0^n1^n\right\} \cup \left\{0^n1^{2n}\right\}</tex>.Очевидно, что язык <tex>L</tex> является контекстно-свободным. Пусть существует <br>Так как множества языков, распознаваемых ДМП-автомат с допуском по допускающему состоянию <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>будем рассматривать в доказательстве ДМП-автомат с допуском по допускающему состоянию.

<br>Пусть существует ДМП-автомат с допуском по допускающему состоянию <tex>M</tex>, распознающий язык <tex>L</tex>.В силу детерминированности автомата <tex>(s, z_0, 0^n1^{n})\vdash^*(q_1, \gamma_1, 1^n)\vdash^*(q_2, \gamma_2, \varepsilon)</tex>, причём <tex>q_1, q_2 \in T</tex>. <br> Рассмотрим также язык <tex>L''=\left\{0^n1^n2^n\right\}</tex>. <br>Построим на основе <tex>M</tex> недетерминированный МП-автомат, распознающий язык :<tex>L' = \left\{0^{n}1^{n}2^{n}\right\} \cup \left\{0^n1^n\right\} \cup \left\{0^n1^{2n}\right\}</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>-переходами (как показано на картинке). <br>