Lema de bombeamento para idiomas regulares finitos simples

A Wikipedia tem a seguinte definição de lema de bombeamento para idiomas regulares ...

Seja uma linguagem regular. Existe então um número inteiro ≥ 1, dependendo apenas de modo que cada string em de comprimento pelo menos ( é chamado de "comprimento de bombeamento") possa ser escrita como = (ou seja, pode ser dividido em três substrings), satisfazendo as seguintes condições:$L$$p$$L$$w$$L$$p$$p$$w$$xyz$$w$

1. | | ≥ 1$y$
2. | | ≤$xy$$p$
3. para todos ≥ 0, ∈$i$$xy^iz$$L$

Não vejo como isso é satisfeito para uma linguagem regular finita simples. Se eu tenho um alfabeto de { } e a expressão regular então consiste em apenas a palavra que é seguida por . Agora quero ver se minha linguagem regular satisfaz o lema de bombeamento ...$a,b$$ab$$L$$a$$b$

Como nada se repete na minha expressão regular, o valor de deve estar vazio para que a condição 3 seja satisfeita para todos os . Mas, nesse caso, falha na condição 1, que diz que deve ter pelo menos 1 comprimento!$y$$i$$y$

Se, em vez disso, eu deixar ser , ou , ele satisfará a condição 1, mas falhará com a condição 3, porque na verdade nunca se repete.$y$$a$$b$$ab$

Obviamente, estou sentindo falta de algo mentalmente óbvio. Qual é?

Você está certo - não podemos permitir "bombear" palavras de um finito . O que está faltando é que o lema diz que existe um número , mas não nos diz o número.$L$$p$

Todas as palavras maiores que podem ser bombeadas pelo lema. Para um finito , isso acontece de modo que é maior do que o comprimento da palavra mais longa em . Assim, o lema é válido apenas de forma vaga e não pode ser aplicado a nenhuma palavra em , ou seja, qualquer palavra em não satisfaz a condição de "ter comprimento pelo menos ", conforme o lema exige.L p L L L $p$$L$$p$$L$$L$$L$$p$

Um corolário: se tem comprimento de bombeamento , e existe alguma palavra de comprimento pelo menos , então é infinito.p w ∈ L p $L$$p$$w\in L$$p$$L$

O lema de bombeamento geralmente é usado em idiomas infinitos, ou seja, idiomas que contêm um número infinito de palavras. Para qualquer idioma finito , como sempre pode ser aceito por um DFA com número finito de estado, deve ser regular.$L$$L$

De acordo com a wikipedia ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement ), o lema de bombeamento diz: $\begin{array}{l} (\forall L\subseteq \Sigma^*) \\ \quad (\mbox{regular}(L) \Rightarrow \\ \quad ((\exists p\geq 1) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\ \quad\quad ((\exists x,y,z \in \Sigma^*) (w=xyz \land (|y|\geq 1 \land |xy|\leq p \land (\forall i\geq 0)(xy^iz\in L)))))))) \end{array}$

Para qualquer idioma finito , seja o comprimento máximo das palavras em , e seja o lema de bombeamento . O lema de bombeamento é válido, pois não há palavras em cujo comprimento .G m um x L p l m um x + 1 L ≥ l m um x + $L$$l_{max}$$L$$p$$l_{max}+1$$L$$\geq l_{max}+1$

Uma maneira de formalizar a parte principal do lema de bombeamento é esta, usando :$L^{\geq k} = \{ w \in L \mid |w| \geq k\}$

Se é regular, existe para quep ∈ $L$$p \in \mathbb{N}$

$\qquad \displaystyle \forall w \in L^{\geq p}.\ \exists x,y,z \dots$ (*).

Por tudo finito e , temos obviamente que . Portanto (*) é (vacuamente) verdadeiro para tal .p > max { | w | | W ∈ L $L$$p > \max \{ |w| \mid w \in L\}$$L^{\geq p} = \emptyset$$p$