Oi pessoal,
Um colega de vocês me relatou dificuldades em fazer demonstrações usando o lema do bombeamento, e também vi na última lista que muitos se embolaram com muitos casos para tratar.
Então fica uma dica bem básica (o prof. Arnaldo deve ter falado isso em sala mas poucos se ligaram): escolham uma palavra que simplifique as coisas, que no fim faça com que vocês tenham menos casos.
Outra coisa que eu acho que simplifica (embora nem todo mundo goste) é você pensar na contrapositiva do lema. Para o caso regular, por exemplo, fica:
"Seja L uma linguagem. Se para todo n > 0, existir uma palavra x em L de tamanho >= n tal que toda decomposição x = uvw com |uv| <= n e |v| > 0 é tal que existe i >= 0 tal que uv^(i)w não está em L, então L não é regular."
Nesse caso não precisa fazer prova por contradição, é uma prova direta.
[]s,
Murilo
Fórum