CCT-UFCA/Ciência da Computação/Autômatos e Linguagens Formais/Lema do Bombeamento das LLCs

O lema do bombeamento para linguagens livres-de-contexto é uma propriedade que garante que se uma linguagem não tem ela, logo a linguagem não é livre-de-contexto, mas não garante que ela será livre-de-contexto caso ela tenha. Precisaremos mostrar um AP ou GLC que aceite tal linguagem para que ela seja livre-de-contexto.

Lema

Se L é uma LLC, então existe um número p (comprimento do bombeamento) tal que toda cadeia w ∈ L com |w| ≥ p pode ser escrita da forma w = uvxyz em que

para todo i ≥ 0, uvⁱxyⁱz ∈ L.
|vy| > 0;
|vxy| ≤ p.

Demonstração

Ideia: Seja A uma LLC e G uma GLC que a gera. Devemos mostrar que podemos bombear qualquer cadeia suficientemente longa s em A. Logo, seja s uma cadeia muito longa em A. Devido ao fato de que está em A, ela é derivável de G e portanto tem uma árvore sintática. A árvore sintática para s tem que ser muito alta porque s é muito longa. Ou seja, a árvore sintática tem que conter algum caminho longo da variável inicial na raiz da árvore para um dos símbolos terminais em uma folha. Sobre esse caminho longo algum símbolo da variável R deve se repetir devido ao princípio da casa-de-pombos. Essa repetição nos permite substituir a subárvore embaixo da segunda ocorrência de R pela subárvore embaixo da primeira ocorrência de R e ainda obter uma árvore sintática legal. Por conseguinte podemos cortar s em cinco pedaços uvxyz e podemos repetir o segundo e o quarto pedaços e obter uma cadeia ainda na linguagem. Em outras palavras, uvⁱxyⁱz está em A para qualquer i ≥ 0.

Prova: Seja G uma GLC a LLC A. Seja b o número máximo de símbolos no lado de direito de uma regra. Podemos assumir que b ≥ 2. Em qualquer árvore sintática usando essa gramática sabemos que um nó não pode ter mais que b filhos. Em outras palavras no máximo b folhas estão 1 passo da variável inicial; no maximo b² folhas estão a no máximo 2 passos da variável inicial; e no máximo b^h folhas estão a no máximo h passos da variável inicial. Portanto, se a altura da árvore sintática é no máximo h, o comprimento da cadeia gerada é no máximo b^h.

Seja |V| o número de variáveis em G. Fazemos p ser b^|V|+2. Devido ao fato de que b ≥ 2, sabemos que p > b^|V|+1, portanto uma árvore sintática para qualquer cadeia em A de comprimento pelo menos p requer altura no mínimo |V| + 2.

Suponha que s seja uma cadeia em A de comprimento no mínimo p. Agora mostramos como bombear s. Seja τ a árvore sintática para s. Se s tem várias árvores sintáticas, escolhemos τ como sendo a árvore sintática que tem o menor número de nós. Como |s| >= p, sabemos que τ tem altura no mínimo |V| + 2, portanto o caminho mais longo em τ tem comprimento pelo menos |V| + 2. Esse caminho tem que ter pelo menos |V|+1 variáveis porque somente a folha é um terminal. Como G tendo somente |V| variáveis, alguma variável R aparece mais que uma vez no caminho. Por conveniência mais adiante, selecionamos R como sendo a variável que se repete entre as |V|+1 variáveis mais baixas nesse caminho.

Dividimos s em uvxyz. Cada ocorrência de R tem uma subárvore sob ela, gerando uma parte da cadeia s. A ocorrência mais superior de R tem uma subárvore maior e gera vxy, enquanto que a ocorrência mais inferior gera somente x como uma subárvore menor. Ambas essas subárvores são geradas pela mesma variável, portanto podemos substituir uma pela outra e ainda assim obter uma árvore sintática válida. Substituindo a menor pela maior repetidamente dá árvores sintáticas para as cadeias uvⁱxyⁱz a cada i > 1. Substituindo a maior pela menor gerada a cadeia uxz. Isso estabelece a condição 1 do tema.

Para obter a condição 2, temos que assegurar que ambas v e y não são ε. Se fossem, a árvore sintática obtida substituindo-se a menor subárvore pela maior teria menos nós que τ tem e ainda geraria s. Esse resultado não é possível porque já tínhamos escolhido τ como sendo uma árvore sintática para s com o menor número de nós. Essa é a razão para se selecionar τ dessa maneira.

De modo a obter a condição 3 precisamos nos assegurar de que vxy tem comprimento no máximo p. Na árvore sintática para s a ocorrência mais superior de R gera vxy. Escolhemos R de modo que ambas as ocorrências estejam entre as |V| + 1 variáveis de baixo no caminho, e escolhemos o caminho mais longo na árvore sintática, portanto a subárvore onde R gera vxy tem altura no máximo |V| + 2. Uma árvore dessa altura pode gerar uma cadeia de comprimento no máximo b^|V|+2 = p.

Exemplos

Vamos usar o lema do bombeamento para mostrar que a linguagem L = {aⁿbⁿcⁿ | n ≥ 0} é não-livre-de-contexto.

Assumimos que L é uma LLC e obtemos uma contradição. Seja p o comprimento de bombeamento para L que é garantido existir pelo lema do bombeamento. Selecione a cadeia s = a^pb^pc^p. Claramente s é um membro de L e de comprimento pelo menos p. O lema do bombeamento enuncia que s pode ser bombeada, mas mostramos que ela não pode. Em outras palavras, mostramos que independentemente de como dividimos s em uvxyz, uma das 3 condições do lema é violada. Vamos verificar isso para a primeira e terceira condições.

1) Quando tanto v quanto y contêm somente um tipo de símbolos do alfabeto, v não contém ambos a's e b's ou ambos b's e c's, e o mesmo se verifica para y. Nesse caos a cadeia uv²xy²z não pode conter igual número de a's, b's e c's. Por conseguinte ela não pode ser um membro de L. Isso viola a condição 1 do lema e é portanto uma contradição.

2) Quando v ou y contém mais que um tipo de símbolo uv²xy²z pod conter iguais números dos três símbolos do alfabeto mas não contê-los-á na ordem correta. Daí ela não pode ser um membro de L e uma contradição ocorre.