Linguagem livre de contexto

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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 S\to SS ~|~ (S) ~|~ \lambda. Da mesma forma, a maioria das expressões aritméticas é gerada por gramáticas livres de contexto.

Exemplos[editar | editar código-fonte]

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, a primeira metade sempre preenchida com "a"s e a segunda metade sempre preenchida com "b"s. L é gerada pela gramática S\to aSb ~|~ ab, e é aceita pelo autômato de pilha M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, \{q_f\}), em que \delta é definido da seguinte forma:

\delta(q_0, a, z) = (q_0, a)
\delta(q_0, a, a) = (q_0, a)
\delta(q_0, b, a) = (q_1, x)
\delta(q_1, b, a) = (q_1, x)
\delta(q_1, b, z) = (q_f, z)

\delta(estado_1, leitura, desempilha) = (estado_2, empilha)

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

LLCs não ambiguas 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 \{a^n b^m c^m d^n | n, m > 0\} com \{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 ambigua cadeias no subconjunto (não-livre-contexto) \{a^n b^n c^n d^n | n > 0\} que é a interseção dessas duas linguagens.[2]

Linguagens não livres de contexto[editar | editar código-fonte]

O conjunto \{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[editar | editar código-fonte]

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]

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 L\cap D e sua diferença L\setminus D são linguagens livres de contexto.

Não fechamento dentro de interseção e complemento[editar | editar código-fonte]

As linguagens livres de contexto não são fechadas sob interseção. Isto pode ser visto tomando as linguagens A = \{a^n b^n c^m \mid m, n \geq 0 \} and B = \{a^m b^n c^n \mid m,n \geq 0\}, que são ambos livre de contexto.[6] A interseção é 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: A \cap B = \overline{\overline{A} \cup \overline{B}} .

Propriedades de decisão[editar | editar código-fonte]

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, é L(A)=L(B)?
  • Intersecção vazia: Dadas duas gramáticas livres de contexto A e B, é 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, é 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, é 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, é L(A)=\emptyset ?
  • Finitude: Dada uma gramática livre de contexto A, L(A) é finito?
  • Composição: Dada uma gramática livre de contexto G, e uma palavra w, então 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[editar | editar código-fonte]

Determinar uma instância do problema da composição, ou seja, dada uma cdeia w, determinar se w \in L(G) onde L é a linguagem gerada por alguma gramática 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[editar | editar código-fonte]

Teorema da iteração para linguagens livre de contexto[editar | editar código-fonte]

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

Referências

  1. a b David Déharbe (2003). Gramáticas livres de contexto. Visitado em 23 de agosto de 2008.
  2. a b 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. Visitado em 23 de agosto de 2008.
  5. a b c Context-Free Grammar (em inglês) Old Dominion University. Visitado 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: SSc | aTb | ε; TaTb | ε. A gramática para B é análoga.
  7. doi:10.1016/S0019-9958(65)90426-2
    Esta citação será automaticamente completada em poucos minutos. Você pode furar a fila ou completar manualmente

Ver também[editar | editar código-fonte]

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