Какова Насосная Лемма в терминах Неспециалиста?

Трудная вещь войти в условия неспециалиста, но в основном регулярные выражения должна иметь непустую подстроку в нем, которая может повторяться так много раз, как Вы желаете, в то время как все новое слово остается допустимым для языка.

В практика , качающие леммы не достаточны для ДОКАЗАТЕЛЬСТВА корректного языка, а скорее как способ сделать доказательство противоречием и показать, что язык не помещается в класс языков (Регулярный или Контекстно-свободный) путем показа, что насосная лемма не работает на него.

В основном у Вас есть определение языка (как XML), который является способом сказать, является ли данная строка символов ("слово") членом того языка или нет.

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

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

Теперь предполагают, что у Вас есть строка, которая распознана конечным автоматом, и которая достаточно длинна для "превышения" памяти автоматизации, т.е. в котором должны повториться состояния. Тогда существует подстрока, где состояние автомата в начале подстроки совпадает с состоянием в конце подстроки. Начиная с чтения подстроки не изменяет состояние, это может быть удалено или копировало произвольное число времен без автомата, являющегося более мудрым. Таким образом, эти измененные строки должны также быть приняты.

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

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

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

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

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

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

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

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

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

Можно сказать, что z - это некоторое количество правых паренов.

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

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

Можно сказать, что z - это некоторое количество правых паренов.

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

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

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

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

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

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

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

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

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

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

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

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

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

ab
aabb
aaabbb
aaaabbbb

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

aab
bab
aaabbbbbb

и т.д. - нет.

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

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

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

aaaa(a*)bbbb

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