Доказательство от противного.Предположим, что язык не зависит от контекста.Тогда, по накачанной лемме для контекстно-свободных языков, любая строка в L может быть записана как uvxyz, где | vxy |
0 и для всех натуральных чисел k, u (v ^ k) x (y ^ k) z также есть в языке.Выберите 0 ^ m, где m - любое простое число> p.Тогда мы должны быть в состоянии написать 0 ^ m как uvxyz так, чтобы | vy |> 0. Пусть | vy |= г.Тогда 0 ^ (m-r + kr) должно быть простым для любого натурального числа k.Однако выбор k = m + 1 дает m-r + (m + 1) r = m - r + mr + r = m (1 + r), что не может быть простым, противоречие.Поэтому наше предположение о том, что язык не зависит от контекста, опровергнуто.