Изменения

Рассмотрим язык <tex>0^{n}1^{n}2^{n}</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> и получаем, количество символов 1 изменилось, а количество либо <tex>0</tex>, либо <tex>2</tex> осталось тем же. Очевидно, что такое слово не принадлежит рассмотренному языку. Значит, язык <tex>0^{n}1^{n}2^{n}</tex> не является контекстно-свободным.