Насосная лемма для простых конечных регулярных языков

20

В Википедии есть следующее определение леммы прокачки для регулярных языков ...

Пусть обычный язык. Тогда существует целое число ≥ 1, зависящее только от , так что каждая строка в длиной не менее ( называется «длиной накачки») может быть записана как = (т. можно разделить на три подстроки), удовлетворяющих следующим условиям:LL w L p p w x y z wpLwLppwxyzw

  1. | y | ≥ 1
  2. | xy | ≤ p
  3. для всех i ≥ 0, xyizL

Я не вижу, как это выполняется для простого конечного регулярного языка. Если у меня есть алфавит { a,b } и регулярное выражение ab тогда L состоит только из одного слова, a которым следует b . Теперь я хочу посмотреть, удовлетворяет ли мой обычный язык лемме прокачки ...

Поскольку в моем регулярном выражении ничего не повторяется, значение y должно быть пустым, чтобы условие 3 выполнялось для всех i . Но если это так, то оно не выполняется условие 1, которое говорит, что y должно быть по крайней мере 1 в длину!

Если вместо этого я позволю быть либо a , b, либо a b, тогда оно будет удовлетворять условию 1, но не выполнит условие 3, потому что оно фактически никогда не повторяется.yabab

Я явно упускаю что-то невероятно очевидное. Который?

Фил Райт
источник

Ответы:

29

Вы правы - мы не можем позволить «накачки» слова конечного . Вы упускаете то, что лемма говорит, что существует число p , но не сообщает нам число.Lp

Все слова больше , чем можно прокачивать, в силу леммы. Для конечного L , это происходит так , что р больше , чем длина самого длинного слова в L . Таким образом, лемма справедлива только в вакууме и не может быть применена к любому слову в L , т. Е. Любое слово в L не удовлетворяет условию «иметь длину не менее p », как того требует лемма.pLpLLLp


Следствие: если имеет длину накачки p и существует какое-то слово w L длины хотя бы p , то L бесконечно.LpwLpL

Ран Г.
источник
2
Хороший пример пустого множества выполняющего -statements.
Рафаэль
7

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

Согласно Википедии ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement ), лемма прокачки гласит: (LΣ*)(регулярный(L)((п1)((весL)((|вес|п)((Икс,Y,ZΣ*)(весзнак равноИксYZ(|Y|1|ИксY|п(я0)(ИксYяZL))))))))

Для любого конечного языка пусть l m a x будет максимальной длиной слов в L , и пусть p в лемме прокачки будет l m a x + 1 . Лемма накачки справедлива, поскольку в L нет слов , длина которых l m a x + 1 .LLмaИксLпLмaИкс+1LLмaИкс+1

У Инь
источник
2

Один из способов формализации основной части леммы о накачке заключается в следующем: :LКзнак равно{весL||вес|К}

Если регулярно, существует p N, так чтоLпN

(*).весLп, Икс,Y,Z...

Для всех конечных и p > max { | ш | w L } , очевидно, что L p = . Поэтому (*) верно (слабо) для таких p .Lп>Максимум{|вес||весL}Lпзнак равноп

Рафаэль
источник