Linguagens Não-Regulares e
o Lema do Bombeamento
Já são conhecidas as Linguagens Regulare; mas
existem também as Linguagens que não são
Regulares…
Identificando Linguagens Não-Regulares
• Uma Linguagem Regular pode sempre ser definida por um AFD/AFND/AF-ε!
• Logo, para verificar se uma linguagem L é Não-Regular, torna-se necessário provar que
não existe um dessesautômatos que a reconheça!
• Problema: isso não é fácil de provar
• Solução: Lema do Bombeamento !!!
Lema do Bombeamento
Antes de formular o Lema do Bombeamento, vamos introduzir sua idéia básica através de
um exemplo:
• Seja o autômato (AFND) abaixo, com 4 estados.
• O autômato reconhece as seguintes palavras: (a,b,b); (babb); (b,a,b,b,b,b);(a,b,b,a,b) …
• Observe que para a palavra w=(a,b,b), nenhum estado é repetido!
• Para qualquer palavra w reconhecida, com |w| ≥ 4, existe algum estado repetido!
Lema do Bombeamento
• Generalizando: Num autômato com n estados, uma
w palavra reconhecida w, com |w| ≥ n, ou seja, o
número de transições entre o Estado Inicial e o
Final é maior ou igual ao número de estados do
referido autômato, então algum estado é repetido!
• Esse é conhecido como o princípio da casa de
pombos!
• O princípio da casa dos pombos refere-se à
afirmação de que se n pombos devem ser postos
em m casas, e se n > m, então pelo menos uma
casa irá conter mais de um pombo.
• É ainda conhecido como teorema de Dirichlet,
matemático que supostamente tenha citado o
primeiro relato deste princípio em 1834, com o
nome de Schubfachprinzip ("princípio das
gavetas").
• De maneira geral, se uma palavra submetida à entrada
Lema do de um autômato de n estados, possui comprimento
maior ou igual a n, certamente, pelo menos um estado
Bombeamento foi repetido!
Lema do
Bombeamento
• Seja L uma linguagem Regular Infinita, e um
autômato com m estados, que aceita L.
• Considere uma string w, com w Є L.
• Haverá, portanto, uma sequencia de
transições dos estados do autômato para
reconhecer w...
• Ou seja, se m é o número de estados e |w|≥ m, algum
Lema do estado q será repetido (bombeado)!
Bombeamento
Lema do Bombeamento
Considere w=xyz (fragmentação de W), onde:
• y é a parte repetida (bombeada);
• x é a parte inicial, antes da repetição;
• y a parte final, após a repetição;
• |xy| ≤ m, e
• y| > 0.
As palavras…
• w= xz é aceita;
• w= xyz é aceita;
• w= xyyz é aceita;
• w= xyiz é aceita, com i=(1,2,…)
w= xyiz é aceita, com i=(1,2,…)
Lema do Bombeamento
Descrição do Lema:
Dada uma linguagem regular infinita L, existe um inteiro m, tal que
para todo string w Є L, com |w| ≥ m, podemos escrever w=xyz, com
|xy| ≤ m, e |y| > 0, tal que w=xyiz, com i={1,2,…}.
• O Lema do Bombeamento é aplicado para verificar se determinada linguagem é
não-regular. Vejamos o seguinte exemplo:
• A linguagem L={anbn}, com n≥0, é regular?
Aplicação do Lema do Bombeamento – Exemplo 1
• Verificando a linguagem L={anbn}, com n≥0:
• Suponha, por contradição, que L é uma linguagem regular; Como L é infinita, podemos
aplicar o Lema do Bombeamento:
• Seja m o inteiro do Lema do Bombeamento (o número de estados de algum autômato
reconhecedor da linguagem). Tome um string w da linguagem (w Є L), com |w| ≥ m...
Por exemplo: w= ambm
Observe que a w segue o modelo da linguagem e seu comprimento é:
|ambm|= 2m;
Logo, obedece a restrição |w| ≥ m.
Aplicando o Lema do
Bombeamento (LB)
• Agora, vamos desmembrar a linguagem
especificada em três partes – xyz:
ambm =xyz
• Então pelo L.B., |xy| ≤ m, e |y| > 0:
• Pelo LB, xyiz Є L, com i = 0,1,2…; porém:
xy2z = xyyz = am+kbm
• Portanto, L é Não-Regular!
Exemplo 2
• A linguagem definida por L={wwR|w Є ∑*},
define as linguagens reversíveis sobre o alfabeto
∑.
• Para ∑={a,b}, as palavras w1=aabbaa e
w2=babbab pertencem à linguagem.
• Para provar por contradição, vamos supor que L
é regular e definir uma palavra pertencente à
linguagem, com |w| ≥ m; digamos:
w = a mb mb ma m
• Realizando a fragmentação sobre w, temos:
w = ambmbmam = xyz
• Bombeando Y, ou seja, para y2, com |y| > 0
teremos:
Exemplo 3
• A linguagem L={anblcn+l }, com n,l ≥ 0 é regular?
• São palavras dessa linguagem: w= abbccc e w=
aabbcccc, por exemplo.
• Para provar por contradição, supor uma palavra
com tamanho superior a m (do LB); consideremos
w= ambmc2m ; notadamente,|w| ≥ m.
• Fazendo o fracionamento...
ambmc2m = xyz.
• Bombeando Y (Y2), e |y| > 0, obtemos:
am+kbmc2m
• Logo, L não é regular!
Exemplo 4
• Considere a linguagem L={an!, n≥0}.
• Vamos supor L é regular;
• Tomando uma palavra w=am!; observe
que obedece a restrição w| ≥ m.
• Fracionando w, teremos:
am!=xyz
• Bombeando Y= a2k
• Obtemos am!+k
• Logo, L não é regular!