Мы докажем, что этот язык не является контекстно-свободным, используя лемму прокачки для контекстно-свободных языков. Предположим, что язык не зависит от контекста. Тогда, используя накачанную лемму для контекстно-свободных языков, любое слово w в языке может быть написано w = uvxyz, где выполняется следующее:
- | Уха | <= p </li>
- | уу | > 0
- для любого натурального числа k, u (v ^ k) x (y ^ k) z также на языке
Рассмотрим строку (a ^ p) (b ^ 1.5p) (a ^ p) (b ^ 1.5p) (a ^ p) в языке (она имеет то же число a, что и b, и она такая же вперед как назад). Существуют различные случаи для подстроки vxy:
- vxy полностью состоит из первого сегмента. В результате этой операции получается строка, которая не может быть палиндромом, поскольку первый и последний сегменты a больше не могут иметь одинаковую длину.
- vxy состоит из a и b из первых двух сегментов. Накачка изменяет первые два, но не последние два сегмента, поэтому она не может производить палиндром.
- vxy состоит из b из второго сегмента. В результате этого получается строка, которая не может быть палиндромом.
- vxy состоит из b из второго сегмента и a из середины. Опять же, это не может привести к палиндрому, поскольку вы получаете меньше b слева, чем справа.
- vxy состоит только из середины. результат откачки вполне может быть палиндромом, но он не может теперь иметь равные числа как a, так и b.
Все остальные случаи совершенно симметричны уже рассмотренным. Это означает, что для vxy нет выбора, так как при прокачке мы получаем строки на языке. Это противоречие, поэтому наше предположение о том, что язык не зависит от контекста, было неверным.
Мы полагались на | vxy | <= p для того, чтобы количество случаев было небольшим, а насос не работал. Если бы мы выбрали средний сегмент a, чтобы иметь длину меньше, чем p - 2, это не сработало бы, так как мы могли бы выбрать v = (b ^ n) (a ^ n) и y = (a ^ n) (b ^ п) и он бы накачал просто отлично. </p>