Lei do Bombeamento - Pumping Lemma

O que é?

• Lei do Bombeamento / Pumping Lemma = ferramenta teórica usada para provar que certas linguagens não são regulares
• não é um teste para provar que uma linguagem é regular, apenas que ela não pode ser

Enunciado - para linguagens regulares

• se uma linguagem L é regular, então existe um número inteiro p ≥ 1 - chamado de "constante de bombeamento" - tal que, para qualquer string s ∈ L com comprimento ∣s∣ ≥ p, a string s pode ser dividida em três partes:
  • s = x, y, z
• condições
  • ∣xy∣ ≤ p
  • ∣y∣ > 0
  • para todo i ≥ 0, a string xy^i z ∈ L

Intuição

• a ideia é que, como o autômato finito tem um número finito de estados, uma string suficientemente longa deve fazer com que o autômato repita algum estado
• Isso implica em um "ciclo" que pode ser "bombeado" e ainda resultar em uma string da linguagem.
• "bombear" = repetir arbitrariamente

Aplicação

• Etapas para provar que uma linguagem não é regular
• Supor que a linguagem é regular
• Usar a lei do bombeamento para encontrar uma contradição
• Mostrar que, para qualquer forma de dividir s = xyz, existe um i tal que xy^i z ∉ L

Exercícios Resolvidos

Exemplo 1

• Linguagem - L1 = {a^n b^n ∣ n ≥ 0}
• Prove que L1 não é regular.
• Solução...

1. Supor que L1 seja regular

• pelo Pumping Lemma, existe um inteiro p - constante de bombeamento - tal que qualquer string s ∈ L1 com ∣s∣ ≥ p pode ser dividida em s = xyz com
  • ∣xy∣ ≤ p
  • ∣y∣ > 0
  • para todo i ≥ 0, a string xy^i z ∈ L
  • ∀ i ≥ 0, x(y^i)z ∈ L1

2. Escolher uma string específica em L1 com ∣s∣ ≥ p

• s = a^p b^p

3. Dividir s = xyz, com ∣xy∣ ≤ p

• como os primeiros p caracteres são todos a, tanto x quanto y são só compostos por letras a
• portanto
  • x = a^k
  • y = a^l, com l > 0
  • z = a^(p-k-l) b^p

4. Aplicar i = 2

• x y^2 z = a^k a^2l a^(p−k−l) b^p = a^(p+l) b^p

1. Verificar se x y^2 z ∈ L1

• há p + l letras a e p letras b
  • ou seja, a quantidade de a's ≠ quantidade de b's ⇒
• x y^2 z ∉ L1

Conclusão

• contradição ⇒ a suposição de que L1 é regular está errada.
• Logo, L1 não é regular.

Exercício 2

• L2 = {a^n b^m ∣ n = 2m}

1. Supor que L2 seja regular

• supor que L2 é regular ⇒ existe um p tal que toda string s ∈ L2 com ∣s∣ ≥ p pode ser decomposta em xyz com as condições do Pumping Lemma
  • ∣xy∣ ≤ p
  • ∣y∣ > 0
  • para todo i ≥ 0, a string xy^i z ∈ L2
  • ∀ i ≥ 0, x(y^i)z ∈ L2

2. Escolher uma string específica

• no caso, escolher s = a^2p b^p ∈ L2, pois n = 2p, m = p

3. Dividir s = xyz, com ∣xy∣ ≤ p

• ∣xy∣ ≤ p, então x e y estão na parte de a's
• logo
  • x = a^k
  • y = a^l, com l > 0
  • z = a^(2p−k−l) b^p

4. Aplicar i=2

• x y^2 z = a^k a^2l a^(2p−k−l) b^p = a^(2p+l) b^p
• agora
  • número de a's = 2p + l
  • número de b's = p
  • ⇒ n ≠ 2mn ⇒ x y^2 z ∉ L2

Conclusão

• contradição ⇒ L2 não é regular

Exercício 3

• Linguagem L3 = {ww ∣ w ∈ {a,b}∗}
• ou seja - cadeias compostas por uma palavra repetida duas vezes
  • abab, aaaa, bb, abccabcc...

1. Supor que L3 é regular

• Pelo lema do bombeamento, existe um p tal que qualquer string com ∣s∣ ≥ p pode ser bombeada

2. Escolher string específica

• no caso, s = a^p b a^p b ∈ L3
• nessa string, w = a^p b, então ww = a^p b a^p b

3. Dividir s = xyz, com ∣xy∣ ≤ p

• como ∣xy∣ ≤ p, e os primeiros p símbolos são todos a, então
  • x = a^k
  • y = a^l, com l > 0
  • z = a^(p−k−l) b a^p b

4. Aplicar i = 2

• x y^2 z = a^k a^2l a^(p−k−l) b a^p b = a^(p+l) b a^p b
• agora, essa nova string não está na forma ww
  • a primeira metade agora tem mais a's que a segunda
• ⇒ x y^2 z ∉ L3

Conclusão

• contradição! ⇒ L3 não é regular

Exercícios Sugeridos

Lista

• Prove que as seguintes linguagens não são regulares usando o Pumping Lemma.

• L1 = {a^n b^n ∣ n ≥ 1}

• L2 = {a^p | p é primo}
• L3 = {a^n b^m ∣ n ≠ m}
• L4 = {a^n b^n c^k ∣ n, k ≥ 0}
• L5 = {a^(n^2) ∣ n ≥ 1}

Gabarito

• L1 = {a^n b^n ∣ n ≥ 1}
  • supor que L1 é regular
  • escolher s = a^p b^p ∈L1
  • como ∣xy∣ ≤ p, então y está só na parte de a's
  • bombeando y → número de a’s muda, número de b’s permanece → desequilíbrio → x y^i z ∉ L1
  • contradição ⇒ não regular
• L2 = {a^p | p é primo}
  • supor que L2 é regular
  • escolher s = a^q, com q primo grande ≥ p
  • bombear y com |y| = k > 0
  • para i = q + k, o número de a's deixa de ser primo
    • soma de múltiplos
  • portanto, x y^i z ∉ L2 para algum i
  • ⇒ contradição ⇒ não regular
• L3 = {a^n b^m ∣ n ≠ m}
  • Supor regular
  • o complemento {a^n b^n} ∪ {a^n b^m ∣ n,m ∈ N e n = m} seria regular
  • mas {a^n b^n} não é regular ⇒ complemento não regular ⇒ L3 não é regular.
  • solução alternativa = fazer prova direta com s = a^p b^p, que está fora da linguagem, e usar bombeamento levando para dentro
• L4 = {a^n b^n c^k ∣ n, k ≥ 0}
  • supor regular
  • escolher s = a^p b^p c^k
  • como ∣xy∣ ≤ p , então y está nos a’s
  • bombeando y → número de a’s muda, b’s e c’s não ⇒ desequilíbrio entre a’s e b’s ⇒ string fora da linguagem ⇒ L4 não regular
• L5 = {a^(n^2) ∣ n ≥ 1}
  • supor regular
  • escolher s = a^(p^2) ∈ L5
  • bombear y com |y| = k > 0
  • para i=2
    • x y^2 z = a^(p^2 + k)
    • mas p^2 + k não é necessariamente um quadrado perfeito ⇒ x y^i z ∉ L5
  • contradição ⇒ L5 não regular

---