Лемма о разрастании

Материал из Википедии — свободной энциклопедии

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

Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.

[править] Формальная запись

Пусть L автоматный язык над алфавитом V. Тогда:

$(\exists n\in \mathbb{N})(\forall \alpha \in L:|\alpha|>n)(\exists u,v,w\in V^*):$
$[\alpha=uvw \land |uv|\leq n \land |v|\geq 1 \land (\forall i\in\mathbb{N} uv^iw\in L)].$

[править] Доказательство

Итак, пусть автоматный язык $L$ содержит бесконечное число цепочек.

Предположим, что $L$ распознается детерминированным конечным автоматом $A$ с $n$ состояниями.

Для проверки автоматности языка $L$ выберем произвольную цепочку $α$ этого языка, которая имеет длину $n$ .

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

Разделим цепочку $α$ на три части, так что $α = u v w$ , где $v$ – подцепочка, переводящая $A$ из состояния $q k$ опять в состояние $q k$ , и $w$ – подцепочка, переводящая $A$ из состояния $q k$ в заключительное состояние. Заметим, что как $u$ , так и $w$ могут быть пустыми, но подцепочка $v$ не может быть пустой. Но тогда очевидно, что автомат $A$ должен допускать также и цепочку $u v v w$ , поскольку повторяющаяся подцепочка $v$ снова проходит по циклическому пути из $q k$ в $q k$ , а также и цепочку $u v v v w$ , и любую вида $u v v ... v w$ .

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

[править] Обратная формулировка

Другая форма этой леммы, которую иногда удобнее применять, чтобы доказать неавтоматность некоторого языка, записывается так:

Пусть L — некоторый язык над алфавитом V. Если:

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