Existem várias maneiras de demonstrar que um idioma não é livre de contexto. Os métodos mais comuns dependem de provar que o idioma viola as propriedades inerentes aos idiomas livres de contexto (CFLS):
1. Lema de bombeamento para idiomas livres de contexto: Esta é a técnica mais amplamente usada. O lema de bombeamento afirma que, para qualquer CFL l, existe uma constante * p * (o comprimento do bombeamento) de modo que qualquer corda * w * em l com comprimento | W | ≥ *p *pode ser escrito como *uvxyz *, onde:
* | vxy | ≤ *p *
* | vy | ≥ 1
* * uv
i
xy
i
z* ∈ L para todos* i* ≥ 0
Para provar um idioma * não * sem contexto usando o lema de bombeamento:
1.
Suponha: Suponha, por uma questão de contradição, que o idioma * l * é livre de contexto.
2.
Escolha uma string: Selecione uma string *w *in *l *com comprimento pelo menos o comprimento do bombeamento *p *(você geralmente precisa escolher estrategicamente *W *).
3.
bombear a corda: Tente decompor * w * em * uvxyz * satisfazendo as condições do lema.
4.
Encontre uma contradição: Mostre isso para alguns *i *, *uv
eu
xy
i
Z*não é**em*l*. Isso contradiz o lema de bombeamento, provando que a suposição original (que * l * é livre de contexto) deve ser falsa.
Exemplo: Vamos considerar o idioma l ={a
n
B
n
c
n
| n ≥ 0}. Usando o lema de bombeamento:
1.
Suponha: L é livre de contexto.
2.
Escolha uma string: Seja * W * =a
p
b
p
c
p
(onde * p * é o comprimento do bombeamento).
3.
bombear a corda: Não importa como você decompõe *w *em *uvxyz *, o bombeamento inevitavelmente violará o
n
B
n
c
n
estrutura. Por exemplo, se * vxy * contiver apenas 'A's, o bombeamento aumentará o número de' A sem aumentar o número de 'B e' C. Problemas semelhantes surgem se * vxy * contém apenas 'b's ou' c's, ou uma mistura que não mantém a proporção igual.
4. contradição: Portanto, existe um *i *tal que *uv
eu
xy
i
Z* ∉ L, contradizendo o lema de bombeamento. Assim, L não está livre de contexto.
2. Propriedades de fechamento: Os idiomas livres de contexto são fechados sob certas operações (Union, Concatenation, Kleene Star, interseção com um idioma regular). Se você pode mostrar que um idioma * não está * fechado em uma dessas operações, não pode ser livre de contexto. Esse método é usado com menos frequência para prova direta do que o lema de bombeamento, mas pode ser útil em combinação com outras técnicas.
3. Lema de Ogden: Esta é uma versão mais poderosa do lema de bombeamento, permitindo que você escolha posições marcadas dentro da string *W *. É útil para idiomas em que o lema simples de bombeamento é difícil de aplicar.
4. Teorema de Parikh: Esse teorema se relaciona com o número de ocorrências de cada símbolo nas cordas de um idioma. Embora não seja usado diretamente para provar que uma linguagem * não é * sem contexto, às vezes pode ajudar a mostrar que a estrutura de um idioma é incompatível com as restrições impostas pelos CFLs. É frequentemente usado em conjunto com outras técnicas.
Em resumo, o lema de bombeamento é o método mais comum e geralmente eficaz para provar que um idioma não é livre de contexto. No entanto, a escolha do método depende da estrutura da linguagem específica e da facilidade com que cada técnica pode ser aplicada. O lema de Ogden oferece mais energia quando necessário, e as propriedades de fechamento podem fornecer evidências suplementares.
