Подробно о лемме прокачки для регулярных языков

Question

У меня есть один маленький вопрос о лемме прокачки для обычных языков - достаточно ли этого, чтобы показать, что если конкретная строка, принадлежащая языку L, не может быть прокачана, то язык нерегулярен? Например, если я выберу язык L1 в форме a ^ nb ^ n (ab, aabb, aaabbb ...) и покажу, что строка aabb не может быть перекачана и все еще будет частью L1, то будет ли она для меня правильно сразу сделать вывод, что L1 нерегулярен?

Приветствие.

Answer 1

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

(Примечание: аналогично для контекстно-свободных языков и соответствующихпрокачка леммы есть)

Answer 2

Лемма прокачки гласит: Если язык A регулярный =>, существует число p (длина прокачки), где, если s - любая строка из L такая, что | s |> = p, то s можно разделить на три части: s = xyz, удовлетворяющих следующему условию:

1. xy ⁱ z находится в L для каждого i> = 0
2. | y |> = 0
3. p> = | xy |

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

Давайте попробуем продемонстрировать, что L = {0 ⁿ 1 ⁿ } | n> = 0} не является регулярным.Наоборот, мы предполагаем, что L. регулярно.

Вы можете думать об этой демонстрации как об игре:
Претендент: Он выбирает длину прокачки p.Вы не можете делать какие-либо предположения об этом.
Вы : Теперь ваша очередь: выберите «вид» строки, представляющей неправильность языка.
Допустим, строка имеет вид 0 ^p 1 ^p .
Хороший совет на этом шаге - попытаться ограничить противника следующим ходом.
Претендент: Он представляет вам строку s в форме 0 ^p 1 ^p .
Вы: Этовремя прокачать!Если вы правильно выбрали форму строки в предыдущем шаге, вы можете сделать некоторые предположения.
В нашем случае, например, мы знаем, что подстрока y состоит только из 0s (по крайней мере, один 0, потому что | y |> 0), потому что | xy | <= p и первые p-элементы равны 0s. </p>

Теперь мы покажем, что он существует i> = 0 так, что xy ⁱ z отсутствует в L. Например, для i = 2 строка xyyz имеет больше 0s, чем 1s, и поэтому не являетсячлен Л. Этот случай противоречие.=> L не является регулярным.

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

Возможно, вам уже поздно помогать, но кому-то еще может понадобитьсятакое объяснение ... может быть ^^

ура.

Answer 3

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

Answer 4

Да, вот как это работает, но будьте осторожны, показывая, как строка «не может быть накачана»

Для этого вам нужно разбить строку w в L на подстроки xyz и показать, что некоторыеверсии xy ^ 1z для int ii> = 0 приводят к строкам не в L, но все еще принимаются DFA M (для M, построенного для принятия L), что приводит к противоречию.

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