Linguagem livre de contexto §

---

Uma linguagem livre de contexto é uma linguagem formal que pode ser descrita por uma gramática livre de contexto.

Uma linguagem é livre de contexto se todas as suas palavras podem ser geradas por uma gramática desse tipo.

Características §

• Livre de contexto: O termo “livre de contexto” significa que, ao aplicar uma regra de produção (por exemplo, substituir uma variável por uma sequência ), não é necessário considerar os símbolos vizinhos de . Isso diferencia as gramáticas livres de contexto das gramáticas sensíveis ao contexto, onde as regras dependem do contexto em que a variável aparece.

• Reconhecida por autômatos: Toda linguagem livre de contexto pode ser reconhecida por um autômato de pilha (pushdown automaton, PDA), que é um modelo computacional mais poderoso que os autômatos finitos, mas menos poderoso que as máquinas de Turing.

Exemplos Conhecidos §

• A linguagem das expressões aritméticas bem formadas, como , onde os parênteses estão balanceados.

• A linguagem dos palíndromos, como , onde é o inverso de .

• A linguagem , que contém palavras com o mesmo número de s e s, na ordem (ex.: "", “ab”, “aabb”, “aaabbb”).

Exemplo prático §

Vamos considerar a linguagem . Uma gramática livre de contexto para essa linguagem é:

• Variáveis:
• Terminais:
• Símbolo inicial:
• Regras:

Aqui, representa a palavra vazia. Vamos derivar algumas palavras:

• Para : (palavra vazia).
• Para : .
• Para : .

Essa gramática gera todas as palavras da forma , e como é livre de contexto, a linguagem também é.

Limitações §

Nem todas as linguagens são livres de contexto. Por exemplo, a linguagem (com o mesmo número de , , e ) não é livre de contexto, porque exige rastrear três contagens simultaneamente, o que está além da capacidade de um autômato de pilha.

Note

Isso pode ser comprovado usando o Lema do Bombeamento para linguagens livres de contexto.

Referências §

---

Linguagens Formais e Autômatos 16-04-2025