Я видел этот вопрос , и мне было любопытно, что это была за лемма о перекачке (Википедия не не очень помогает).
Я понимаю, что это в основном теоретическое доказательство, которое должно быть истинным, чтобы язык принадлежал определенному классу, но кроме этого, я этого не понимаю.
Кто-нибудь хочет попытаться объяснить это на довольно детальном уровне так, чтобы это было понятно не математикам / докторантам?
Лемма о накачке - это простое доказательство того, что язык не является регулярным, а это означает, что для него нельзя построить конечный автомат. Канонический пример - язык (a^n)(b^n). Это простой язык, который представляет собой любое количество a, за которым следует такое же количество b. Итак, струны
ab
aabb
aaabbb
aaaabbbb
и т. д. на языке, но
aab
bab
aaabbbbbb
и т. д. нет.
Для этих примеров достаточно просто построить конечный автомат:
Этот будет работать до n = 4. Проблема в том, что наш язык не накладывал никаких ограничений на n, а конечные автоматы должны быть, ну, конечными. Независимо от того, сколько состояний я добавлю к этой машине, кто-нибудь может дать мне ввод, где n равно количеству состояний плюс один, и моя машина выйдет из строя. Поэтому, если может быть создана машина для чтения этого языка, где-то внутри должен быть цикл, чтобы количество состояний оставалось конечным. С этими добавленными петлями:
все строки на нашем языке будут приняты, но есть проблема. После первых четырех as машина теряет счет введенного as, потому что остается в том же состоянии. Это означает, что после четырех я могу добавить к строке столько a, сколько захочу, без добавления каких-либо b, и все равно получить то же возвращаемое значение. Это означает, что строки:
aaaa(a*)bbbb
с (a*), представляющим любое количество a, все будут приняты машиной, даже если они явно не все на языке. В этом контексте мы бы сказали, что часть строки (a*) может быть накачана. Тот факт, что конечный автомат конечен, а n не ограничено, гарантирует, что любая машина, которая принимает все строки на языке, ДОЛЖНА обладать этим свойством. В какой-то момент машина должна зацикливаться, и в той точке, в которой она зацикливается, язык можно прокачать. Следовательно, для этого языка невозможно построить конечный автомат, и язык не является регулярным.
Помните, что регулярные выражения и конечные автоматы эквивалентны, затем замените a и b открывающим и закрывающим HTML теги, которые можно встраивать друг в друга, и вы поймете, почему это невозможно использовать регулярные выражения для синтаксического анализа HTML
a^n b^n нерегулярно, и не предлагает большой части интуиции относительно леммы о накачке.
- person Raphael; 07.04.2015
Это устройство, предназначенное для доказательства того, что данный язык не может принадлежать к определенному классу.
Давайте рассмотрим язык сбалансированных круглых скобок (означающих символы '(' и ')', включая все строки, которые сбалансированы в обычном значении, и ни одну из них, которые нет). Мы можем использовать лемму о накачке, чтобы показать, что это не регулярно.
(Язык - это набор возможных строк. Синтаксический анализатор - это своего рода механизм, который мы можем использовать, чтобы увидеть, находится ли строка на языке, поэтому он должен иметь возможность различать строку на языке или строку вне язык. Язык является "обычным" (или "контекстно-независимым", или "контекстно-зависимым" или чем-то еще), если есть обычный (или любой другой) синтаксический анализатор, который может его распознать, различая строки на языке и строки не в язык.)
LFSR Consulting предоставила хорошее описание. Мы можем изобразить синтаксический анализатор для обычного языка в виде конечного набора прямоугольников и стрелок, где стрелки представляют символы, а прямоугольники их соединяют (действуя как «состояния»). (Если это сложнее, то это не обычный язык.) Если мы можем получить строку длиннее, чем количество ящиков, это означает, что мы прошли через одну ячейку более одного раза. Это означает, что у нас есть цикл, и мы можем повторять его столько раз, сколько захотим.
Следовательно, для обычного языка, если мы можем создать произвольно длинную строку, мы можем разделить ее на xyz, где x - это символы, которые нам нужны, чтобы добраться до начала цикла, y - это фактический цикл, а z - это то, что мы необходимо сделать строку действительной после цикла. Важно то, что общая длина x и y ограничена. В конце концов, если длина больше, чем количество ящиков, очевидно, что мы прошли через другой ящик, делая это, и поэтому возникает цикл.
Итак, в нашем сбалансированном языке мы можем начать с написания любого количества левых скобок. В частности, для любого данного парсера мы можем написать больше левых скобок, чем прямоугольников, и поэтому парсер не может определить, сколько там левых скобок. Следовательно, x - это некоторое количество левых скобок, и это фиксировано. y - это также некоторое количество левых пар, и оно может увеличиваться бесконечно. Можно сказать, что z - некоторое количество правильных парных скобок.
Это означает, что у нас может быть строка из 43 левых и 43 правых скобок, распознаваемых нашим анализатором, но парсер не может определить это из строки из 44 левых скобок и 43 правых скобок, чего нет в нашем языке, поэтому парсер не может разобрать наш язык.
Поскольку любой возможный обычный синтаксический анализатор имеет фиксированное количество полей, мы всегда можем написать больше левых скобок, чем это, и, согласно лемме о перекачке, мы можем добавить больше левых скобок таким образом, что парсер не может определить. Следовательно, сбалансированный язык скобок не может быть проанализирован обычным синтаксическим анализатором и, следовательно, не является регулярным выражением.
В терминах непрофессионала это сложно понять, но в основном регулярные выражения должны иметь внутри непустую подстроку, которая может повторяться сколько угодно раз, пока все новое слово остается действительным для языка.
На практике перекачивания лемм недостаточно, чтобы ДОКАЗАТЬ, что язык правильный. ), показав, что лемма о накачке для него не работает.
По сути, у вас есть определение языка (например, XML), с помощью которого можно определить, является ли данная строка символов («слово») членом этого языка или нет.
Лемма о перекачке устанавливает метод, с помощью которого вы можете выбрать «слово» из языка, а затем применить к нему некоторые изменения. Теорема утверждает, что если язык является регулярным, эти изменения должны дать «слово», которое все еще принадлежит к тому же языку. Если слово, которое вы придумали, отсутствует в языке, значит, язык вообще не мог быть регулярным.
Лемма о простой перекачке применяется для регулярных языков, которые, помимо прочего, представляют собой наборы строк, описываемые конечными автоматами. Основная характеристика конечной автоматизации состоит в том, что у нее есть только конечный объем памяти, описываемый ее состояниями.
Теперь предположим, что у вас есть строка, которую распознает конечный автомат и которая достаточно длинна, чтобы «превзойти» память автоматизации, т.е. в которой состояния должны повторяться. Затем есть подстрока, в которой состояние автомата в начале подстроки совпадает с состоянием в конце подстроки. Поскольку чтение подстроки не меняет состояния, она может быть удалена или продублирована произвольное количество раз без вмешательства автомата. Так что эти модифицированные строки также должны быть приняты.
Существует также несколько более сложная лемма о перекачке для контекстно-свободных языков, где вы можете удалить / вставить то, что интуитивно можно рассматривать как совпадающие круглые скобки в двух местах строки.
По определению регулярные языки - это языки, распознаваемые конечным автоматом. Думайте об этом как о лабиринте: состояния - это комнаты, переходы - это коридоры с односторонним движением между комнатами, есть начальная комната и выходная (последняя) комната. Как следует из названия «конечный автомат», количество комнат ограничено. Каждый раз, когда вы путешествуете по коридору, вы записываете письмо, написанное на его стене. Слово можно распознать, если вы найдете путь от начальной до последней комнаты, проходя через коридоры, помеченные его буквами, в правильном порядке.
Лемма о перекачке говорит, что существует максимальная длина (длина перекачки), на которой вы можете бродить по лабиринту, никогда не возвращаясь в комнату, через которую вы прошли раньше. Идея состоит в том, что, поскольку существует очень много отдельных комнат, в которые вы можете пройти, пройдя определенную точку, вы должны либо выйти из лабиринта, либо пересечь свои пути. Если вам удастся пройти в лабиринте более длинный путь, чем эта длина прокачки, то вы выберете обходной путь: вы вставите (хотя бы один) цикл на свой путь, который можно убрать (если вы хотите, чтобы ваше пересечение лабиринта было распознавать меньшее слово) или повторяться (накачиваться) бесконечно (позволяя распознать сверхдлинное слово).
Аналогичная лемма существует для контекстно-свободных языков. Эти языки могут быть представлены как слово, принимаемое автоматами выталкивания, которые представляют собой конечные автоматы, которые могут использовать стек, чтобы решать, какие переходы выполнять. Тем не менее, поскольку число состояний все еще ограничено, интуиция, объясненная выше, сохраняется, даже если формальное выражение свойства может быть немного более сложный.
С точки зрения непрофессионала, я думаю, вы почти правы. Это метод доказательства (на самом деле два) для доказательства того, что язык НЕ принадлежит определенному классу.
Например, рассмотрим обычный язык (регулярное выражение, автоматы и т. Д.) С бесконечным количеством строк в нем. В определенный момент, как сказал starblue, у вас заканчивается память, потому что строка слишком длинная для автомата. Это означает, что должен быть кусок строки, который автомат не может определить, сколько у вас копий (вы находитесь в цикле). Итак, любое количество копий этой подстроки в середине строки, и вы все еще находитесь на языке.
Это означает, что если у вас есть язык, который НЕ имеет этого свойства, т. Е. Имеется достаточно длинная строка с подстрокой NO, которую вы можете повторять любое количество раз и при этом оставаться на языке, тогда язык не является регулярным.
Например, возьмите этот язык L = a n b n.
Теперь попробуйте визуализировать конечный автомат для вышеуказанного языка для некоторых n.
если n = 1, строка w = ab. Здесь мы можем создать конечный автомат без цикла, если n = 2, строка w = a 2 b 2 . Здесь мы можем сделать конечный автомат без зацикливания
если n = p, строка w = a p b p . По сути, конечный автомат можно представить с 3-мя ступенями. Первый этап, он принимает ряд входных данных и переходит на второй этап. Аналогично от этапа 2 к этапу 3. Назовем эти этапы x, y и z.
Есть некоторые наблюдения
Таким образом, состояния конечного автомата для этапа y должны иметь возможность принимать входные данные 'a' и 'b', а также не должны принимать больше значений a и b, которые нельзя подсчитать.
Так что дизайн stage y абсолютно бесконечен. Мы можем сделать его конечным, только поместив несколько циклов, и если мы поместим циклы, конечный автомат сможет принимать языки за пределами L = a n b n < / sup>. Итак, для этого языка мы не можем построить конечный автомат. Следовательно, это не регулярно.
Это не объяснение как таковое, но оно простое. Для a ^ n b ^ n наш автомат должен быть построен таким образом, чтобы b должен знать количество уже проанализированных a и принимать такое же n количество b. Автомат просто не может делать такие вещи.
