Лемма о накачке ( лемма о разрастании , лемма-насос ; англ. pumping lemma ) — важное утверждение теории автоматов , позволяющее во многих случаях проверить, является ли данный язык автоматным . Поскольку все являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.

Существует также лемма о разрастании для контекстно-свободных языков , ещё более общее утверждение — .

Формулировка

Для бесконечного автоматного языка ${\displaystyle L}$ над алфавитом ${\displaystyle V}$ существует такое натуральное число ${\displaystyle n}$ , что для любого слова ${\displaystyle \alpha \in L}$ длины не меньше ${\displaystyle n}$ найдутся слова ${\displaystyle u,v,w\in V^{*}}$ такие, что ${\displaystyle \alpha =uvw}$ , ${\displaystyle |uv|\leqslant n}$ , ${\displaystyle |v|\geqslant 1}$ и для всякого неотрицательного целого ${\displaystyle i}$ цепочка ${\displaystyle uv^{i}w}$ является словом языка ${\displaystyle L}$ .

Запись в кванторах:

${\displaystyle (\exists n\in \mathbb {N} )(\forall \alpha \in L:|\alpha |\geqslant n)(\exists u,v,w\in V^{*}):\,[\alpha =uvw\land |uv|\leqslant n\land |v|\geqslant 1\land (\forall i\in \mathbb {N} \cup \{0\},uv^{i}w\in L)]}$ .

Доказательство

Пусть автоматный язык ${\displaystyle L}$ содержит бесконечное число цепочек и предположим, что ${\displaystyle L}$ распознаётся детерминированным конечным автоматом ${\displaystyle A}$ с ${\displaystyle n}$ состояниями . Для проверки заключения леммы выберем произвольную цепочку ${\displaystyle \alpha }$ этого языка, которая имеет длину ${\displaystyle n}$ .

Если конечный автомат ${\displaystyle A}$ распознаёт ${\displaystyle L}$ , то цепочка ${\displaystyle \alpha }$ допускается этим автоматом, то есть в автомате ${\displaystyle A}$ существует путь длины ${\displaystyle n}$ из начального в одно из заключительных состояний, помеченный символами цепочки ${\displaystyle \alpha }$ . Путь этот не может быть простым, он должен проходить ровно через ${\displaystyle n+1}$ состояние, в то время как автомат ${\displaystyle A}$ имеет ${\displaystyle n}$ состояний. Это значит, что этот путь проходит по меньшей мере два раза через одно и то же состояние автомата ${\displaystyle A}$ , то есть на этом пути есть цикл с повторяющимся состоянием. Пусть это повторяющееся состояние ${\displaystyle q_{k}}$ .

Разделим цепочку ${\displaystyle \alpha }$ на три части, так что ${\displaystyle \alpha =uvw}$ , где ${\displaystyle v}$ — подцепочка, переводящая ${\displaystyle A}$ из состояния ${\displaystyle q_{k}}$ опять в состояние ${\displaystyle q_{k}}$ , и ${\displaystyle w}$ — подцепочка, переводящая ${\displaystyle A}$ из состояния ${\displaystyle q_{k}}$ в заключительное состояние. Заметим, что как ${\displaystyle u}$ , так и ${\displaystyle w}$ могут быть пустыми, но подцепочка ${\displaystyle v}$ не может быть пустой. Но тогда очевидно, что автомат ${\displaystyle A}$ должен допускать также и цепочку ${\displaystyle uvvw}$ , поскольку повторяющаяся подцепочка ${\displaystyle v}$ снова проходит по циклическому пути из ${\displaystyle q_{k}}$ в ${\displaystyle q_{k}}$ , а также и цепочку ${\displaystyle uvvvw}$ , и любую вида ${\displaystyle uvv...vw}$ .

Это рассуждение и составляет доказательство леммы о накачке.

Обратная формулировка

Другая форма этой леммы, которую иногда удобнее применять, чтобы доказать неавтоматность некоторого языка, для языка ${\displaystyle L}$ над алфавитом ${\displaystyle V}$ состоит в следующем — если имеет место:

${\displaystyle (\forall n\in \mathbb {N} )(\exists \alpha \in L\colon |\alpha |\geqslant n)(\forall u,v,w\in V^{*}\colon \alpha =uvw\land |v|\geqslant 1\ \land |uv|\leqslant n)(\exists i\in \mathbb {N} \cup \{0\})uv^{i}w\not \in L}$

то язык ${\displaystyle L}$ — неавтоматный.

Для доказательства неавтоматности языка можно также пользоваться тем фактом, что пересечение регулярных языков регулярно. Так, непосредственно применить лемму о накачке к языку правильных скобочных структур в алфавите ${\displaystyle \{(,)\}}$ проблематично, но пересечение его с языком ${\displaystyle (^{*})^{*}}$ даёт язык ${\displaystyle (^{n})^{n}}$ , неавтоматность которого тривиально следует из леммы о накачке.

Литература

• Джон Хопкрофт , Раджив Мотвани , Джеффри Ульман . Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М. : , 2002. — С. 528. — ISBN 0-201-44124-1 .

Ссылки

• Пентус, А. Е., Пентус, М. Р. . М., 2004
• Серебряков В. А. , Галочкин М. П., Гончар Д. Р., Фуругян М. Г. — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
• Винокуров Н.С. // Сиб. матем. журнал, 2005, Том 46, № 1. (недоступная ссылка с 13-05-2013 [3901 день] — )