Lema
E se L é uma linguagem livre de contexto, há um comprimento de bombeamento p de modo que qualquer corda w ∈ L de comprimento ≥ p pode ser escrito como w = uvxyz, Onde vy ≠ ε, |vxy| ≤ p, e para todos i ≥ 0, uvixyiz ∈ L.
Aplicações do Lema de Bombeamento
O lema do bombeamento é usado para verificar se uma gramática está livre de contexto ou não. Vamos dar um exemplo e mostrar como ele é verificado.
Problema
Descubra se o idioma L = {xnynzn | n ≥ 1} é livre de contexto ou não.
Solução
Deixei Lé livre de contexto. Então,L deve satisfazer o lema do bombeamento.
Primeiro, escolha um número ndo lema do bombeamento. Então, considere z como 0 n 1 n 2 n .
Pausa z para dentro uvwxy, Onde
|vwx| ≤ n and vx ≠ ε.
Conseqüentemente vwxnão pode envolver 0s e 2s, uma vez que o último 0 e os primeiros 2 estão separados por pelo menos (n + 1) posições. Existem dois casos -
Case 1 - vwxnão tem 2s. Entãovxtem apenas 0s e 1s. Entãouwy, que teria que estar em L, tem n 2s, mas menos do que n 0s ou 1s.
Case 2 - vwx não tem 0s.
Aqui ocorre contradição.
Conseqüentemente, L não é uma linguagem livre de contexto.