Изменения

|proof=Для доказательства леммы воспользуемся [[Лемма о разрастании для КС-грамматик | леммой о накачке для КС-грамматик]]. Для фиксированного <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'</tex> не является контекстно-свободным по лемме о разрастании для КС-грамматик.

Так как множества языков, распознаваемых ДМП-автомат с допуском по допускающему состоянию и ДМП-автомат с допуском по пустому стеку совпадают(см. [[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку | соответствующую теорему]]), будем рассматривать в доказательстве ДМП-автомат с допуском по допускающему состоянию.