Linguagem livre de contexto

Na teoria de linguagens formais, uma linguagem livre de contexto é uma linguagem gerada por alguma gramática livre de contexto. O conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas por um autômato de pilha. De acordo com a Hierarquia de Chomsky, linguagens livres de contexto são Tipo-2.

Aplicações

Tais linguagens são importantes para definir linguagens de programação. Por exemplo, as linguagens que requerem o balanceamento de parênteses são geradas pela gramática $S\to SS ~|~ (S) ~|~ \lambda$. Da mesma forma, a maioria das expressões aritméticas é gerada por gramáticas livres de contexto.

Exemplos

Uma linguagem livre de contexto é $L = \{a^nb^n:n\geq1\}$, a linguagem de todas as cadeias de caracteres não vazias de tamanho par, as primeiras metades sempre preenchidas com "a"s e as segundas metades sempre preenchidas com "b"s. L é gerada pela gramática $S\to aSb ~|~ ab$, e é aceita pelo autômato de pilha M = ({q₀,q₁,q_f},{a,b},{a,z},δ,q₀,{q_f}), em que δ é definido da seguinte forma:

δ(q₀,a,z) = (q₀,a)
δ(q₀,a,a) = (q₀,a)
δ(q₀,b,a) = (q₁,x)
δ(q₁,b,a) = (q₁,x)
δ(q₁,b,z) = (q_f,z)

δ(estado₁,leitura,desempilha) = (estado₂,empilha)

Em que z é a pilha de símbolos inicial e x significa desempilhar.

Propriedades de fechamento

Linguagens livres de contexto são fechadas nas seguintes operações. Se L e P são linguagens livres de contexto e D é uma linguagem regular, as seguintes linguagens também são livres de contexto:

• o fecho de Kleene L ^* de L
• a imagem φ(L) de L sob um homomorfismo φ
• a concatenação $L \circ P$ de L e P
• a união $L \cup P$ de L e P
• a interseção (com uma linguagem regular) $L \cap D$ de L e D

Linguagens livres de contexto não são fechadas em complemento, interseção ou diferença.

Propriedades de decisão

Os seguintes problemas são indecidíveis para quaisquer gramáticas livres de contexto A e B:

• L(A) = L(B)?
• $L(A) \cap L(B) = \emptyset$ ?
• L(A) = Σ ^*  ?
• $L(A) \subseteq L(B)$ ?

Os seguintes problemas são decidíveis para quaisquer linguagens livres de contexto:

• $L(A)=\emptyset$?
• L(A) é finito?
• Dada a palavra w, $w \in L(A)$?

Decidindo se uma linguagem é ou não livre de contexto

Teorema da iteração para linguagens livre de contexto

Se L é uma linguagem livre de contexto, então existe um n tal que para todo s ∈ L tal que |s| ≥ n, s pode ser reescrito da forma uvxyz, |vxy| > 0 e |vxy| ≤ n, tal que ∀ i, i ≥ 0 uvⁱxyⁱz ∈ L

Ver também

• Formalismo de Backus-Naur