Прокачивание леммы на обычных языках?

Я немного запутался в теории леммы прокачки. Как я знаю, используется, чтобы решить, является ли язык регулярным или нет. Существует переменная let m такая, что это состояния?

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

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

Источник

1 ответ

Решение

Лемма прокачки такова:

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

  • | ъх | ≤ р
  • | х | > 0
  • vx i u ∈ L для всех i ≥ 0

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

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

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

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

Как я уже говорил выше, это не так, есть некоторые прокачиваемые языки, которые не являются регулярными (EDIT Wikipedia имеет пример языка, который удовлетворяет лемме прокачки, но не является регулярным здесь), однако, я думаю, что, возможно, вопрос, который вы хотите задать Спросите: почему все обычные языки могут быть накачаны?

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

Рассмотрим характеристику обычного языка как распознаваемую некоторым дискретным конечным автоматом 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, при обработке w:

  a 1 a 2 a 3... a n
q s → q 1 → q 2 →... → q n = q f

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

  a 1 a 2 a 3 a r a r + 1 a r + 2 a r + k a r + k + 1 a r + k + 2 a n
q s → q 1 → q 2 →... → qr = R → qr + 1 →... → qr + k = R → qr + k + 1 →... → qn = q f

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

  a 1 a 2 a 3 a r
q s → q 1 → q 2 →... → q r

так же, как это:

   v
q s → * q r

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

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

v = a 1 a 2... a r
x = a r + 1 a r + 2... a r + k 
u = a r + k + 1 a r + k + 2... a n

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

   v
q s → * R

И для х:

  Икс
R →* R

И для тебя:

  U
R → * q f

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

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

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

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

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

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

Да, вот оно:

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

  • | хуг | ≤ р
  • | XZ | > 0
  • ux i yz i v ∈ L для всех i ≥ 0

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

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

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

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

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

Источник
Другие вопросы по тегам