Что такое накачка леммы в терминах Леймана?

Question

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

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

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

Answer 1

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

ab
aabb
aaabbb
aaaabbbb

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

aab
bab
aaabbbbbb

и т.д.. не.

Достаточно просто построить FSM для следующих примеров:

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

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

aaaa(a*)bbbb

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

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

Answer 2

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

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

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

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

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

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

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

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

Answer 3

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

В практике насосных лемм недостаточно для ПРОВЕРКИ правильного языка, а скорее как способ сделать доказательство от противного и показать, что язык не вписывается в класс языков (обычный или контекстный) -Бесплатно), показывая, что лемма прокачки не работает для него.

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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

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

, если n = p , строка w = a ^p b ^p . По сути, конечный автомат можно предположить с 3 этапами. Первый этап, он принимает ряд входов и входит во второй этап. Аналогично со стадии 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 ⁿ b ⁿ . Таким образом, для этого языка мы не можем построить конечный автомат. Следовательно, это не регулярно.

Answer 8

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

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

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

Answer 9

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

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

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