Изменения

Рассмотрим язык <tex>L=\left\{0^n1^n \right\} \cup \left\{0^n1^{2n}\right\}</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>L' \cup L = \left\{0^{n}1^{n}2^{n}\right\} \cup \left\{0^n1^n\right\} \cup \left\{0^n1^{2n}\right\}</tex> не является контекстно-свободным. Для фиксированного <tex>n</tex> рассмотрим слово <tex>\omega=0^n 1^n 2^n</tex>. Пусть <tex>\omega</tex> разбили на <tex>u, v, x, которыйy, z</tex> произвольным образом. Так как известно<tex>|vxy|\leqslant n</tex>, то в слове не содержится либо ни одного символа <tex>0</tex>, либо ни одного символа <tex>2</tex>. Для любого такого разбиения выбираем <tex>k=2</tex> и получаем, что количество символов <tex>1</tex> изменилось, а количество либо <tex>0</tex>, либо <tex>2</tex> осталось тем же. Очевидно, что такое слово не принадлежит рассмотренному языку. Значит, язык <tex>L' \cup L</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>-переходами (как показано на картинке).