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

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

Лемма о накачке, или лемма о разрастании (англ. 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 — некоторый язык над алфавитом V. Если:

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