Что такое лемма о накачке и как ее выполнить?

Итак, у меня есть вопрос по лемме прокачки A{www|w ∈ {a,b}*} У меня есть правильный ответ, но я не совсем уверен, как это работает. Я дам ответ, чтобы люди знали, с чем я собираюсь

Предположим, что A представляет собой REG, пусть p будет длиной накачки x ∈ A, x=a^p b, a^p b, a^p b.... |s|=3p+3, где каждый a^p b представляет собой w

Пусть s = xyz такое разбиение, что 1)sum of i>=0 s'=xy'z ∈ A 2)|x|>0 , 3)|xy| <=p

По (3) y содержит только a, а по (2) y содержит по крайней мере 1 a. Пусть s'=xyyz, Тогда s=a^+ ba^p ba^p b,

1)s' ∈ A, так как содержит противоречие t>p, т.е. A не является элементом REG


math computation-theory
person Jon    schedule 20.01.2016    source источник
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что для этого существует математический обмен, и его следует перенести туда.   -  person Rob    schedule 21.01.2016
comment
@Rob, это вопрос теории вычислений, он здесь.   -  person Jon    schedule 21.01.2016
comment
@Rob Я не думаю, что вы можете привести веские аргументы в пользу переноса этого вопроса. Math содержит 537 вопросов с тегами regular-language по сравнению с 417 в SO и 17 вопросов с тегами pumping-lemma против 81 на SO. Информатика имеет похожие цифры (это был бы еще один вариант), но я не вижу, чтобы одно явно предпочтительнее другого.   -  person beaker    schedule 21.01.2016
comment
@beaker, учитывая, что математический обмен не имеет тега теории вычислений, я чувствовал, что он здесь. Спасибо, что показали цифры   -  person Jon    schedule 21.01.2016
comment
@ Джон, я думаю, что твой вопрос просто прекрасен там, где он есть. Вы можете добавить два тега, которые я упомянул выше, это может помочь увидеть ваш вопрос тому, кто может ответить. К сожалению, прошло слишком много времени с тех пор, как я фактически использовал лемму о накачке, чтобы помочь мне в дальнейшем.   -  person beaker    schedule 21.01.2016
comment
Возможно, вы захотите прочитать ответы на этот вопрос на cs.stackexchange.com. Одним из преимуществ {math,cs}.stackexchange.com является то, что вы можете использовать mathjax на этих сайтах, что делает такие вопросы и ответы более читабельными.   -  person rici    schedule 21.01.2016
comment
Я думаю, вы пытались прочитать об этом, например. Википедия. Где именно у вас возникла проблема с описанием там?   -  person MvG    schedule 21.01.2016

Ответы (1)


arrow_upward
0
arrow_downward

Я думаю, что вы получите лучшие ответы на cs.stackexchange, но вот основной обзор:

Лемма о накачке (для регулярных языков; есть более сложная лемма для контекстно-свободных языков) — это результат о регулярных языках, который гласит: «Если L — регулярный язык, то существует целое число p, такое что каждое слово в L не меньше длины поскольку p можно разделить на три части x, y и z так, что xz ∈ L, xyz ∈ L, xyyz ∈ L, xyyyz ∈ L и т. д.». (Есть еще несколько деталей, например, длина y не меньше 1, а длина xy равна ‹= p, так что проверьте формальное утверждение в Википедии) «p» часто называют «длиной накачки» языка.

Этот результат обычно используется как способ доказать, что язык не является регулярным — эти доказательства работают, говоря что-то вроде:

  1. Если бы L был регулярным, у него была бы длина накачки p, как в лемме о накачке.

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

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

  4. Следовательно, лемма о накачке для L неверна, а значит, L нерегулярна.

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

Доказательство примера следует этому формату. Вот еще одно доказательство, взятое из недавнего вопроса stackoverflow:

L = {w ∈ {0,1}* | w has an odd length and the middle character is 0}

Теперь, доказывая, что L не является регулярным:

Если бы L был регулярным, он имел бы длину накачки p.

Рассмотрим строку s = '1'*p + '0' + '1'*p - эта строка состоит из L и длиннее p символов. Следовательно, по лемме о накачке s можно разделить на три части x, y, z такие, что |xy|‹=p, |y|>0, а строки вида xyyyz находятся в L.

Но из-за того, как было построено s, мы знаем, что часть y содержит только символы «1», имеет ли строка xyyyz только один символ «0», и в ней больше символов «1» слева от «0», чем вправо, поэтому xyyyz не находится в L.

Следовательно, L не является регулярным.

person Daniel Martin    schedule 03.02.2016