Если L является контекстно-свободным языком, существует длина накачки p такая, что любую строку w ∈ L длины ≥ p можно записать как w = uvxyz , где vy ≠ ε , | vxy | ≤ p , и для всех i ≥ 0 uv i xy i z ∈ L.
Применение насосной леммы
Насосная лемма используется для проверки, является ли грамматика контекстно-свободной или нет. Давайте возьмем пример и покажем, как он проверен.
проблема
Узнайте, является ли язык L = {x n y n z n | n ≥ 1} не зависит от контекста или нет.
Решение
Пусть L не зависит от контекста. Тогда L должна удовлетворять лемме накачки.
Сначала выберите номер n леммы прокачки. Тогда возьмите z в качестве 0 n 1 n 2 n .
Разбить z в uvwxy, где
| VWX | ≤ n и vx ≠ ε.
Следовательно, vwx не может включать в себя как 0, так и 2, поскольку последние 0 и первые 2 расположены на расстоянии не менее (n + 1) позиций. Есть два случая —
Случай 1 — vwx не имеет 2s. Тогда у vx есть только 0 и 1. Тогда uwy , который должен быть в L , имеет n 2s, но меньше, чем n 0s или 1s.
Случай 2 — vwx не имеет нулей.
Здесь возникает противоречие.
Следовательно, L не является контекстно-свободным языком.