Лемма о накачке для регулярных языков - Pumping lemma for regular languages

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

В частности, лемма о накачке говорит, что для любого регулярного языка ${ displaystyle L}$ существует постоянная ${ displaystyle p}$ такое, что любое слово ${ displaystyle w}$ в ${ displaystyle L}$ длиной не менее ${ displaystyle p}$ можно разбить на три подстроки, ${ displaystyle w = xyz}$ , где средняя часть ${ displaystyle y}$ не должно быть пустым, чтобы слова ${ displaystyle xz, xyz, xyyz, xyyyz, ...}$ построен путем повторения ${ displaystyle y}$ ноль или более раз все еще в ${ displaystyle L}$ . Этот процесс повторения известен как «накачивание». Кроме того, лемма о накачке гарантирует, что длина ${ displaystyle xy}$ будет самое большее ${ displaystyle p}$ , устанавливая ограничения на способы, которыми ${ displaystyle w}$ могут быть разделены. Конечные языки бессмысленно удовлетворяют лемме о накачке, имея ${ displaystyle p}$ равна максимальной длине строки в ${ displaystyle L}$ плюс один.

Лемма о перекачке полезна для опровержения регулярности конкретного рассматриваемого языка. Впервые это было доказано Майкл Рабин и Дана Скотт в 1959 г.,^[1] и вскоре после этого был заново открыт Иегошуа Бар-Гилель, Миха А. Перлес, и Эли Шамир в 1961 г., как упрощение их лемма о прокачке для контекстно-свободных языков.^[2]^[3]

Официальное заявление

Позволять ${ displaystyle L}$ быть обычным языком. Тогда существует целое число ${ displaystyle p geq 1}$ в зависимости только от ${ displaystyle L}$ так что каждая строка ${ displaystyle w}$ в ${ displaystyle L}$ длины не менее ${ displaystyle p}$ ( ${ displaystyle p}$ называется «длина накачки»^[4]) можно записать как ${ displaystyle w = xyz}$ (т.е. ${ displaystyle w}$ можно разделить на три подстроки), удовлетворяющие следующим условиям:

${ displaystyle | y | geq 1}$
${ Displaystyle | ху | leq p}$
${ Displaystyle ( forall п geq 0) (ху ^ {п} г в L)}$

${ displaystyle y}$ - это подстрока, которую можно перекачивать (удалять или повторять любое количество раз, и результирующая строка всегда находится в ${ displaystyle L}$ ). (1) означает цикл ${ displaystyle y}$ для перекачивания должен быть длиной не менее одного; (2) означает, что цикл должен выполняться в пределах первого ${ displaystyle p}$ символы. ${ displaystyle | x |}$ должен быть меньше чем ${ displaystyle p}$ (вывод (1) и (2)), но кроме этого, нет никаких ограничений на ${ displaystyle x}$ и ${ displaystyle z}$ .

Проще говоря, для любого обычного языка ${ displaystyle L}$ , любое достаточно длинное слово ${ displaystyle w}$ (в ${ displaystyle L}$ ) можно разделить на 3 части. ${ displaystyle w = xyz}$ , так что все струны ${ displaystyle xy ^ {n} z}$ за ${ Displaystyle п geq 0}$ также в ${ displaystyle L}$ .

Ниже приводится формальное выражение леммы о накачке.

${ displaystyle { begin {array} {l} ( forall L substeq Sigma ^ {*}) quad ({ mbox {regular}} (L) Rightarrow quad (( существует p geq 1) (( forall w in L) ((| w | geq p) Rightarrow quad (( существует x, y, z in Sigma ^ {*}) (w = xyz land (| y | geq 1 land | xy | leq p land ( forall n geq 0) (xy ^ {n} z in L))))))) end {массив }}}$

Использование леммы

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

Например, язык ${ Displaystyle L = {a ^ {n} b ^ {n}: п geq 0 }}$ по алфавиту ${ Displaystyle Sigma = {а, Ь }}$ можно показать как нерегулярные следующим образом:

Позволять ${ displaystyle w, x, y, z, p}$ , и ${ displaystyle n}$ использоваться в формальная формулировка леммы о накачке над. Мы предполагаем, что существует некоторая постоянная ${ displaystyle p}$ . Позволять ${ displaystyle w}$ в ${ displaystyle L}$ быть предоставленным ${ Displaystyle ш = а ^ {р} Ь ^ {р}}$ , которая является строкой длиннее, чем ${ displaystyle p}$ . По лемме о накачке должно существовать разложение ${ displaystyle w = xyz}$ с ${ Displaystyle | ху | leq p}$ и ${ displaystyle | y | geq 1}$ такой, что ${ displaystyle xy ^ {i} z}$ в ${ displaystyle L}$ для каждого ${ displaystyle i geq 0}$ . С помощью ${ Displaystyle | ху | leq p}$ , мы знаем ${ displaystyle y}$ состоит только из экземпляров ${ displaystyle a}$ . Более того, поскольку ${ displaystyle | y | geq 1}$ , он содержит хотя бы один экземпляр буквы ${ displaystyle a}$ . Мы сейчас качаем ${ displaystyle y}$ вверх: ${ displaystyle xy ^ {2} z}$ имеет больше экземпляров буквы ${ displaystyle a}$ чем письмо ${ displaystyle b}$ , поскольку мы добавили несколько экземпляров ${ displaystyle a}$ без добавления экземпляров ${ displaystyle b}$ . Следовательно, ${ displaystyle xy ^ {2} z}$ не в ${ displaystyle L}$ . Мы пришли к противоречию. Следовательно, предположение, что ${ displaystyle L}$ регулярна (т.е. существует такая ${ displaystyle p}$ ) должно быть неверным. Следовательно ${ displaystyle L}$ не регулярно.

Доказательство того, что язык сбалансированных (т.е. правильно вложенных) скобок не является регулярным, следует той же идее. Данный ${ displaystyle p}$ , есть строка сбалансированных круглых скобок, которая начинается с более чем ${ displaystyle p}$ оставленные круглые скобки, так что ${ displaystyle y}$ будет полностью состоять из левых скобок. Повторяя ${ displaystyle y}$ , мы можем создать строку, которая не содержит одинакового количества левых и правых скобок, и поэтому их нельзя сбалансировать.

Доказательство леммы о накачке

Идея доказательства: когда достаточно длинный нить xyz признан конечный автомат, он должен был достичь некоторого состояния (

{ displaystyle q_ {s} = q_ {t}}

) дважды. Следовательно, после повторения («прокачки») средней части

{ displaystyle y}

произвольно часто (xyyz, xyyyz, ...) слово все равно будет распознаваться.

Для каждого обычного языка существует конечный автомат (FSA), который принимает язык. Подсчитывается количество состояний в таком FSA, и это количество используется как длина накачки. ${ displaystyle p}$ . Для строки длиной не менее ${ displaystyle p}$ , позволять ${ displaystyle q_ {0}}$ быть начальным состоянием и пусть ${ displaystyle q_ {1}, ..., q_ {p}}$ быть последовательностью следующих ${ displaystyle p}$ состояния, посещаемые при передаче строки. Потому что FSA имеет только ${ displaystyle p}$ состояний, в этой последовательности ${ displaystyle p + 1}$ посещенные состояния должно быть хотя бы одно повторяющееся состояние. Написать ${ displaystyle q_ {s}}$ для такого состояния. Переходы, которые уводят машину от первого столкновения состояния ${ displaystyle q_ {s}}$ ко второй встрече государства ${ displaystyle q_ {s}}$ соответствовать некоторой строке. Эта строка называется ${ displaystyle y}$ в лемме, и поскольку машина найдет строку без ${ displaystyle y}$ часть или со строкой ${ displaystyle y}$ повторяется сколько угодно раз, условия леммы выполнены.

Например, на следующем изображении показан FSA.

FSA принимает строку: abcd. Поскольку эта строка имеет длину, по крайней мере, равную количеству состояний, равному четырем, принцип голубятни указывает, что должно быть по крайней мере одно повторяющееся состояние среди начального состояния и следующих четырех посещенных состояний. В этом примере только ${ displaystyle q_ {1}}$ это повторяющееся состояние. Поскольку подстрока до н.э проводит машину через переходы, которые начинаются в состоянии ${ displaystyle q_ {1}}$ и закончить в состоянии ${ displaystyle q_ {1}}$ , эта часть может быть повторена, и FSA все равно примет, предоставив строку abcbcd. В качестве альтернативы до н.э часть может быть удалена, и FSA все равно согласится предоставить строку объявление. В терминах леммы о накачке струна abcd разбит на ${ displaystyle x}$ часть а, а ${ displaystyle y}$ часть до н.э и ${ displaystyle z}$ часть d.

Общая версия леммы о накачке для регулярных языков

Если язык ${ displaystyle L}$ регулярна, то существует число ${ displaystyle p geq 1}$ (длина накачки) так, чтобы каждая струна ${ displaystyle uwv}$ в ${ displaystyle L}$ с ${ displaystyle | w | geq p}$ можно записать в виде

{ displaystyle uwv = uxyzv}

со струнами ${ displaystyle x}$ , ${ displaystyle y}$ и ${ displaystyle z}$ такой, что ${ Displaystyle | ху | leq p}$ , ${ displaystyle | y | geq 1}$ и

{ displaystyle uxy ^ {i} zv}

в

{ displaystyle L}

для каждого целого числа

{ displaystyle i geq 0}

.^[5]

Отсюда над стандартная версия следует за особым случаем, причем оба ${ displaystyle u}$ и ${ displaystyle v}$ это пустая строка.

Поскольку общая версия предъявляет более строгие требования к языку, ее можно использовать для доказательства нерегулярности многих других языков, таких как ${ displaystyle {a ^ {m} b ^ {n} c ^ {n}: m geq 1 { text {and}} n geq 1 }}$ .^[6]

Обратное к лемме неверно

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

Например, рассмотрим следующий язык:

{ displaystyle { begin {matrix} L & = & {uvwxy: u, y in {0,1,2,3 } ^ {*}; v, w, x in {0,1, 2,3 } land (v = w lor v = x lor x = w) } && cup {w: w in {0,1,2,3 } ^ { *} land { text {точно}} { tfrac {1} {7}} { text {символов в}} w { text {тройки}} } end {matrix}}}

.

Другими словами, ${ displaystyle L}$ содержит все строки в алфавите ${ Displaystyle {0,1,2,3 }}$ с подстрокой длиной 3, включающей повторяющийся символ, а также со всеми строками в этом алфавите, где ровно 1/7 символов строки равны тройкам. Этот язык не является регулярным, но его все же можно "накачать" ${ displaystyle p = 5}$ . Предположим некоторую строку s имеет длину не менее 5. Тогда, поскольку в алфавите всего четыре символа, по крайней мере два из первых пяти символов в строке должны быть дубликатами. Они разделены максимум тремя символами.

Если повторяющиеся символы разделены символами 0 или 1, перекачайте один из двух других символов в строке, что не повлияет на подстроку, содержащую дубликаты.
Если повторяющиеся символы разделены 2 или 3 символами, перекачайте 2 символа, разделяющих их. В результате перекачки вниз или вверх создается подстрока размером 3, содержащая 2 повторяющихся символа.
Второе условие ${ displaystyle L}$ гарантирует, что ${ displaystyle L}$ не является регулярным: рассмотрим строку ${ displaystyle (013) ^ {3m} (012) ^ {i}}$ . Эта строка находится в ${ displaystyle L}$ именно когда ${ displaystyle i = 4m}$ и поэтому ${ displaystyle L}$ не является регулярным Теорема Майхилла – Нероде.

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

Смотрите также

Примечания

^ Рабин, Майкл; Скотт, Дана (Апрель 1959 г.). «Конечные автоматы и проблемы их решения» (PDF). Журнал исследований и разработок IBM. 3 (2): 114–125. Дои:10.1147 / rd.32.0114. Архивировано 14 декабря 2010 года.CS1 maint: неподходящий URL (ссылка на сайт) Здесь: лемма 8, с.119.
^ Бар-Гилель, Ю.; Perles, M .; Шамир, Э. (1961), "О формальных свойствах грамматик простой фразеологической структуры", Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14 (2): 143–172
^ Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления. Эддисон Уэсли. Здесь: раздел 4.6, с.166
^ Берстель, Жан; Лаув, Аарон; Ройтенауэр, Кристоф; Салиола, Франко В. (2009). Комбинаторика слов. Кристоффель слова и повторы словами. Серия монографий CRM. 27. Провиденс, Род-Айленд: Американское математическое общество. п. 86. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
^ Савич, Уолтер (1982). Абстрактные машины и грамматики. п.49. ISBN 978-0-316-77161-0.
^ Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления. Ридинг / МА: Эддисон-Уэсли. ISBN 978-0-201-02988-8. Здесь: стр. 72, упражнение 3.2 (которое дает немного менее общую версию, требующую |ш|=п) и 3.3