Введение
Помповая лемма
В информатике, в частности в теории формальных языков, помповая лемма для контекстно-свободных языков, также известная как лемма Бар-Хиллеля, — это лемма, которая описывает свойство, общее для всех контекстно-свободных языков, и обобщает помповую лемму для регулярных языков. Помповая лемма может быть использована для построения доказательства от противного, показывающего, что конкретный язык не является контекстно-свободным. Обратно, помповой леммы недостаточно для гарантии того, что язык является контекстно-свободным; существуют другие необходимые условия, такие как лемма Огдена или лемма обмена.
In computer science, in particular in formal language theory, the pumping lemma for context free languages, also known as the Bar Hillel lemma, is a lemma that gives a property shared by all context free languages and generalizes the pumping lemma for regular languages. The pumping lemma can be used to construct a proof by contradiction that a specific language is not context free. Conversely, the pumping lemma does not suffice to guarantee that a language is context free; there are other necessary conditions, such as Ogden's lemma, or the Interchange lemma.
Неофициальное заявление и объяснение
Лемма о выкачивании для контекстно-свободных языков (далее в этой статье называемая просто "леммой о выкачивании") описывает свойство, которое гарантированно присуще всем контекстно-свободным языкам. Это свойство относится ко всем строкам в языке, длина которых не меньше , где – константа, называемая длиной выкачивания, которая различается для разных контекстно-свободных языков. Пусть – строка длиной не меньше , принадлежащая данному языку. Лемма о выкачивании утверждает, что строку можно разбить на пять подстрок , где не пуста, а длина не превышает , так что многократное повторение и одинаковое количество раз в приводит к строке, которая также принадлежит этому языку. Часто бывает полезно повторить ноль раз, что эквивалентно удалению и из строки. Этот процесс "выкачивания" дополнительными копиями и послужил названием для леммы о выкачивании. Конечные языки (которые являются регулярными и, следовательно, контекстно-свободными) тривиально удовлетворяют лемме о выкачивании, поскольку равна максимальной длине строки в этом языке плюс один. Поскольку строк такой длины не существует, лемма о выкачивании не нарушается.