Лемма о накачке (лемма о разрастании, лемма-насос; англ. pumping lemma) — важное утверждение теории автоматов, позволяющее во многих случаях проверить, является ли данный язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.
Существует также лемма о разрастании для контекстно-свободных языков, ещё более общее утверждение — лемма о разрастании индексных языков.
Формулировка
Для бесконечного автоматного языка L {displaystyle L} над алфавитом V {displaystyle V} существует такое натуральное число n {displaystyle n} , что для любого слова α ∈ L {displaystyle alpha in L} длины не меньше n {displaystyle n} найдутся слова u , v , w ∈ V ∗ {displaystyle u,v,win V^{*}} такие, что α = u v w {displaystyle alpha =uvw} , | u v | ⩽ n {displaystyle |uv|leqslant n} , | v | ⩾ 1 {displaystyle |v|geqslant 1} и для всякого неотрицательного целого i {displaystyle i} цепочка u v i w {displaystyle uv^{i}w} является словом языка L {displaystyle L} .
Запись в кванторах:
( ∃ n ∈ N ) ( ∀ α ∈ L : | α | ⩾ n ) ( ∃ u , v , w ∈ V ∗ ) : [ α = u v w ∧ | u v | ⩽ n ∧ | v | ⩾ 1 ∧ ( ∀ i ∈ N ∪ { 0 } , u v i w ∈ L ) ] {displaystyle (exists nin mathbb {N} )(forall alpha in L:|alpha |geqslant n)(exists u,v,win V^{*}):,[alpha =uvwland |uv|leqslant nland |v|geqslant 1land (forall iin mathbb {N} cup {0},uv^{i}win L)]} .Доказательство
Пусть автоматный язык L {displaystyle L} содержит бесконечное число цепочек и предположим, что L {displaystyle L} распознаётся детерминированным конечным автоматом A {displaystyle A} с n {displaystyle n} состояниями. Для проверки заключения леммы выберем произвольную цепочку α {displaystyle alpha } этого языка, которая имеет длину n {displaystyle n} .
Если конечный автомат A {displaystyle A} распознаёт L {displaystyle L} , то цепочка α {displaystyle alpha } допускается этим автоматом, то есть в автомате A {displaystyle A} существует путь длины n {displaystyle n} из начального в одно из заключительных состояний, помеченный символами цепочки α {displaystyle alpha } . Путь этот не может быть простым, он должен проходить ровно через n + 1 {displaystyle n+1} состояние, в то время как автомат A {displaystyle A} имеет n {displaystyle n} состояний. Это значит, что этот путь проходит по меньшей мере два раза через одно и то же состояние автомата A {displaystyle A} , то есть на этом пути есть цикл с повторяющимся состоянием. Пусть это повторяющееся состояние q k {displaystyle q_{k}} .
Разделим цепочку α {displaystyle alpha } на три части, так что α = u v w {displaystyle alpha =uvw} , где v {displaystyle v} — подцепочка, переводящая A {displaystyle A} из состояния q k {displaystyle q_{k}} опять в состояние q k {displaystyle q_{k}} , и w {displaystyle w} — подцепочка, переводящая A {displaystyle A} из состояния q k {displaystyle q_{k}} в заключительное состояние. Заметим, что как u {displaystyle u} , так и w {displaystyle w} могут быть пустыми, но подцепочка v {displaystyle v} не может быть пустой. Но тогда очевидно, что автомат A {displaystyle A} должен допускать также и цепочку u v v w {displaystyle uvvw} , поскольку повторяющаяся подцепочка v {displaystyle v} снова проходит по циклическому пути из q k {displaystyle q_{k}} в q k {displaystyle q_{k}} , а также и цепочку u v v v w {displaystyle uvvvw} , и любую вида u v v . . . v w {displaystyle uvv...vw} .
Это рассуждение и составляет доказательство леммы о накачке.
Обратная формулировка
Другая форма этой леммы, которую иногда удобнее применять, чтобы доказать неавтоматность некоторого языка, для языка L {displaystyle L} над алфавитом V {displaystyle V} состоит в следующем — если имеет место:
( ∀ n ∈ N ) ( ∃ α ∈ L : | α | ⩾ n ) ( ∀ u , v , w ∈ V ∗ : α = u v w ∧ | v | ⩾ 1 ∧ | u v | ⩽ n ) ( ∃ i ∈ N ∪ { 0 } ) u v i w ∉ L {displaystyle (forall nin mathbb {N} )(exists alpha in Lcolon |alpha |geqslant n)(forall u,v,win V^{*}colon alpha =uvwland |v|geqslant 1 land |uv|leqslant n)(exists iin mathbb {N} cup {0})uv^{i}w ot in L}то язык L {displaystyle L} — неавтоматный.
Для доказательства неавтоматности языка можно также пользоваться тем фактом, что пересечение регулярных языков регулярно. Так, непосредственно применить лемму о накачке к языку правильных скобочных структур в алфавите { ( , ) } {displaystyle {(,)}} проблематично, но пересечение его с языком ( ∗ ) ∗ {displaystyle (^{*})^{*}} даёт язык ( n ) n {displaystyle (^{n})^{n}} , неавтоматность которого тривиально следует из леммы о накачке.