Прокачка леммы на регулярных языках?

Я немного запутался в теории леммы о накачке. Насколько я знаю, используется, чтобы решить, регулярный язык или нет. Есть переменная let be m такая, что есть состояния?

x = vxu
Where vx >= m
And u not ε (>=1)
and a variable i such that v(x^i)u

Поэтому я не могу понять, как это работает. Я имею в виду, где это полезно? Разбив строку на 3 части и повторив x? И как это проявляется, регулярно он или нет? И есть ли разница между леммой о перекачке для обычных языков и контекстно-свободных языков?


context-free-grammar pumping-lemma
person Dr. Programmer    schedule 09.01.2014    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Лемма о накачке такова:

Для обычного языка L существует p ›0 такое, что для всех w ∈ L, где | w | ≥ p, существует некоторое разбиение w = vxu, для которого выполняется следующее:

  • | vx | ≤ p
  • | x | ›0
  • vx i u ∈ L для всех i ≥ 0

Причина, по которой я повторил это снова, состоит в том, что некоторые из ваших неравенств ошибочны.

Для чего нужна лемма о накачке?

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

Как узнать, регулярно ли это?

Как я уже сказал выше, это не так, есть некоторые языки, которые можно прокачивать, которые не являются регулярными (ИЗМЕНИТЬ В Википедии есть пример языка, который удовлетворяет лемме прокачки, но не является регулярным здесь), однако я думаю, что, возможно, вы хотите задать следующий вопрос: почему все обычные языки можно прокачать?

Почему все обычные языки можно прокачать?

Рассмотрим характеристику регулярного языка как распознаваемую некоторым дискретным конечным автоматом, M, с некоторым конечным числом состояний n.

Затем рассмотрим некоторую строку на языке M, которую мы назовем w, для которой | w | ≥ n.

При проверке w, M должен проходить через | w | +1 состояния (включая его начальное и конечное состояния). Итак, по принципу ячейки, M должен проходить через некоторые состояния более одного раза (потому что | w | + 1 ›n).

Пусть w = a 1 a 2 ... a n

Представьте, что это переходы между состояниями M, начиная с q s и заканчивая q f < / strong>, в обработке w:

  a1   a2   a3 ... an
qs → q1 → q2 → ... → qn = qf

Теперь давайте посмотрим на часть этих переходов состояний, где M повторяет состояние, мы назовем это состояние R:

  a1   a2   a3     ar      ar+1   ar+2   ar+k       ar+k+1   ar+k+2  an
qs → q1 → q2 → ... → qr = R → qr+1 → ... → qr+k = R → qr+k+1 → ... → qn = qf

Давайте воспользуемся сокращением, чтобы сказать это:

  a1   a2   a3     ar
qs → q1 → q2 → ... → qr

то же самое, что и это:

   v
qs →* qr

где v = a 1 a 2 ... a r

Теперь давайте разделим w на три части, w = vxu, следующим образом:

v = a1a2...ar
x = ar+1ar+2...ar+k 
u = ar+k+1ar+k+2...an

Теперь мы видим, что для v:

   v
qs →* R

И для x:

  x
R →* R

И для u:

  u
R →* qf

(Все, что я сделал, это разделил более длинную диаграмму перехода состояний выше на три отдельных)

Здесь вы видите, что M также принимает vu, vxxu, vxxxu, ..., vx i u для i ≥ 0, поскольку обработка строки x в состоянии R сохраняет < strong> M в состоянии R.

По сути, цель леммы о перекачке - найти тот бит строки, который не изменяет состояние M при обработке.

Теперь вы можете задаться вопросом. Что делать, если M не распознает строки, для которых | w | ≥ n верно?

Что ж, в этом случае вы можете заключить, что язык регулярный, просто по тому факту, что он конечен (все конечные подмножества ∑ * регулярны), и, кроме того, лемма о накачке пусто верна , вы просто выбираете длину накачки p ›n и можете быть уверены, что все строки, распознаваемые M, также удовлетворяют | w | ≥ p можно прокачать (потому что вы знаете, что ничего не существует).

Отличается ли лемма о накачке для контекстно-свободных языков?

Да, вот оно:

Для контекстно-свободного языка L существует p ›0 такое, что для всех w ∈ L, где | w | ≥ p, существует некоторое разбиение w = uxyzv, для которого выполняется следующее:

  • | xyz | ≤ p
  • | xz | ›0
  • ux i yz i v ∈ L для всех i ≥ 0

Доказательство для этого немного сложнее, и этот ответ уже довольно длинный, поэтому вот набросок:

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

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

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

Если вам нужна дополнительная информация, я рекомендую Введение в теорию вычислений от Майкла Сипсера. В нем есть несколько хороших разделов по обеим леммам о накачке, и я считаю, что он очень хорошо их объясняет.

person amnn    schedule 09.01.2014
comment
Очень хорошее объяснение, спасибо! Я изучу ваше объяснение, и если возникнут другие вопросы, я отправлю его в качестве комментария здесь. Но я думаю, что это принятый ответ, поэтому я сделаю его принятым. - person Dr. Programmer; 09.01.2014
comment
Просто проверка, когда говорят, что язык не является регулярным, означает, что вы не можете написать для него обычное выражение? - person Dr. Programmer; 09.01.2014
comment
Это правильно, язык является регулярным, если существует регулярное выражение E, которое его распознает, или если существует DFA, M, которое его принимает (действительно, вы можете преобразовать любое регулярное выражение E в такое DFA M, и наоборот). - person amnn; 09.01.2014