Лемма о разрастании для автоматных языков

Лемма 3.3.1 (pumping lemma, лемма о разрастании, лемма о накачке, лемма-насос). Пусть L автоматный язык над алфавитом . Тогда найдется такое положительное целое число p, что для любого слова длины не меньше p можно подобрать слова , для которых верно xyz = w, , и для всех .

Доказательство. Пусть язык L распознается конечным автоматом , содержащим только переходы с метками длины единица. Положим p = |Q|. Пусть слово w является меткой успешного пути

и . Согласно принципу Дирихле найдутся такие индексы j и k, что и q_j = q_k(ведь множество индексов содержит p+1 натуральных чисел, а значения q_i берутся из множества, содержащего всего p элементов). Выберем слова x, y и z так, что |x| = j, |y| = k - j и xyz = w.

Пример 3.3.2. Пусть . Рассмотрим автоматный язык

Положим p = 3. Тогда для любого слова длины не меньше p найдутся слова , соответствующие утверждению леммы 3.3.1. Действительно, если w = abu для некоторого слова u, то положим , y = ab, z = u; иначе w = aabu и можно положить x = a, y = ab, z = u.