Я видел этот вопрос, и мне было любопытно, что было pumping lemma (Wikipedia не помог многим).
Я понимаю, что это в основном теоретическое доказательство, которое должно быть истинным для того, чтобы язык находился в определенном классе, но помимо этого я его действительно не понимаю.
Кто-нибудь хочет попытаться объяснить это на достаточно гранулированном уровне, понятным не математикам/докторам соц-доктора?
Лемма откачки является простым доказательством того, что язык не является регулярным, что означает, что для него невозможно построить конечный государственный механизм. Канонический пример - это язык (a^n)(b^n). Это простой язык, который представляет собой всего лишь число a s, за которым следует такое же число b s. Итак, строки
ab
aabb
aaabbb
aaaabbbb
и т.д.. находятся на языке, но
aab
bab
aaabbbbbb
и т.д.. не являются.
Это достаточно просто, чтобы построить FSM для этих примеров:
Это будет работать до n = 4. Проблема в том, что наш язык не ограничивал n, а конечные государственные машины должны быть, конечно, конечными. Независимо от того, сколько штатов я добавляю к этой машине, кто-то может дать мне вход, где n равно числу состояний плюс один, и моя машина потерпит неудачу. Поэтому, если для чтения этого языка может быть построена машина, там должен быть цикл где-то, чтобы количество состояний было конечным. При добавлении этих петель:
все строки на нашем языке будут приняты, но есть проблема. После первых четырех a s машина теряет количество входов a, потому что она остается в том же состоянии. Это означает, что после четырех я могу добавить столько a, сколько хочу этой строки, не добавляя никаких b s и все равно получаю одинаковое возвращаемое значение. Это означает, что строки:
aaaa(a*)bbbb
с (a*), представляющим любое число a s, все будут приняты машиной, хотя они явно не все на этом языке. В этом контексте мы бы сказали, что часть строки (a*) может накачиваться. Тот факт, что конечный автомат конечен и n не ограничен, гарантирует, что любая машина, которая принимает все строки на языке, ДОЛЖНА иметь это свойство. Машина должна зацикливаться в какой-то точке, и в точке, где она петли, язык может накачиваться. Поэтому для этого языка не может быть создан конечный государственный аппарат, а язык не является регулярным.
Помните, что регулярные выражения и конечные машины эквивалентны, затем замените a и b на открывающие и закрывающие теги Html, которые могут быть встроены друг в друга, и вы можете понять, почему невозможно использовать регулярные выражения для анализа Html
Это устройство, предназначенное для доказательства того, что данный язык не может быть определенного класса.
Рассмотрим язык сбалансированных круглых скобок (означая символы '(' и ')' и включающие все строки, которые сбалансированы в обычном значении, и ни один из них не является). Мы можем использовать лемму о перекачке, чтобы показать, что это не является регулярным.
(Язык - это набор возможных строк. Парсер - это какой-то механизм, который мы можем использовать, чтобы увидеть, является ли строка на языке, поэтому она должна быть способна рассказать о различии между строкой на языке или строка вне языка. Язык является "регулярным" (или "контекстно-зависимым" или "контекстно-зависимым" или любым другим), если есть регулярный (или любой другой) парсер, который может его распознать, различая строки на языке и строки не на языке.)
LFSR Consulting предоставила хорошее описание. Мы можем нарисовать синтаксический анализатор для регулярного языка как конечный набор ящиков и стрелок со стрелками, представляющими символы, и ящики, соединяющие их (действующие как "состояния" ). (Если это более сложно, это не обычный язык.) Если мы можем получить строку длиннее, чем количество ящиков, это означает, что мы проходили через один ящик более одного раза. Это означает, что у нас был цикл, и мы можем проходить цикл столько раз, сколько хотим.
Следовательно, для обычного языка, если мы можем создать произвольно длинную строку, мы можем разделить ее на xyz, где x - это символы, которые нам нужно получить до начала цикла, y - фактический цикл, а z это то, что нам нужно, чтобы строка была действительной после цикла. Важно то, что полные длины х и у ограничены. В конце концов, если длина больше, чем количество ящиков, мы, очевидно, прошли через другую шкатулку, и вот там цикл.
Итак, на нашем сбалансированном языке мы можем начать с написания любого количества левых круглых скобок. В частности, для любого данного синтаксического анализа мы можем записать больше левых парен, чем есть поля, и поэтому синтаксический анализатор не может определить, сколько осталось парнов. Следовательно, x - некоторое количество левых парен, и это фиксировано. y также некоторое количество левых парен, и это может увеличиваться бесконечно. Можно сказать, что z - некоторое число правых парен.
Это означает, что у нас может быть строка из 43 левых парен и 43 правых парсов, распознаваемых нашим парсером, но синтаксический анализатор не может сказать, что из строки из 44 левых парен и 43 правых парен, что нет в нашей язык, поэтому синтаксический анализатор не может анализировать наш язык.
Так как любой возможный регулярный синтаксический анализатор имеет фиксированное количество ящиков, мы всегда можем записать больше левых парен, чем это, и по лемме перекачки мы можем добавить больше левых парсов так, чтобы синтаксический анализатор не мог сказать. Следовательно, сбалансированный язык скобок не может быть проанализирован регулярным синтаксическим анализатором и, следовательно, не является регулярным выражением.
Его трудно найти в непрофессиональных терминах, но в основном регулярные выражения должны содержать непустую подстроку внутри нее, которая может повторяться столько раз, сколько вы хотите, пока все новое слово остается в силе для языка.
В практике леммы откачки недостаточны для того, чтобы ПРОВЕРИТЬ язык корректно, а скорее как способ сделать доказательство в противоречии и показать, что язык не соответствует классу языков (регулярный или Context-Free), показывая лемму о перекачке, не работает для нее.
В принципе, у вас есть определение языка (например, XML), что позволяет определить, является ли данная строка символов ( "слово" ) членом этого языка или нет. Лемма откачки устанавливает метод, с помощью которого вы можете выбрать слово из языка, а затем применить к нему некоторые изменения. Теорема гласит, что если язык является регулярным, эти изменения должны давать "слово", которое все еще с одного языка. Если слово, которое вы придумали, не соответствует языку, тогда язык не мог быть обычным в первую очередь.
Простая лемма накачки является, среди прочего, той, которая предназначена для регулярных языков, которые являются наборами строк, описываемых конечными автоматами. Основная характеристика конечной автоматизации заключается в том, что она имеет только конечный объем памяти, описываемый ее состояниями.
Теперь предположим, что у вас есть строка, которая распознается конечным автоматом и которая достаточно длинна, чтобы "превышать" память автоматизации, то есть в которой должны повторяться состояния. Тогда есть подстрока, в которой состояние автомата в начале подстроки совпадает с состоянием в конце подстроки. Так как чтение подстроки не изменяет состояние, оно может быть удалено или дублировано произвольным числом раз, без того, чтобы автомат был более мудрым. Поэтому эти модифицированные строки также должны быть приняты.
Существует также несколько более сложная лемма откачки для контекстно-свободных языков, где вы можете удалить/вставить то, что можно интуитивно рассматривать как совпадающие скобки в двух местах в строке.
По определению регулярными языками являются те, которые распознаются автоматом конечного состояния. Подумайте об этом как о лабиринте: государства - это комнаты, переходы - это односторонние коридоры между комнатами, начальная комната и выходная (конечная) комната. Как говорит название "автомат конечного состояния", существует конечное количество комнат. Каждый раз, когда вы путешествуете по коридору, вы записываете письмо, написанное на его стене. Слово может быть распознано, если вы можете найти путь от начальной до последней комнаты, проходя через коридоры, обозначенные буквами, в правильном порядке.
Лемма откачки говорит, что существует максимальная длина (длина прокачки), для которой вы можете бродить по лабиринтам, не возвращаясь в комнату, через которую вы уже прошли. Идея состоит в том, что, поскольку есть только очень много отдельных комнат, в которые вы можете пройти, мимо определенного момента, вам нужно либо выйти из лабиринта, либо пересечь ваши следы. Если вам удастся пройти более длинный путь, чем эта длина накачки в лабиринте, вы делаете обход: вы вставляете (по крайней мере один) цикл на своем пути, который можно удалить (если вы хотите, чтобы ваше пересечение лабиринта распознать меньшее слово) или повторять (накачивать) бесконечно (позволяя распознавать сверхдолгое слово).
Существует аналогичная лемма для контекстно-свободных языков. Эти языки могут быть представлены как слово, принятое автоматами pushdown, которые являются автоматами конечного состояния, которые могут использовать стек для определения того, какие переходы выполнять. Тем не менее, поскольку существует еще конечное число состояний, описанная выше интуиция переносится, даже через формальное выражение свойства может быть немного более сложным.
В условиях laymans, я думаю, что у вас почти все. Это метод доказательства (фактически два) для доказательства того, что язык НЕ в определенном классе.
Например, рассмотрим регулярный язык (регулярное выражение, автоматы и т.д.) с бесконечным числом строк в нем. В определенный момент, как сказал starblue, у вас закончилась память, потому что строка слишком длинная для автомата. Это означает, что должен быть фрагмент строки, который автомат не может определить, сколько его копий у вас (вы находитесь в цикле). Итак, любое количество копий этой подстроки в середине строки, и вы все еще находитесь на этом языке.
Это означает, что если у вас есть язык, который НЕ имеет этого свойства, т.е. существует достаточно длинная строка с подстрокой NO, которую вы можете повторять сколько угодно раз и все еще быть на языке, тогда язык не является регулярно.
Например, возьмите этот язык L = a ^ n b ^ n
Теперь попробуйте визуализировать конечный автомат для указанного выше языка для некоторого n
если n = 1, строка w = ab. Здесь мы можем сделать конечный автомат с замкнутым циклом если n = 2, то строка w = a ^ 2b ^ 2. Здесь мы можем сделать конечный автомат с замкнутым циклом
если n = p, строка w = a ^ pb ^ p. По существу, конечный автомат может быть принят с 3 этапами. На первом этапе он принимает серию входных сигналов и вводит второй этап. Аналогично со стадии 2 - этап 3. Назовем эти этапы такими, как x, y и z
Есть некоторые наблюдения 1. Определенно, x будет содержать "a", а z будет содержать "b". 2. Теперь мы должны быть понятны относительно y случай a. y может содержать только "a" случай b. y может содержать только "b" случай c. y может содержать комбинацию 'a' и 'b' Таким образом, конечные состояния автомата для этапа y должны иметь возможность вводить входы "a" и "b", а также не должны принимать больше a и b, которые не могут быть счетными.
Таким образом, конструкция стадии y является чисто бесконечной. Мы можем только сделать это конечным, поместив некоторые петли, и если положить петли, конечный автомат может принимать языки за пределами L = a ^ nb ^ n. Поэтому для этого языка мы не можем построить конечный автомат. Следовательно, он не является регулярным.
Это не объяснение как таковое, но это просто. Для a ^ n b ^ n наш FSM должен быть построен таким образом, что b должен знать число уже проанализированных и будет принимать одно и то же n число b. FSM не может просто делать такие вещи.