В Википедии есть следующее определение леммы прокачки для регулярных языков ...
Пусть обычный язык. Тогда существует целое число ≥ 1, зависящее только от , так что каждая строка в длиной не менее ( называется «длиной накачки») может быть записана как = (т. можно разделить на три подстроки), удовлетворяющих следующим условиям:L w L p p w x y z w
- | | ≥ 1
- | | ≤
- для всех ≥ 0, ∈
Я не вижу, как это выполняется для простого конечного регулярного языка. Если у меня есть алфавит { } и регулярное выражение тогда состоит только из одного слова, которым следует . Теперь я хочу посмотреть, удовлетворяет ли мой обычный язык лемме прокачки ...
Поскольку в моем регулярном выражении ничего не повторяется, значение должно быть пустым, чтобы условие 3 выполнялось для всех . Но если это так, то оно не выполняется условие 1, которое говорит, что должно быть по крайней мере 1 в длину!
Если вместо этого я позволю быть либо a , b, либо a b, тогда оно будет удовлетворять условию 1, но не выполнит условие 3, потому что оно фактически никогда не повторяется.
Я явно упускаю что-то невероятно очевидное. Который?
Насосная лемма обычно используется на бесконечных языках, то есть на языках, которые содержат бесконечное количество слов. Для любого конечного языка , поскольку он всегда может быть принят DFA с конечным числом состояний, L должен быть регулярным.L L
Согласно Википедии ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement ), лемма прокачки гласит:( ∀ L ⊆ Σ*)( обычный ( L ) ⇒( ( ∃ p ≥ 1 ) ( ( ∀ w ∈ L ) ( ( | w | ≥ p ) ⇒( ( ∃ х , у, z∈ Σ*) ( ш = х уZ∧ ( | у| ≥1∧ | ху| ≤p∧(∀i≥0)(x yяZ∈ L ) ) ) ) ) ) ) )
Для любого конечного языка пусть l m a x будет максимальной длиной слов в L , и пусть p в лемме прокачки будет l m a x + 1 . Лемма накачки справедлива, поскольку в L нет слов , длина которых ≥ l m a x + 1 .L Lм а х L п Lм а х+ 1 L ≥ лм а х+ 1
источник
Один из способов формализации основной части леммы о накачке заключается в следующем: :L≥ k= { w ∈ L ∣ | ш | ≥ k }
Для всех конечных и p > max { | ш | ∣ w ∈ L } , очевидно, что L ≥ p = ∅ . Поэтому (*) верно (слабо) для таких p .L p > max { | ш | | Ш ∈ L } L≥ р= ∅ п
источник