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 $A$ por uma sequência $\alpha$), não é necessário considerar os símbolos vizinhos de $A$. 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 $(3+5)\times 2$, onde os parênteses estão balanceados.

• A linguagem dos palíndromos, como $\{w{w}^R\mid w\in \{a,b{\}}^{\ast }\}$, onde $w^R$ é o inverso de $w$.

• A linguagem $\{a^n{b}^n\mid n\ge 0\}$, que contém palavras com o mesmo número de $a$s e $b$s, na ordem (ex.: "", “ab”, “aabb”, “aaabbb”).

Exemplo prático

Vamos considerar a linguagem $\{a^n{b}^n\mid n\ge 0\}$. Uma gramática livre de contexto para essa linguagem é:

• Variáveis: $\{S\}$
• Terminais: $\{a,b\}$
• Símbolo inicial: $S$
• Regras:

$$S\to aSb\mid ϵ$$

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

• Para $n=0$: $S\to ϵ$ (palavra vazia).
• Para $n=1$: $S\to aSb\to ab$.
• Para $n=2$: $S\to aSb\to aaSbb\to aabb$.

Essa gramática gera todas as palavras da forma $a^n{b}^n$, e como é livre de contexto, a linguagem também é.

Limitações

Nem todas as linguagens são livres de contexto. Por exemplo, a linguagem $\{a^n{b}^n{c}^n\mid n\ge 0\}$ (com o mesmo número de $a$, $b$, e $c$) 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