Предположим, что язык L = {a ^ nb ^ m: n 0 и для любого натурального числа k x (y ^ k) z также является строкой в L. Рассмотрим строку a ^ pb ^ (p + 1).Эта строка имеет длину не менее p и находится в L. Теперь мы рассмотрим варианты для подстроки y:
- y состоит только из a.Затем мы можем выбрать k> 1, чтобы увеличить число a, чтобы оно было больше числа b, и получить строку, не принадлежащую L.
- y состоит из a и b.Тогда при k> 1 перекачка заставит некоторые a идти после некоторых b, в результате чего строка, которая не может быть в L.
- y, состоит только из b.Затем мы можем выбрать k = p, чтобы было не менее 2p + 1 b, что дает более чем вдвое больше числа b, чем числа a, и, следовательно, строки не в L.
, поскольку онитри способа являются единственными способами выбора подстроки y, нет способа выбрать y так, чтобы условия леммы накачки были выполнены.Это противоречие.Следовательно, предположение о правильности языка должно быть неверным.Отсюда следует, что язык не является регулярным.Доказательством было противоречие / сокращение до абсурда.