Lema de bombeamento para idiomas regulares finitos simples

20

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:LpLwLppwxyzw

  1. | | ≥ 1y
  2. | | ≤xyp
  3. para todos ≥ 0, ∈ixyizL

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,babLab

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!yiy

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.yabab

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

Phil Wright
fonte

Respostas:

29

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.pLp

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 PpLpLLLp


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

Tocou.
fonte
2
Uma boa instância do conjunto vazio cumprindo -statements.
Raphael
7

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.LLL

De acordo com a wikipedia ( http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement ), o lema de bombeamento diz: (LΣ)(regular(L)((p1)((wL)((|w|p)((x,y,zΣ)(w=xyz(|y|1|xy|p(i0)(xyizL))))))))

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 + 1LlmaxLplmax+1Llmax+1

Wu Yin
fonte
2

Uma maneira de formalizar a parte principal do lema de bombeamento é esta, usando :Lk={wL|w|k}

Se é regular, existe para quep NLpN

wLp. x,y,z (*).

Por tudo finito e , temos obviamente que . Portanto (*) é (vacuamente) verdadeiro para tal .p > max { | w | | W L }Lp>max{|w|wL}pLp=p

Rafael
fonte