Что такое лемма о накачке в терминах непрофессионала?

82

Я видел этот вопрос , и мне было любопытно, что это за лемма о перекачке ( Википедия мало помогла).

Я понимаю, что это в основном теоретическое доказательство, которое должно быть истинным, чтобы язык принадлежал определенному классу, но кроме этого, я этого не понимаю.

Кто-нибудь хочет попытаться объяснить это на довольно детальном уровне таким образом, чтобы это было понятно не математикам / докторантам?

Штеймер
источник
2
Я твердо убежден, что к математике / TCS нет короткого пути: «термины непрофессионала» не помогут вам понять. Тем не менее, мы, конечно, подробно рассмотрели это в компьютерных науках ; см. здесь , здесь и здесь .
Рафаэль
1
Обратите внимание, что студенты первого курса обычно должны понимать теорему и ее доказательство и применять их, поэтому просьбу о чем-то «понятном для [...] не докторантов» легко выполнить, заглянув в любой учебник формального языка.
Рафаэль
Лемма о накачке не является доказательством: как следует из названия, это лемма .
nbro

Ответы:

157

Лемма о накачке - это простое доказательство, показывающее, что язык не является регулярным, а это означает, что для него нельзя построить конечный автомат. Канонический пример - язык (a^n)(b^n). Это простой язык, состоящий из любого количества as, за которым следует такое же количество bs. Итак, струны

ab
aabb
aaabbb
aaaabbbb

и т. д. на языке, но

aab
bab
aaabbbbbb

и т.п. нет.

Для этих примеров достаточно просто построить конечный автомат:

FSM

Этот будет работать вплоть до n = 4. Проблема в том, что наш язык не накладывал никаких ограничений на n, а конечные автоматы должны быть, ну, конечными. Независимо от того, сколько состояний я добавлю к этой машине, кто-нибудь может дать мне ввод, где n равно количеству состояний плюс один, и моя машина выйдет из строя. Так что, если можно построить машину для чтения этого языка, где-то внутри должен быть цикл, чтобы количество состояний оставалось конечным. С этими добавленными петлями:

FSM 2

все строки на нашем языке будут приняты, но есть проблема. По прошествии первых четырех aсекунд машина теряет счет введенного количества aсекунд, потому что остается в том же состоянии. Это означает, что после четырех я могу добавить aк строке столько s, сколько хочу, без добавления bs, и все равно получить то же возвращаемое значение. Это означает, что строки:

aaaa(a*)bbbb

с (a*)любым числом as, все будут приняты машиной, даже если они явно не все на языке. В этом контексте мы бы сказали, что часть колонны (a*)можно перекачивать. Тот факт, что конечный автомат конечен, а n не ограничено, гарантирует, что любая машина, которая принимает все строки на языке, ДОЛЖНА иметь это свойство. В какой-то момент машина должна зацикливаться, и в той точке, в которой она зацикливается, язык можно прокачать. Следовательно, для этого языка невозможно построить конечный автомат, и язык не является регулярным.

Помните, что регулярные выражения и машины с конечными состояниями эквивалентны , затем замените aи bоткрывающими и закрывающими тегами Html, которые могут быть встроены друг в друга, и вы поймете, почему нельзя использовать регулярные выражения для синтаксического анализа HTML.

Графика Нуб
источник
2
Ваша вторая диаграмма также неверна, поскольку может дать baaaabbbb.
Джеймс
3
@James, это правда, это можно исправить довольно просто, добавив еще одно принимающее состояние, но для простоты я оставлю его как есть.
Graphics Noob
1
Хороший ответ, но не упоминается, что лемма о перекачке может быть использована для доказательства того, что язык ЯВЛЯЕТСЯ контекстно-свободным, а не просто для опровержения регулярности »
MobileMon
1
Это даже не доказывает, что a^n b^nэто нерегулярно, и не предлагает большой части интуиции относительно леммы о накачке.
Рафаэль
1
@GraphicsNoob Лемма о накачке НЕ является доказательством, это лемма, как следует из названия. Лемма является утверждение , что было доказано. Лемму можно рассматривать как меньшую не столь важную теорему, которая обычно используется для доказательства или демонстрации других предложений или утверждений. Я не верю, что ответ, который начинает говорить, что «лемма о накачке является доказательством», в настоящее время набирает 114 голосов, поэтому за вопросы и ответы следует проголосовать с описанием или объяснением.
nbro
15

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

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

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

LFSR Consulting предоставила хорошее описание. Мы можем изобразить синтаксический анализатор для обычного языка в виде конечного набора прямоугольников и стрелок, где стрелки представляют символы и прямоугольники, соединяющие их (действующие как «состояния»). (Если это сложнее, то это не обычный язык.) Если мы можем получить строку длиннее, чем количество ящиков, это означает, что мы прошли через одну ячейку более одного раза. Это означает, что у нас есть цикл, и мы можем проходить его столько раз, сколько захотим.

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

Итак, в нашем сбалансированном языке мы можем начать с написания любого количества левых скобок. В частности, для любого данного парсера мы можем написать больше левых скобок, чем прямоугольников, и поэтому парсер не может определить, сколько там левых скобок. Следовательно, x - некоторое количество левых скобок, и это фиксировано. y - также некоторое количество левых пар, и оно может увеличиваться бесконечно. Можно сказать, что z - некоторое количество правых скобок.

Это означает, что у нас может быть строка из 43 левых скобок и 43 правых скобок, распознаваемых нашим анализатором, но парсер не может определить это по строке из 44 левых скобок и 43 правых скобок, чего нет в нашем языке, поэтому парсер не может разобрать наш язык.

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

Дэвид Торнли
источник
Отличный ответ и чтение для тех, кто хочет фиксировать сбалансированные строки с помощью регулярных выражений.
Джастин Джонсон
9

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

На практике лемм о подкачке недостаточно, чтобы ДОКАЗАТЬ, что язык правильный, а скорее как способ провести доказательство от противоречия и показать, что язык не подходит к классу языков (регулярных или контекстно-свободных), путем демонстрации леммы о подкачке. не работать на это.

Алексвуд
источник
Что значит « недостаточно, чтобы ДОКАЗАТЬ, что язык правильный»? Под «правильным», я полагаю, вы имели в виду регулярный. Действительно, регулярный язык демонстрирует свойство накачки, но если язык демонстрирует свойство накачки, это не обязательно означает, что он регулярный. С другой стороны, если язык не обладает свойством перекачивания, то мы уверены, что это не обычный язык. По сути, свойство накачки необходимо, но недостаточно, чтобы показать, что язык является регулярным.
nbro
4

По сути, у вас есть определение языка (например, XML), которое позволяет определить, является ли данная строка символов («слово») членом этого языка или нет.

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

Велбог
источник
3

Лемма о простой перекачке применяется для регулярных языков, которые, помимо прочего, представляют собой наборы строк, описываемые конечными автоматами. Основная характеристика конечной автоматизации состоит в том, что у нее есть только конечный объем памяти, описываемый ее состояниями.

Теперь предположим, что у вас есть строка, которая распознается конечным автоматом и достаточно длинна, чтобы «превзойти» память автоматизации, то есть в которой состояния должны повторяться. Затем есть подстрока, в которой состояние автомата в начале подстроки совпадает с состоянием в конце подстроки. Поскольку чтение подстроки не меняет состояния, она может быть удалена или продублирована произвольное количество раз, причем автомат не будет более мудрым. Таким образом, эти модифицированные строки также должны быть приняты.

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

звездно-голубой
источник
Ваш второй абзац хорош, но первый немного плох: «Лемма о простой перекачке подходит для обычных языков». Что делать с обычными языками? Зачем нужна лемма о накачке? Какая связь между леммой о накачке и обычным языком? Вы должны ответить на все эти вопросы, ИМО.
нбро
@starblue: Не могли бы вы сказать, почему. Если язык - $ {a} $, минимальная длина перекачки составляет $ 2 $; если язык $ {a ^ n: n∈ℕ} $, то минимальная длина накачки составляет $ 1 $. подробнее здесь :( math.stackexchange.com/questions/1508471/minimum-pumping-length/… ).
Джастин
0

По определению регулярные языки - это языки, распознаваемые конечным автоматом. Думайте об этом как о лабиринте: состояния - это комнаты, переходы - это коридоры с односторонним движением между комнатами, есть начальная комната и выходная (последняя) комната. Как говорит название «конечный автомат», количество комнат ограничено. Каждый раз, путешествуя по коридору, вы записываете письмо, написанное на его стене. Слово можно распознать, если вы найдете путь от начальной до последней комнаты, проходя через коридоры, помеченные его буквами, в правильном порядке.

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

Аналогичная лемма существует для контекстно-свободных языков. Эти языки могут быть представлены как слово, принимаемое автоматами выталкивания, которые представляют собой конечные автоматы, которые могут использовать стек, чтобы решать, какие переходы выполнять. Тем не менее, поскольку число состояний все еще ограничено, интуиция, объясненная выше, сохраняется, даже если формальное выражение свойства может быть немного более сложным .

Франсуа Г
источник
@ Ищу такой ответ. Могут ли начальная и последняя комнаты быть одинаковыми? Я застрял с этим комментарием: если язык - $ {a} $, минимальная длина перекачки составляет $ 2 $; если язык - $ {a ^ n: n∈N} $, то минимальная длина накачки составляет $ 1 $. Не могли бы вы мне помочь. подробнее здесь :( math.stackexchange.com/questions/1508471/minimum-pumping-length /… ).
Джастин
0

С точки зрения непрофессионала, я думаю, вы почти правы. Это метод доказательства (на самом деле два) для доказательства того, что язык НЕ принадлежит определенному классу.

Например, рассмотрим обычный язык (регулярное выражение, автоматы и т. Д.) С бесконечным количеством строк в нем. В определенный момент, как сказал starblue, у вас заканчивается память, потому что строка слишком длинная для автомата. Это означает, что должен быть кусок строки, который автомат не может определить, сколько у вас копий (вы находитесь в цикле). Итак, любое количество копий этой подстроки в середине строки, и вы все еще находитесь на языке.

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

Брайан Постоу
источник
По крайней мере, последнее предложение неверно. Язык, состоящий из строки «а», обычный, но прокачать его нельзя. Если вы можете накачать струну определенным образом, это не всегда. Например, язык с символами '(' и ')', состоящий из всех сбалансированных выражений (и без несбалансированных), не является регулярным, и вы доказываете это, накачивая "()".
Дэвид Торнли,
@ Дэвид, спасибо, поправил последнее предложение. Но я думаю, что вы ошибаетесь насчет сбалансированных родителей. Я не думаю, что вы можете доказать, что parens не является регулярным, с помощью леммы о перекачке. Я думаю, что Parens насосы.
Брайан Постоу,
0

Например, возьмем этот язык L = a n b n .

Теперь попробуйте представить себе конечный автомат для указанного выше языка для некоторого n .

если n = 1, строка w = ab . Здесь мы можем сделать конечный автомат без зацикливания, если n = 2, строка w = a 2 b 2 . Здесь мы можем сделать конечный автомат без зацикливания

если n = p , строка w = a p b p . По сути, конечный автомат можно считать трехступенчатым. Первый этап, он принимает ряд входных данных и переходит на второй этап. Аналогично от этапа 2 к этапу 3. Назовем эти этапы x , y и z .

Есть некоторые наблюдения

  1. Определенно x будет содержать "a", а z будет содержать "b".
  2. Теперь мы должны прояснить y :
    • case a : y может содержать только 'a'
    • case b : y может содержать только 'b'
    • case c : y может содержать комбинацию 'a' и 'b'

Таким образом, состояния конечного автомата для этапа y должны иметь возможность принимать входные данные «a» и «b», а также не должны принимать больше значений a и b, которые невозможно подсчитать.

  1. Если стадия y принимает только один 'a' и один 'b', тогда требуются два состояния
  2. Если он принимает два 'a' и один 'b', требуются три состояния без циклов и так далее ....

Итак, конструкция стадии y абсолютно бесконечна. Мы можем сделать его конечным, только поместив несколько циклов, и если мы поместим циклы, конечный автомат сможет принимать языки за пределами L = a n b n . Поэтому для этого языка мы не можем построить конечный автомат. Следовательно, это не регулярно.

Саджив Рамакришнан
источник
-1

Это не объяснение как таковое, но оно простое. Для a ^ nb ^ n наш автомат должен быть построен таким образом, что b должен знать количество уже проанализированных a и принимать такое же количество n b. Автомат просто не может делать такие вещи.

SMUsamaShah
источник