Лемма о накачке для контекстно-свободных языков

В информатике , в частности в формальной теории языков , лемма о накачке для контекстно-свободных языков , также известная как лемма Бара-Хиллеля ^[1] , представляет собой лемму , которая дает свойство, общее для всех контекстно-свободных языков, и обобщает лемму о накачке . лемма для регулярных языков .

Лемму о накачке можно использовать для построения доказательства от противного того, что конкретный язык не является контекстно-свободным. И наоборот, леммы о накачке недостаточно, чтобы гарантировать, что язык не зависит от контекста; есть и другие необходимые условия, такие как лемма Огдена или лемма об обмене .

Если язык не зависит от контекста, то существует некоторое целое число (называемое «длиной накачки») ^[2] , такое, что каждая строка в нем имеет длину или более символов (т. е. с ) и может быть записана как${\ Displaystyle L}$${\ Displaystyle п \ geq 1}$${\ Displaystyle с}$${\ Displaystyle L}$${\ Displaystyle р}$${\ Displaystyle | с | \ geq р}$

с подстроками и такими, что${\ Displaystyle и, v, ш, х}$${\ Displaystyle у}$

Идея доказательства: если оно достаточно длинное, его дерево вывода относительно грамматики нормальной формы Хомского должно содержать некоторый нетерминал дважды на некотором пути дерева (верхний рисунок). Повторяя часть вывода ⇒...⇒ , получаем вывод для (нижний левый и правый рисунок для и соответственно).${\ Displaystyle с}$ ${\ Displaystyle Н}$${\ Displaystyle п}$${\ Displaystyle Н}$${\ Displaystyle vNx}$${\ Displaystyle уф ^ {п} шх ^ {п} у}$${\ Displaystyle п = 0}$${\ Displaystyle 2}$