Linguagem livre de contexto

Na teoria de linguagens formais, uma linguagem livre de contexto (LLC) é uma linguagem gerada por alguma gramática livre de contexto (GLC). Diferentes gramáticas livres de contexto podem gerar a mesma linguagem livre de contexto, ou, inversamente, uma dada linguagem livre de contexto pode ser gerada por diferentes gramáticas livres de contexto. É importante distinguir as propriedades da linguagem (propriedades intrínsecas) de propriedades de uma gramática específica (propriedades extrínsecas).

O conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas por um autômato de pilha,^[1] o que faz com que essas linguagens sejam passíveis de análise. Na verdade, dada uma GLC, há uma maneira direta para produzir um autômato com pilha para a gramática (e linguagem correspondente), mas indo para o outro lado (produzindo uma gramática dado um autômato) não é tão direta.

Aplicações

Tais linguagens são importantes para definir linguagens de programação.^[1] Por exemplo, as linguagens que requerem o balanceamento de parênteses são geradas pela gramática ${\displaystyle 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 é ${\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}$, a linguagem de todas as cadeias de caracteres não vazias de tamanho par, a primeira metade sempre preenchida com "${\displaystyle a}$"s e a segunda metade sempre preenchida com "${\displaystyle b}$"s. ${\displaystyle L}$ é gerada pela gramática ${\displaystyle S\to aSb~|~ab}$, e é aceita pelo autômato de pilha ${\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},\{q_{f}\})}$, em que ${\displaystyle \delta }$ é definido da seguinte forma:

${\displaystyle \delta (q_{0},a,z)=(q_{0},a)}$
${\displaystyle \delta (q_{0},a,a)=(q_{0},a)}$
${\displaystyle \delta (q_{0},b,a)=(q_{1},x)}$
${\displaystyle \delta (q_{1},b,a)=(q_{1},x)}$
${\displaystyle \delta (q_{1},b,z)=(q_{f},z)}$

${\displaystyle \delta (estado_{1},leitura,desempilha)=(estado_{2},empilha)}$

Onde z é o símbolo inicial da pilha e x significa desempilhar.

LLCs não ambíguas são um subconjunto próprio de todos os LLCs: há LLCs inerentemente ambíguas. Um exemplo de uma LLC inerentemente ambígua é a união de ${\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\}}$ com ${\displaystyle \{a^{n}b^{n}c^{m}d^{m}|n,m>0\}}$. Este conjunto é livre de contexto, uma vez que a união de duas linguagens livres de contexto é sempre livre de contexto. Mas não há nenhuma maneira de transformar de forma não ambígua cadeias no subconjunto (não-livre-contexto) ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}$ que é a interseção dessas duas linguagens.^[2]

Linguagens não livres de contexto

O conjunto ${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}$ é uma Linguagem sensível ao contexto, mas não existe uma gramática livre de contexto gerando essa linguagem. ^[2] Então existem linguagens sensíveis ao contexto que não são livres de contexto. Para provar que uma determinada linguagem não é livre de contexto, pode-se empregar o Lema do bombeamento para linguagens livres de contexto ou uma série de outros métodos, como o Lema de Ogden ou Teorema de Parikh.^[3]

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:^[4] OI

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

Linguagens livres de contexto não são fechadas sob complemento, interseção ou diferença. No entanto, se L é uma linguagem livre de contexto e D é uma linguagem regular, então tanto a sua interseção ${\displaystyle L\cap D}$ e sua diferença ${\displaystyle L\setminus D}$ são linguagens livres de contexto.

Não fechamento dentro de interseção e complemento

As linguagens livres de contexto não são fechadas sob interseção. Isto pode ser visto tomando as linguagens ${\displaystyle A=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}}$ e ${\displaystyle B=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}}$, que são ambos livre de contexto.^[6] A interseção é ${\displaystyle A\cap B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}}$, que pode ser mostrado como sendo não livre do contexto pelo Lema do bombeamento para linguagens livres de contexto.

Linguagens livres de contexto também não estão fechadas sob complementação, como para qualquer linguagem de A e B: ${\displaystyle A\cap B={\overline {{\overline {A}}\cup {\overline {B}}}}}$.

Propriedades de decisão

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

• Equivalência: Dadas duas gramáticas livres de contexto A e B, é ${\displaystyle L(A)=L(B)}$?
• Intersecção vazia: Dadas duas gramáticas livres de contexto A e B, é ${\displaystyle L(A)\cap L(B)=\emptyset }$ ? No entanto, a intersecção entre uma linguagem livre de contexto e uma linguagem regular é livre de contexto, e a variante do problema onde B é uma gramática regular, é decidível.
• Contenção: Dada uma gramática livre de contexto A, é ${\displaystyle L(A)\subseteq L(B)}$ ? Mais uma vez, a variante do problema em que B é uma gramática regular é decidível.
• Universalidade: Dada uma gramática livre de contexto A, é ${\displaystyle L(A)=\Sigma ^{*}}$ ?

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

• Vacuidade: Dada uma gramática livre de contexto A, é ${\displaystyle L(A)=\emptyset }$ ?
• Finitude: Dada uma gramática livre de contexto A, ${\displaystyle L(A)}$ é finito?
• Composição: Dada uma gramática livre de contexto G, e uma palavra ${\displaystyle w}$, então ${\displaystyle w\in L(G)}$ ? Algoritmos eficientes em tempo polinomial para o problema de composição são o Algoritmo CYK e Algoritmo Earley.

Análise sintática

Determinar uma instância do problema da composição, ou seja, dada uma cadeia ${\displaystyle w}$, determinar se ${\displaystyle w\in L(G)}$ onde ${\displaystyle L}$ é a linguagem gerada por alguma gramática ${\displaystyle G}$, também é conhecido como Análise sintática (computação).

Formalmente, o conjunto de todas as linguagens livres de contexto é idêntico ao conjunto de linguagens aceitas por autômato com pilha (AP). Algoritmos de análise sintática para linguagens livres de contexto incluem o Algoritmo CYK e o Algoritmo Earley.

Uma subclasse especial de linguagens livres de contexto é a Linguagem livre de contexto determinística, que é definida como o conjunto de linguagens aceitas por um Autômato com pilha determinístico e pode ser analisado por um Analisador sintático LR.^[7]

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 ${\displaystyle uv^{i}xy^{i}z}$ ∈ L

Teoria da computação

Teoria de autômatos: linguagem formal e gramática formal
Hierarquia Chomsky	Gramática	Linguagem	Reconhecedor
Tipo-0	Irrestrita	Recursivamente enumerável	Máquina de Turing
--	--	Recursiva	Máquina de Turing que sempre para
Tipo-1	Sensível ao contexto	Sensível ao contexto	Autômato linearmente limitado
Tipo-2	Livre de contexto	Livre de contexto	Autômato com pilha
Tipo-3	Regular	Regular	Autômato finito

Ver também

• Formalismo de Backus-Naur

Referências

1. David Déharbe (2003). «Gramáticas livres de contexto» (PDF). Universidade Federal do Rio Grande do Norte. Consultado em 23 de agosto de 2008. Arquivado do original (PDF) em 23 de março de 2005
2. Hopcroft & Ullman 1979.
3. How to prove that a language is not context-free?
4. «CS 273: Closure Properties for Context-Free Languages» (em inglês). Universidade de Illinois em Urbana-Champaign. Consultado em 23 de agosto de 2008
5. «Context-Free Grammar» (em inglês). Old Dominion University. Consultado em 23 de agosto de 2008
6. Uma gramática livre de contexto para a linguagem de A é dado pelas seguintes regras de produção, tendo S como o símbolo de início: S → Sc | aTb | ε; T → aTb | ε. A gramática para B é análoga.
7. Knuth, Donald E. (1 de dezembro de 1965). «On the translation of languages from left to right». Information and Control. 8 (6): 607-639. doi:10.1016/S0019-9958(65)90426-2