O lema de bombeamento para idiomas livres de contexto é uma ferramenta poderosa para provar que um idioma * não é * sem contexto. Funciona por contradição:assumimos que o idioma * é * sem contexto, depois mostramos que essa suposição leva a uma contradição. Veja como é aplicado, juntamente com exemplos:
O lema de bombeamento (para CFLs): Se L é uma linguagem sem contexto, existe uma constante * p * (o comprimento do bombeamento) de modo que qualquer string * w * em l com | w | ≥ *p *pode ser escrito como *w =uvxyz *, onde:
1. | Vxy | ≤ *p *
2. | Vy | ≥ 1
3. Para todos *i *≥ 0, *uv
i
xy
i
Z* está em L.
A estratégia de prova é encontrar uma string *W *no idioma de tal forma que, não importa como a decomponhamos em *uvxyz *satisfazendo as condições do lema, bombeando -o (aumentando *i *) produzirá uma corda que não *não *no idioma. Isso contradiz o lema, provando que o idioma não é livre de contexto.
Exemplos: Vamos ilustrar com alguns exemplos de idiomas e como provar que eles não estão sem contexto usando o lema de bombeamento:
1. L₁ ={a
n
B
n
c
n
| n ≥ 0} 1.
suponha que L₁ esteja livre de contexto. Isso significa que o lema de bombeamento se aplica.
2.
Escolha uma string w: Vamos escolher *w =a
p
b
p
c
p
*, onde *p *é o comprimento do bombeamento. | W | ≥ *p *.
3.
bombeamento: Porque | vxy | ≤ *p *, *vxy *pode abranger no máximo duas das seções (aaa ... bbb ... ccc ...). Existem três possibilidades:
*
vxy contém apenas a's e b's: O bombeamento alterará o número de A e/ou B sem alterar o número de C's, resultando em uma string não em L₁.
*
vxy contém apenas B e C's: Semelhante ao acima, o número de B e/ou C's mudará desproporcionalmente.
*
vxy contém apenas A's: O bombeamento afetará apenas o número de A's.
4.
contradição: Em todos os casos, o bombeamento produz uma corda não em L₁. Isso contradiz a afirmação do lema de bombeamento de que *uv
eu
xy
i
Z* está em l₁ para todos* i* ≥ 0.
5.
Conclusão: Portanto, L₁ não está livre de contexto.
2. L₂ ={a
n
b
m
c
n+m
| n, m ≥ 0} 1.
suponha que L₂ esteja livre de contexto. 2.
Escolha uma string w: Vamos *w =a
p
b
p
c
2p
*.
3.
bombeamento: Novamente, | vxy | ≤ *p *. As possibilidades são semelhantes a L₁:se * vxy * contiver apenas A e B, o bombeamento alterará o número de A e B sem alterar proporcionalmente o número de C's.
4.
contradição: O bombeamento levará a cordas não em L₂.
5.
Conclusão: L₂ não está livre de contexto.
3. L₃ ={ww | w ∈ {a, b}*} (A linguagem das cordas que são a concatenação de uma corda consigo mesmo)
1.
suponha que L₃ esteja livre de contexto. 2.
Escolha uma string w: Vamos *w =a
p
b
p
A
p
b
p
*.
3.
bombeamento: Porque | vxy | ≤ *p *, *vxy *não pode atravessar o meio da corda (não pode abranger as duas metades de `ww`). Se * vxy * estiver inteiramente no primeiro tempo, o bombeamento desequilibrará as duas metades.
4.
contradição: A corda bombeada não estará em L₃.
5.
Conclusão: L₃ não está livre de contexto.
Considerações importantes: *
Escolhendo a string certa *W *: Isso é crucial. A sequência deve ser cuidadosamente escolhida para explorar as limitações impostas por | vxy | ≤ *p *. Freqüentemente, as cordas com padrões repetidos são úteis.
*
lidar com todos os casos: Você deve considerar todas as maneiras possíveis de decompor * w * em * uvxyz * satisfazendo as condições do lema e mostrar que o bombeamento leva a uma contradição em cada caso.
*
O comprimento do bombeamento * p * é arbitrário: Você não precisa saber o valor de *p *; A prova funciona para qualquer *p *.
Ao aplicar cuidadosamente essas etapas, você pode usar o lema de bombeamento para mostrar que muitos idiomas não estão livres de contexto. Lembre-se de que o lema de bombeamento fornece apenas um método para provar idiomas * não * sem contexto; Não pode ser usado para provar que um idioma * é * sem contexto.
