Насосная лемма гласит:
Если L - обычный язык, то существует натуральное число p, такое, что любая строка w длиной не менее p может быть записана как w = uvx, где | уф | <= p, | v | > 0 и для всех натуральных чисел n, u (v ^ n) x также есть в языке.
Чтобы доказать, что язык не является регулярным с использованием леммы прокачки, нам нужно спроектировать строку w таким образом, что остальная часть утверждения терпит неудачу: то есть, нет допустимых назначений u, v и x.
Наш язык L требует, чтобы число a было таким же, как число b. Самая короткая строка, которая удовлетворяет гипотезе, что длина строки w не меньше p, представляет собой ^ (p / 2) b ^ (p / 2). Мы могли бы угадать это как нашу строку. Если мы это сделаем, у нас есть несколько случаев:
- v полностью состоит из а. Но тогда накачка приведет к другому количеству a и b, поэтому результирующая строка не на языке; противоречие.
- v охватывает a и b. Но тогда перекачка приведет к тому, что a и b будут смешиваться в середине, в то время как наш язык требует, чтобы все a были на первом месте. Это также противоречие.
- v полностью состоит из b. Но тогда мы имеем то же противоречие, что и в случае № 1.
Во всех случаях этот выбор w приводил к противоречию. Это означает, что предположение сработало.
Здесь был более простой выбор: выберите w = a ^ pb ^ p, тогда есть только один случай. Но наш выбор удался. Если бы наш выбор не удался, мы могли бы узнать из этого выбора, что пошло не так и выбрать другого кандидата.