Используйте лемму о перекачке для контекстно-свободных языков. Хорошей строкой для этого языка является строка (0 ^ p) (1 ^ p) (0 ^ p) (1 ^ p). Лемма о перекачке говорит, что если язык контекстно-свободный, то эту строку можно записать как uvxyz, где | vxy | <= p, | vy | > 0 и для всех натуральных чисел n, u (v ^ n) x (y ^ n) z тоже есть в языке. У нас есть несколько различных случаев:
vy состоит только из ведущих нулей. Прокачка будет означать, что две секции нулей имеют разное количество нулей. Это не сработает
vy состоит из нулей и единиц только из первых двух разделов. Это не работает, потому что либо нули и единицы смешиваются, либо первая половина получает больше или меньше нулей и единиц, чем вторая.
vy состоит из единиц из второй секции. Это не работает по той же причине, что и в случае 1.
vy состоит из единиц из второй секции и нулей из третьей секции. Это не работает по той же причине, что и в случае 2.
vy состоит из нулей из третьей секции. Это не работает по той же причине, что и в случаях 1 и 3.
vy состоит из нулей и единиц из третьей и четвертой секций. Это не работает по той же причине, что и в случаях 2 и 4.
vy состоит из единиц четвертого раздела. Это не работает по той же причине, что и в случаях 1, 3 и 5.
Это все случаи, и ни в одном случае мы не смогли накачать нашу струну (0 ^ p ) (1 ^ p) (0 ^ p) (1 ^ p) в качестве требуемой леммы о накачке мы должны. Следовательно, мы приходим к выводу, что язык не мог быть контекстно-независимым.