Лемма о накачке

В теории формальных языков, лемма о накачке для регулярных языков описывает существенное свойство всех регулярных языков. Неформально она утверждает, что все достаточно длинные слова регулярного языка можно накачать, то есть повторить внутреннюю часть слова сколько угодно раз, производя новое слово, также принадлежащее языку.

Лемма о накачке описывает существенное свойство регулярных языков. Она утверждает, что слово w языка L длины по меньшей мере m, (где m константа, называемая длиной накачки, зависит лишь от L) можно разделить на три подстроки, <math>w = xyz</math>, так что среднюю часть, y (непустую), можно повторить произвольное число раз (включая ноль, то есть удалить) и получить строку из L. Этот процесс повторения называется «накачкой». Более того, лемма о накачке гарантирует, что длина xy не превысит m, ограничивая способы разделения строки w. Заметим, что конечные языки удовлетворяют требованиям леммы о накачке тривиально определяя m длиной максимальной строки из языка плюс один.

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

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

Дата добавления: 2015-07-26; просмотров: 170; Нарушение авторских прав

Мы поможем в написании ваших работ!