Pesquisa · Mapa mental

Linguagem livre de contexto

Na teoria de linguagens formais, uma Linguagem Livre de Contexto (LLC) é definida por uma Gramática Livre de Contexto (GLC). É importante notar que diferentes GLCs podem gerar a mesma LLC, e uma mesma LLC pode ser gerada por diferentes GLCs. Por isso, devemos distinguir as propriedades da linguagem das propriedades de uma gramática específica.

Fonte: Wikipédia (pt)Texto didático por IAAtualizado em 25/07/2026

Pontos-chave

  • LLCs são geradas por Gramáticas Livres de Contexto (GLCs).
  • Diferentes GLCs podem gerar a mesma LLC.
  • LLCs são fundamentais para definir linguagens de programação e expressões aritméticas.
  • Nem toda linguagem sensível ao contexto é livre de contexto.
  • LLCs são fechadas sob união, concatenação e fecho de Kleene, mas não sob interseção e complemento.
01

Aplicações das LLCs

Imagem: Rodrigo Soldon Souza · BY-NC-ND · Openverse

As LLCs desempenham um papel crucial na definição de linguagens de programação. Por exemplo, a gramática S → SS | (S) | λ gera linguagens que exigem o balanceamento de parênteses. Da mesma forma, a maioria das expressões aritméticas é definida por meio de gramáticas livres de contexto.

02

Exemplo de LLC

Imagem: Rodrigo Soldon Souza · BY-NC-ND · Openverse

Considere a linguagem L = { aⁿbⁿ : n ≥ 1 }, que consiste em todas as cadeias de caracteres não vazias com a primeira metade preenchida por 'a' e a segunda metade por 'b', ambas de igual comprimento. Essa linguagem é gerada pela gramática S → aSb | ab e pode ser aceita por um autômato de pilha específico.

03

Linguagens Não Livres de Contexto

Imagem: Rodrigo Soldon Souza · BY-NC-ND · Openverse

O conjunto { aⁿbⁿcⁿdⁿ | n > 0 } é um exemplo de linguagem sensível ao contexto que não pode ser gerada por nenhuma gramática livre de contexto. Para provar que uma linguagem não é livre de contexto, podem ser utilizados o Lema do Bombeamento para LLCs, o Lema de Ogden ou o Teorema de Parikh.

04

Propriedades de Fechamento

Imagem: Rodrigo Soldon Souza · BY-NC-ND · Openverse

Linguagens Livres de Contexto são fechadas sob operações como união, concatenação e fecho de Kleene. Se L e P são LLCs e D é uma linguagem regular, então L ∪ P, L ⋅ P e L* também são LLCs. No entanto, LLCs não são fechadas sob complemento, interseção ou diferença. Contudo, a interseção de uma LLC com uma linguagem regular (L ∩ D) e a diferença (L ∖ D) resultam em LLCs.

Não Fechamento em Interseção e Complemento

Linguagens Livres de Contexto não são fechadas sob interseção. Por exemplo, as linguagens A = { aⁿbⁿcᵐ | m, n ≥ 0 } e B = { aᵐbⁿcⁿ | m, n ≥ 0 }, ambas livres de contexto, têm uma interseção A ∩ B = { aⁿbⁿcⁿ | n ≥ 0 } que não é livre de contexto. LLCs também não são fechadas sob complementação, o que pode ser demonstrado pela relação A ∩ B = ¬(¬A ∪ ¬B).

05

Propriedades de Decisão

Imagem: Rodrigo Soldon Souza · BY-NC-ND · Openverse

Existem problemas indecidíveis relacionados a gramáticas livres de contexto (como a equivalência entre duas GLCs). No entanto, outros problemas são decidíveis, como determinar se uma cadeia pertence a uma linguagem livre de contexto.

06

Análise Sintática (Parsing)

Imagem: Rodrigo Soldon Souza · BY-NC-ND · Openverse

O problema de determinar se uma cadeia 'w' pertence à linguagem L(G) gerada por uma gramática G é chamado de Análise Sintática. O conjunto de todas as LLCs é equivalente ao conjunto de linguagens aceitas por Autômatos com Pilha (AP). Algoritmos como CYK e Earley são usados para análise sintática de LLCs. Linguagens Livres de Contexto Determinísticas, aceitas por Autômatos com Pilha Determinísticos, podem ser analisadas por Analisadores LR.

07

Decidindo se uma Linguagem é LLC

Imagem: Rodrigo Soldon Souza · BY-NC-ND · Openverse

O Teorema da Iteração (ou Lema do Bombeamento) para Linguagens Livres de Contexto é uma ferramenta fundamental para provar se uma linguagem é ou não livre de contexto.

Teorema da Iteração para LLCs

Se L é uma Linguagem Livre de Contexto, então existe um número n tal que toda cadeia 's' em L com comprimento |s| ≥ n pode ser decomposta em s = uvxyz, onde |vxy| > 0 e |vxy| ≤ n. Para qualquer i ≥ 0, a cadeia uvⁱxyⁱz também pertence a L.

Vídeos recomendados

Fontes consultadas

Continue pesquisando