O lema de bombeamento para idiomas livres de contexto (CFLS) é uma ferramenta poderosa para provar que um determinado idioma não é * sem contexto. É uma prova da técnica de contradição. Aqui está o processo geral e as principais idéias:

1. Declare o lema de bombeamento (com cuidado!)

Antes de começar, é essencial entender a declaração do lema de bombeamento *exatamente *. Aqui está uma formulação comum:

bombear lema para CFLs:
Se l é uma linguagem sem contexto, existe um número inteiro *p *(o "comprimento do bombeamento") de modo que, para qualquer string *s *em l com comprimento maior ou igual a *p *(| s | ≥ *p *), *s *pode ser dividido em cinco substringas:*s =uvxyz *, satisfazendo as seguintes condições:

* | vxy | ≤ * p * (a parte do meio que está sendo bombeada não é muito longa)
* | vy | ≥ 1 (a seção bombeada não está vazia)
* Para todos * i * ≥ 0, * uv i xy i Z* também está em L (bombeando 'v' e 'y' qualquer número de vezes mantém a corda no idioma)

2. Suponha que o idioma * seja * sem contexto

Comece assumindo, por uma questão de contradição, que o idioma *l *você deseja provar é *não *sem contexto *é *, de fato, sem contexto. Esta é a suposição inicial de que você acabará por refutar.

3. Seja * p * o comprimento do bombeamento

Como você assumiu que * l * é livre de contexto, o lema de bombeamento * deve * se aplicar. Isso significa que existe um comprimento de bombeamento * P * (do qual você não conhece o valor exato). É crucial lembrar que o adversário (quem sabe que o idioma não é *sem contexto e está tentando enganá-lo) pode escolher *p *. Seu objetivo é encontrar uma corda que * não importa qual o valor de P * seja escolhido, as condições do lema de bombeamento levam a uma contradição.

4. Escolha uma string*s*∈*l*tal que |*s*| ≥ *p *

Esta é uma etapa crítica. Você deve selecionar cuidadosamente uma string *s *que pertence ao idioma *l *e tem um comprimento maior ou igual a *p *. A escolha de * s * é crucial para fazer a prova funcionar. Pense na estrutura das cordas em seu idioma e em como o bombeamento pode afetar essa estrutura. O objetivo é escolher uma corda cujas propriedades serão violadas quando 'V' e 'Y' forem bombeadas de uma maneira ditada pelo lema de bombeamento. Essa escolha *frequentemente *envolve a definição de algumas partes da string com base no valor *p *.

*Pense nas propriedades que fazem as cordas na linguagem pertencem a ela. Em seguida, escolha uma string de tal maneira que, quando qualquer sub-string for bombeada, pelo menos uma das restrições para a associação ao idioma é violada.*

5. Considere todas as decomposições possíveis * s =uvxyz * satisfazendo | vxy | ≤ * p * e | vy | ≥ 1

O lema de bombeamento afirma que*qualquer*string*s*com |*s*| ≥ * p * pode ser dividido dessa maneira. Então, * seu adversário * escolhe como * s * é dividido em * uvxyz * (sujeito às restrições | vxy | ≤ * p * e | vy | ≥ 1). No entanto, você considera todas essas divisões possíveis. Você precisa mostrar que *não importa como *o adversário escolher *u *, *v *, *x *, *y *e *z *, você pode bombear a corda para obter uma contradição.

Freqüentemente, isso envolve considerar diferentes casos * *com base em onde *v *e *y *poderia potencialmente se enquadrar na string *s *. Para cada caso, você analisará o que acontece quando bombear *v *e *y *.

6. Mostre isso para alguns *i *≥ 0, a string *uv i xy i z * não é * * em * l *

Este é o núcleo da contradição. Para cada caso considerado na etapa 5, você deve mostrar que existe alguns *i *(geralmente *i *=0 ou *i *=2, mas às vezes outros valores são necessários) de modo que a string resultante *uv i xy i Z*não é**no idioma*l*. Isso significa que viola as regras que definem cordas pertencentes ao idioma.

* como mostrar * uv eu xy i z * não está em * l *:Isso dependerá do idioma específico. Você precisará demonstrar que a corda bombeada viola as propriedades definidoras de *l *. As estratégias comuns incluem:

* mostrando que a string agora tem um número desigual de símbolos que eram antes iguais. Por exemplo, se * l * requer o mesmo número de 'A e' B, você mostra que o bombeamento faz com que a contagem seja desigual.
* mostrando que a ordem dos símbolos está agora incorreta. Por exemplo, se * l * exigir todos os 'A's para chegar antes de todos os' B, você mostra que o bombeamento pode colocar um 'b' antes de um 'a'.
* mostrando que uma relação matemática entre as contagens não mantém mais. Por exemplo, se * l * exigir que o número de 'A seja o dobro do número de' B, você mostra que o bombeamento viola esse relacionamento.

7. Conclua que * l * não * não * sem contexto

Como você mostrou que a suposição de que * l * é livre de contexto leva a uma contradição (o lema de bombeamento deve manter, mas você mostrou um caso em que não), você pode concluir que sua suposição inicial era falsa. Portanto, * l * não é uma linguagem sem contexto.

Exemplo:a linguagem l ={a n B n c n | n ≥ 0}

Vamos provar que * l * ={a n B n c n | n ≥ 0} não está livre de contexto usando o lema de bombeamento.

1. assume * l * é livre de contexto.

2. Vamos * P * o comprimento do bombeamento garantido pelo lema de bombeamento.

3. Escolha uma string *s *: Seja*s*=a *p* b *p* c *p* . Claramente,*s*∈*l*e |*s*| =3*p*≥*p*.

4. Considere todas as divisões possíveis * s =uvxyz * tal que | vxy | ≤ * p * e | vy | ≥ 1: Precisamos considerar onde as substringas *v *e *y *podem ser localizadas dentro de *s *. A restrição crucial é que | vxy | ≤ *p *. Isso limita significativamente as possibilidades:

* Caso 1:* vxy * consiste apenas em 'a's. Então * v * =a j e * y * =a k Para alguns*j*,*k*≥ 0 e*j + k*≥ 1. Se bombearmos (*i*=0), obtemos a string a *p-j-k* b *p* c *p* . Como * j + k * ≥ 1, essa corda tem menos de * p * 'a, mas ainda tem * p *' b's e * p * 'c's. Portanto, não está em *l *.

* Caso 2:* vxy * consiste apenas em 'B's. Então * v * =b j e * y * =b k Para alguns*j*,*k*≥ 0 e*j + k*≥ 1. Se bombearmos (*i*=0), obtemos um *p* B *p-j-k* c *p* . Novamente, o número de 'B's é menor que *P *, enquanto os números de' A e 'C permanecem *P *, então não está em *l *.

* Caso 3:* vxy * consiste apenas em 'c's. Então * v * =c j e * y * =c k Para alguns*j*,*k*≥ 0 e*j + k*≥ 1. Se bombearmos (*i*=0), obtemos um *p* b *p* c *p-j-k* . O número de 'C's é menor que *P *, enquanto os números de' A e 'B permanecem *P *, então não está em *l *.

* Caso 4:* Vxy * consiste em 'A e' B's. Desde | vxy | ≤ *p *, ele não pode incluir nenhum 'c's porque todos os *p *' a's e *p *'b's devem preceder qualquer "c's. Desde | vy | ≥ 1, pelo menos um de * v * ou * y * deve conter um caractere. Portanto * v * =a j B k e * y * =a l b m para alguns *j *, *k *, *l *, *m *≥ 0 e *j + k + l + m *≥ 1, com pelo menos um de 'a' ou 'b' em *v *ou *y *.

Se bombearmos (*i*=2), obtemos a string a *p+j+l* b *p+k+m* c *p* . Se * k + m * for zero (então * v * e * y * contém apenas 'a's) o número de' A aumenta, mas o número de 'B permanece o mesmo. O resultado é um *p+j+l* b *p* c *p* que não está mais no idioma. Se * j + l * for zero (então * v * e * y * contém apenas 'b's), o número de' b's aumenta, mas o número de 'A permanece o mesmo. O resultado é um *p* b *p+k+m* c *p* que não está mais no idioma. Se ambos *k+m *e *j+l *forem maiores que zero, então *uv 2 xy 2 Z* tem mais 'A e' B do que 'C, o que significa que não pode ser da forma A n B n c n .

* Caso 5:* vxy * consiste em 'B e' C's. Isso é simétrico para o caso 4. Novamente, a bombeação resultará em uma string que não está no idioma.

5. contradição: Em todos os casos possíveis, mostramos que existe um *i *tal que *uv i xy i Z*não está em*l*. Isso contradiz o lema de bombeamento.

6. Conclusão: Portanto, nossa suposição inicial de que * l * está livre de contexto deve ser falsa. Assim, * l * ={a n B n c n | n ≥ 0} não está livre de contexto.

Dicas de chave para usar o lema de bombeamento:

* Entenda o lema com precisão: Conheça a declaração e as condições exatas.
* Escolha estratégica de string: A escolha de * s * é crucial. Escolha uma string que destaque a propriedade que você deseja romper com o bombeamento. Freqüentemente, definir partes da string com base em * p * é útil.
* Análise de caso cuidadosa: Considere todos os locais possíveis para *v *e *y *dentro *s *, dadas as restrições | vxy | ≤ * p * e | vy | ≥ 1.
* Escolha a direita * i *:Experimente com *i *=0, *i *=2, ou outros valores para encontrar o que mais claramente demonstra a violação de *l *. Às vezes * i * =0 faz com que algo desapareça e * i * =2 fará com que algo seja duplicado.
* Seja claro e rigoroso: Explique exatamente por que a corda bombeada não está mais em *l *. Consulte as propriedades definidoras do idioma.

O lema de bombeamento pode ser complicado de dominar. Pratique com diferentes idiomas para obter experiência na escolha de sequências apropriadas e no manuseio da análise de casos. Lembre -se de que o objetivo é encontrar uma string em que * qualquer aplicação possível do lema de bombeamento leve a uma contradição. Boa sorte!