Gramática livre de contexto

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

Na teoria de linguagem formal, a gramatica livre de contexto (GLC) é uma gramática formal onde todas as regras de produções são da forma

A\ \to\ \alpha

Onde A é um símbolo não terminal, e \alpha  é uma cadeia de terminal e/ou não terminais (\alpha pode ser vazia). Uma linguagem formal é considerada “livre do contexto” quando suas regras de produções podem ser aplicadas independentemente do contexto do simbolo não terminal. Não importa quais símbolos existem na GLC, um único símbolo não terminal existente no lado esquerdo de uma regra pode sempre ser substituído pelo lado direito. E isso é o que distingue a GLC da gramática sensível ao contexto (GSC)

Essa gramática tem uma longa lista de palavras, e também regras sobre os tipos de palavras que podem ser adicionadas e em qual ordem. Normas superiores combina várias regras inferiores para fazer uma frase. Uma sentença pode ser gramaticalmente correta, mas pode não ter nenhum significado. Cada regra tem o seu próprio símbolo, o qual pode ser substituído com símbolos que representam as regras inferior, que podem ser substituídos com palavras.

Isso também pode ser feito na ordem inversa para verificar se uma frase é gramaticalmente correta.

Linguagens geradas por gramáticas livres de contexto são conhecidos como linguagens livres de contexto (LLC). Diferentes gramáticas livres de contexto podem gerar a mesma linguagem livre de contexto. O problema da igualdade de idioma (É possível fazer duas dadas gramáticas livres de contexto gerar a mesma língua?) É indecidível. 

Gramáticas livres de contexto surgiu da linguística, onde são utilizadas para descrever a estrutura das frases e palavras em linguagem natural, e elas foram, de fato, inventada pelo linguista Noam Chomsky para este fim,mas não foram utilizadas da maneira originalmente esperada. Em contrapartida, em ciência da computação, como o uso de conceitos recursivamente definidos aumentou, as GLCs foram usados mais e mais. As primeiras aplicações das gramáticas eram principalmente para descrever a estrutura de linguagens de programação. Uma aplicação mais recente, foi a utilização de GLC em uma parte essencial da Extensible Markup Language (XML) chamada de definição do tipo de documento.[1]

Na linguística, alguns autores usam o termo gramática de estrutura frasal para se referir a gramáticas livres de contexto, em que gramática de estrutura frasal são distintas das gramáticas de dependência. Na ciência da computação, uma notação popular para gramáticas livres de contexto é Formalismo de Backus-Naur, ou BNF

Antecedentes[editar | editar código-fonte]

Desde o tempo de Pāṇini, pelo menos, os linguistas têm descrito as gramáticas de línguas em termos de sua estrutura de blocos, e descrevendo como as sentenças são recursivamente construídos a partir de frases menores e, eventualmente, palavras individuais ou elementos nominativos. Uma propriedade essencial destas estruturas de bloco é que as unidades lógicas não se sobrepõem. Por exemplo, a frase:  João, cujo carro azul estava na garagem, andou para o supermercado.  pode ser logicamente entre parênteses, como se segue: (João, ((cujo carro azul) (estava (na garagem))), (andou (para (o supermercado)))). Uma gramática livre de contexto fornece um mecanismo simples e matematicamente preciso para descrever os métodos pelos quais algumas frases em linguagem natural são construídos a partir de blocos menores, capturando a "estrutura de blocos" de frases de uma forma natural. Sua simplicidade faz o formalismo passíveis de estudo matemático rigoroso. Características importantes da sintaxe da linguagem natural, como acordo e referência não fazem parte da gramática livre de contexto, mas a estrutura recursiva básica de frases, a maneira em que cláusulas se alinham dentro de outras cláusulas, e a maneira em que lista de adjetivos e advérbios são engolido por substantivos e verbos, é descrito precisamente.

O formalismo de gramáticas livres de contexto foi desenvolvido em meados dos anos 1950 por Noam Chomsky,[2] e também a sua classificação como um tipo especial de gramática formal (que ele chamou de Gramática de estrutura frasal)[3] . O que Chomsky chamou de Gramática de estrutura frasal também é conhecido como gramáticas constituintes. , em que gramáticas constituintes estão em contraste com gramáticas de dependência. No quadro Gramática gerativa de Chomsky, a sintaxe da linguagem natural foi descrito por regras livres de contexto combinados com regras de transformação.

Estrutura do bloco foi introduzido em linguagens de programação de computador pelo o projeto Algol (1957-1960), que, como consequência, também contou com uma gramática livre de contexto para descrever a sintaxe resultando do Algol. Isto tornou-se uma característica padrão das linguagens de computador, e a notação de gramáticas usados em descrições concretas de linguagens de computador veio a ser conhecido como Formalismo de Backus-Naur, em homenagem à dois membros do comitê de design de linguagem Algol [2] . O aspecto "estrutura de bloco" que gramáticas livres de contexto captura é fundamental à gramática em que os termos de sintaxe e a gramática são frequentemente identificados como as regras da gramática livre de contexto, especialmente em ciência da computação. Restrições formais não capturados pela gramática são então considerados a fazer parte da "semântica" da linguagem.

Gramáticas livres de contexto são simples o suficiente para permitir a construção de algoritmos de parsing eficientes que, para uma dada sequência de caracteres, determinar se e como ela pode ser gerada a partir da gramática. Um parsing Earley é um exemplo de tal algoritmo, enquanto os amplamente utilizados LR e LL parsing são algoritmos mais simples que lidam apenas com subconjuntos mais restritivos de gramáticas livres de contexto. 

Definições formais[editar | editar código-fonte]

A gramática livre de contexto é definida por uma 4-tuplas [4]

G = (V, \Sigma, R, S) onde :

  1. V é um conjunto finito; cada elemento  v\in V  é chamado de símbolo não terminal ou uma variável. Cada variável representa um tipo diferente de frase ou cláusula na sentença. As variáveis são também chamados de categorias sintáticas. Cada variável define uma sub-linguagem da linguagem definida por G.
  2. Σ é um conjunto finito de terminais, disjuntos de V,  que compõem o conteúdo real da sentença. O conjunto de terminais é o alfabeto da língua definido pela gramática G.
  3. R é uma relação finito de V para (V\cup\Sigma)^{*}, em que o asterisco representa a operação de fecho de Kleen. Os membros do R são chamadas as regras de reescrita ou produções da gramática (também comumente simbolizado por um P)
  4. S é a variável de início (ou símbolo inicial), usado para representar a frase inteira (ou programa). Ele deve ser um elemento de V.

Notação das Regras de Produção[editar | editar código-fonte]

A regra de produção em R é formalizada matematicamente como um par (\alpha, \beta)\in R, onde \alpha \in Vé um não terminal e \beta \in (V\cup\Sigma)^{*} é uma cadeia de variáveis e / ou terminais; ao invés de usar a notação par ordenado, regras de produção são geralmente escritos usando um operador seta com α como o seu lado esquerdo e  β como o seu lado direito: \alpha\rightarrow\beta.

É permitido que β seja a cadeia vazia, e, neste caso, é habitual designar pelo ε. A forma \alpha\rightarrow\varepsilon é chamada de uma ε-produção.[5]

É comum listar todos os lados direito para o mesmo lado esquerdo na mesma linha, utilizando | (o símbolo barra vertical ) para separá-los. Regras .\alpha\rightarrow \beta_1\alpha\rightarrow\beta_2, portanto, pode ser escrito como \alpha\rightarrow\beta_1\mid\beta_2. Neste caso,\beta_1\beta_2 são chamadas a primeira e segunda alternativa, respectivamente. 

Aplicação das Regras[editar | editar código-fonte]

Para quaisquer cadeias u, v\in (V\cup\Sigma)^{*}, dizemos que u produz diretamente v, escrevendo como  u\Rightarrow v\,, se \exists (\alpha, \beta)\in R sendo\alpha \in V and u_{1}, u_{2}\in (V\cup\Sigma)^{*} de forma que u\,=u_{1}\alpha u_{2}v\,=u_{1}\beta u_{2}. Assim, v é o resultado da aplicação da regra (\alpha, \beta) para u.

Aplicacão repetida de regras[editar | editar código-fonte]

Para quaisquer palavra u, v\in (V\cup\Sigma)^{*}, , dizemos u produz v, escrevendo como u\stackrel{*}{\Rightarrow} v (ou u\Rightarrow\Rightarrow v\, como em alguns livros didáticos ), se\exists k\geq 1\, \exists \, u_{1}, \cdots, u_{k}\in (V\cup\Sigma)^{*} de forma queu = \, u_{1} \Rightarrow u_{2} \Rightarrow \cdots \Rightarrow u_{k} \, = v. Neste caso, se k\geq 2 (i.e., u \neq v), a relaçãou\stackrel{+}{\Rightarrow} v mantém. Por outras palavras, (\stackrel{*}{\Rightarrow}) e(\stackrel{+}{\Rightarrow}) são o fechamento transitivo reflexivo(permitindo uma palavra para produzir a si mesma) e o Fecho transitivo (que requer, pelo menos, uma etapa ) de (\Rightarrow), respectivamente.

Linguagem livre de contexto[editar | editar código-fonte]

A linguagem de uma gramática G = (V, \Sigma, R, S) é o conjunto

L(G) = \{ w\in\Sigma^{*} : S\stackrel{*}{\Rightarrow} w\}

Uma linguagem L é dito ser uma linguagem livre de contexto (CFL), se existe uma GLC L, de tal modo que  L\,=\,L(G).

GLC adequadas[editar | editar código-fonte]

Uma gramática livre de contexto é dita ser adequada[6] , se tiver :

  • nenhum símbolos inalcançáveis:\forall N \in V: \exists \alpha,\beta \in (V\cup\Sigma)^*: S \stackrel{*}{\Rightarrow} \alpha{N}\beta
  • nenhum símbolos que não podem ser produzidos:\forall N \in V: \exists w \in \Sigma^*: N \stackrel{*}{\Rightarrow} w
  • nenhuma ε-produção \neg\exists N \in V: (N, \varepsilon) \in R
  • nenhum ciclo : \neg\exists N \in V: N \stackrel{+}{\Rightarrow} N

Em teoria da linguagem formal, equivalência fraca de duas gramáticas significa que elas geram o mesmo conjunto de cadeias, ou seja, que a linguagem formal que eles geram é o mesmo. Cada gramática livre de contexto pode ser transformada em uma fracamente equivalente sem símbolos inacessíveis[7] , uma fracamente equivalente sem símbolos improdutivos [8] , e uma fracamente equivalente sem ciclos[9] . Cada gramática livre de contexto que não possui produz ε pode ser transformada em uma fracamente equivalente sem ε-produções [10] ; Ao todo, cada tal gramática pode ser transformada em uma GLC adequada fracamente equivalente. 

Exemplo[editar | editar código-fonte]

A gramática G = (\{S\}, \{a, b\}, P, S), com as produções :

SaSa,
SbSb,
Sε,

é livre de contexto. Não não é adequada uma vez que inclui um ε-produção. Uma derivação típico nesta gramática é

SaSaaaSaaaabSbaaaabbaa.

Essa derivação deixa claro que L(G) = \{ww^R:w\in\{a,b\}^*\}. A linguagem é livre de contexto, no entanto, pode ser provado que não é regular.  

Exemplos[editar | editar código-fonte]

Parênteses bem formados[editar | editar código-fonte]

O exemplo canônico de uma gramática livre de contexto é o da correspondência de parênteses , que é representante do caso geral. Há dois símbolos terminais "( " e " )" e um símbolo não terminal S. As regras de produção são 

S → SS
S → (S)
S → ()

A primeira regra permite que o símbolo S para multiplicar; a segunda regra permite que o símbolo S fique entre parênteses correspondentes; e a terceira regra termina a recursividade. 

Parênteses aninhados e colchetes bem formado[editar | editar código-fonte]

Um segundo exemplo canônico é dois tipos diferentes de correspondência de parênteses aninhados, descritas pelas produções: 

S → SS
S → ()
S → (S)
S → []
S → [S]

Com o símbolos terminal [] () e o não terminal S. 

A sequencia a seguir pode ser derivado dessa gramática:

([ [ [ ()() [ ][ ] ] ]([ ]) ])

No entanto, não há nenhuma gramática livre de contexto para a geração de todas as sequências de colchetes e parenteses , cada um separadamente em relação desprezando o outro, mas onde os dois tipos não precisa alinhar um dentro do outro, por exemplo: 

[ ( ] )

ou

[ [ [ [(((( ] ] ] ]))))(([ ))(([ ))([ )( ])( ])( ])

A Gramática Regular[editar | editar código-fonte]

Toda gramática regular é livre de contexto, mas nem todas as gramaticas livres de contexto são regulares.. A gramática livre de contexto seguinte, no entanto, também é regular. 

S → a
S → aS
S → bS

Os terminais aqui são a e b, enquanto o único não terminal é S. A linguagem descrita é todas as cadeias não vazias  as ebs que terminam em a.

Essa gramática é regular: nenhuma regra tem mais do que um não terminal em seu lado direito, e cada um desses não terminais é, ao mesmo ao fim do lado direito. 

Cada gramática regular corresponde diretamente a um autômato finito não determinístico, por isso sabemos que esta é uma linguagem regular.

Usando a barra vertical, a gramática descrita acima pode ser mais sucintamente do seguinte modo: 

S → a | aS | bS

Combinando pares[editar | editar código-fonte]

Em uma gramática livre de contexto, podemos emparelha caracteres a forma como fazemos com os colchetes. O exemplo mais simples: 

S → aSb
S → ab

Essa gramática gera a linguagem \{ a^n b^n : n \ge 1 \} ,que não e regular ( de acordo com a regra do lema do bombeamento para linguagens regulares).

O caractere especial ε serve para a cadeia vazia. Ao alterar a gramática acima para

S → aSb | ε

obtém-se uma gramática que gera a linguagem  \{ a^n b^n : n \ge 0 \} . Esta difere apenas que contém a cadeia vazia, enquanto a gramática original não tem. 

Expressões Algébricas[editar | editar código-fonte]

Aqui está uma gramática livre de contexto para expressões algébricas sintaticamente corretas e infixas nas variáveis x, y e z:

  1. S → x
  2. S → y
  3. S → z
  4. S → S + S
  5. S → S - S
  6. S → S * S
  7. S → S / S
  8. S → ( S )

Essa gramática pode, por exemplo, gerar a cadeia 

( x + y ) * x - z * y / ( x + x )

como a seguir: 

S (o símbolo inicial)
→ S - S (pela regra 5)
→ S * S - S (pela regra 6, aplicada à extremidade esquerda S)
→ S * S - S / S (pela regra 7, aplicada à extremidade direita S)
→ ( S ) * S - S / S (pela regra 8, aplicada à extremidade esquerda S)
→ ( S ) * S - S / ( S ) (pela regra 8, aplicada à extremidade direita S)
→ ( S + S ) * S - S / ( S ) (etc.)
→ ( S + S ) * S - S * S / ( S )
→ ( S + S ) * S - S * S / ( S + S )
→ ( x + S ) * S - S * S / ( S + S )
→ ( x + y ) * S - S * S / ( S + S )
→ ( x + y ) * x - S * y / ( S + S )
→ ( x + y ) * x - S * y / ( x + S )
→ ( x + y ) * x - z * y / ( x + S )
→ ( x + y ) * x - z * y / ( x + x )

Note-se que muitas opções foram feitas no andamento como a que foi reescrita vai ser realizada em seguida. Estas escolhas parecem bastante arbitrária. Por uma questão de fato, elas são, no sentido de que a cadeia gerado no final é sempre a mesma. Por exemplo, o segundo e terceiro reescritos

→ S * S - S (pela regra 6, aplicada à extremidade esquerda S)
→ S * S - S / S (pela rega 7, aplicada à extremidade direita S)

pode ser feita na ordem oposta: 

→ S - S / S (pela regra 7,aplicada à extremidade direita S)
→ S * S - S / S (pela regra 6, aplicada à extremidade esquerda S)

Além disso, muitas escolhas foram feitas para que regra aplicar para cada  S selecionado. Mudando as escolhas feitas e não apenas a ordem em que elas foram feitas, geralmente afeta em qual terminal da cadeia vem no final.

Vamos olhar isso com mais detalhes. Considere a árvore de análise dessa derivação:

           S
           |
          /|\
         S - S
        /     \
       /|\    /|\
      S * S  S / S
     /    |  |    \
    /|\   x /|\   /|\
   ( S )   S * S ( S )
    /      |   |    \   
   /|\     z   y   /|\
  S + S           S + S
  |   |           |   |
  x   y           x   x

Começando na parte superior, passo a passo, um S na árvore é expandida, até que não haja mais S não expandido, isto é  (não terminais) permanecem.Escolher uma ordem diferente de expansão irá produzir uma derivação diferente, mas a mesma árvore de análise. A árvore de análise só vai mudar se nós escolhemos uma regra diferente para aplicar em alguma posição na árvore.

Porém, pode uma árvore de análise diferente ainda produzir a mesma seqüência terminal, que é( x + y ) * x - z * y / ( x + x  nesse caso? Sim, com essa gramática particular, isso é possível. Gramáticas com esta propriedade são chamadas ambígua.

Por exemplo, x + y * z pode ser produzida com estas duas árvores de análise diferentes:

         S               S
         |               |
        /|\             /|\
       S * S           S + S    
      /     \         /     \
     /|\     z       x     /|\
    S + S                 S * S    
    |   |                 |   |
    x   y                 y   z

No entanto, a linguagem descrita por esta gramática não é inerentemente ambígua: uma alternativa, gramática não ambígua pode ser dada para o idioma, por exemplo:

T → x
T → y
T → z
S → S + T
S → S - T
S → S * T
S → S / T
T → ( S )
S → T

(mais uma vez escolhendo S como o símbolo de inícial). Essa gramática alternativa produzirá x + y * z com uma árvore de análise similar à esquerda, a cima, isto é, admitindo implicitamente a associação (x + y) * z, que não está de acordo com a precedência do operador padrão. Mais elaboradas, gramáticas não ambígua e livres de contexto podem ser construídas de forma que produzem árvores de análise que obedecem a todas as regras de precedência e associatividade de operadores desejados.

Exemplos adicionais[editar | editar código-fonte]

Exemplo 1[editar | editar código-fonte]

Uma gramática livre de contexto para a linguagem consistindo de todas as cadeias sobre {a, b} contendo um número desigual de a's e b's: 

S → U | V
U → TaU | TaT | UaT
V → TbV | TbT | VbT
T → aTbT | bTaT | ε

Aqui, o simbolo não terminal T pode gerar todas as cadeias com o mesmo número de a's e b's, o simbolo não terminal U gera todas as cadeias com mais a's do que de b's e o simbolo não terminal V gera todas as cadeias com menos a's do que b's. Omitindo a terceira alternativa na regra para U e V não restringe a linguagem da gramática. 

Exemplo 2[editar | editar código-fonte]

Outro exemplo de uma linguagem não regular é  \{ b^n a^m b^{2n} : n \ge 0, m \ge 0 \} . É livre de contexto, uma vez que pode ser gerado pela seguinte gramática livre de contexto:

S → bSbb | A
A → aA | ε

Outros exemplos[editar | editar código-fonte]

As regras de formação para os termos e fórmulas da lógica formal se encaixam na definição de gramática livre de contexto, exceto que o conjunto de símbolos pode ser infinito e pode haver mais do que um símbolo de inicial.

Derivações e árvores de sintaxe[editar | editar código-fonte]

A derivação de uma cadeia de caracteres para uma gramática é uma sequência de aplicações de regras de gramática que transforma o símbolo inicial na cadeia. Uma derivação prova que a sequência pertence à linguagem da gramática.

A derivação é totalmente determinado fornecendo em cada passo : 

  • a regra aplicada nesse passo
  •  a ocorrência do seu lado esquerdo para o qual é aplicado 

Para maior clareza, a cadeia intermediária geralmente é dado também. 

Por exemplo, com a gramática:

 (1)  S → S + S
 (2)  S → 1
 (3)  S → a

 a cadeia :

1 + 1 + a

pode ser derivada com a derivação: 

S
   → (regra 1 do primeiro S)
 S+S
   → (regra 1 do segundo S)
 S+S+S
   → (regra 2 do segundo S)
 S+1+S
   → (regra 3 do terceiro S)
 S+1+a
   → (regra 2 do primeiro S)
 1+1+a

Muitas vezes, uma estratégia que é seguida deterministicamente determina o próximo não terminal que vai ser reescrito:  

  • em uma derivação mais à esquerda, é sempre o simbolo não terminal mais à esquerda l; 
  • em uma derivação mais à direita, é sempre o simbolo não terminal à direita. 

Diante de tal estratégia, uma derivação é completamente determinada pela sequência de regras aplicadas. Por exemplo, a derivação mais à esquerda 

S
  → (regra 1 do primeiro S) S+S
  → (regra 2 do primeiro S) 1+S
  → (regra 1 do primeiro S) 1+S+S
  → (regra 2 do primeiro S) 1+1+S
  → (regra 3 do primeiro S) 1+1+a

pode ser resumido como 

regra 1, regra 2, regra 1, a regra 2, regra 3

A distinção entre derivação mais à esquerda e mais à direita derivação é importante porque, na maioria dos parsers a transformação da entrada é definida por dar um pedaço de código para cada regra gramatical que é executado sempre que a regra é aplicada. Por isso, é importante saber se o parser determina o tipo de derivação mais a esquerda ou à direita, porque isso determina a ordem em que as partes de código vai ser executado. Veja por exemplo uma analisadores LL e analisadores LR.

A derivação também impõe em certo sentido, uma estrutura hierárquica na cadeia que vai ser derivada. Por exemplo, se a cadeia "1 + 1 + a" é derivada de acordo com a derivação mais à esquerda:

S → S + S (1)
   → 1 + S (2)
   → 1 + S + S (1)
   → 1 + 1 + S (2)
   → 1 + 1 + a (3)

a estrutura da cadeia seria: 

{ { 1 }S + { { 1 }S + { a }S }S }S

onde { ... }S indica uma sub-cadeia reconhecida como parte de S. Esta hierarquia pode também ser visto como uma árvore:

           S
          /|\
         / | \
        /  |  \
       S  '+'  S
       |      /|\
       |     / | \
      '1'   S '+' S
            |     |
           '1'   'a'

Esta árvore é chamada uma árvore de análise ou "árvore de sintaxe concreta" da cadeia, por contraste com a árvore de sintaxe abstrata. Neste caso que foi apresentado, as derivações mais à esquerda e à direita definem a mesma árvore de análise; No entanto, existe um outro (mais à direita) derivação da mesma cadeia 

S → S + S (1)
   → S + a (3)
   → S + S + a (1)
   → S + 1 + a (2)
   → 1 + 1 + a (2)

e isso define o seguinte árvore de análise:  

           S 
          /|\
         / | \
        /  |  \
       S  '+'  S
      /|\      |
     / | \     |
    S '+' S   'a'
    |     |
   '1'   '1'

Se, para certas cadeias na linguagem da gramática, há mais de uma árvore de análise,então, a gramática é dito ser uma gramática ambígua.Essas gramáticas são geralmente difíceis de analisar porque o analisador não pode sempre decidir qual regra gramatical tem que ser aplicada.Normalmente, a ambiguidade é uma característica da gramática, não da linguagem, e uma gramática não ambígua pode ser encontrada que gera a mesma linguagem livre de contexto.No entanto, há certas línguas que só podem ser geradas por gramáticas ambíguas; tais linguagens são chamadas de linguagens inerentemente ambíguas.

Forma Normal[editar | editar código-fonte]

Toda gramática livre de contexto que não gera a cadeia vazia pode ser transformado em um em que não há ε-produção (isto é, uma regra que tem a cadeia vazia como um produto). Se uma gramática faz gerar a cadeia vazia, será necessário incluir a regraS \rarr \epsilon, mas não há necessidade de nenhuma outra regra ε. Toda gramática livre de contexto sem ε-produção tem uma gramática equivalente em forma normal de Chomsky ou forma normal de Greibach ."Equivalente", aqui, significa que as duas gramáticas gerar a mesma língua.  

A forma especialmente simples de regras de produção em gramáticas na Forma Normal de Chomsky tem implicações teóricas e práticas.Por exemplo, dada uma gramática livre de contexto pode-se usar a Forma Normal de Chomsky para construir um algoritmo de tempo polinomial que decide se uma determinada cadeia está na linguagem representado pela a gramática ou não (o algoritmo CYK).

Propriedades de fechamento[editar | editar código-fonte]

Linguagens livres de contexto são fechados sob união, concatenação, Fecho de Kleene[11] , de Operações em cadeias de caracteres(em particular homomorfismo),[12] , homomorfismo inverso,[13] e intersecção com uma linguagem regular.[14] Elas não estão fechadas sob intersecção geral (por consequência não são fechadas no complemento) e diferença de conjunto.[15]  

Problemas decidíveis[editar | editar código-fonte]

Existem algoritmos para decidir se uma linguagem livre de contexto está vazio, e se ele é finito.[16]

Problemas indecidíveis[editar | editar código-fonte]

Algumas perguntas que são indecidíveis para as classes mais amplas de gramáticas se tornam decidíveis para gramáticas livres de contexto;por exemplo. o problema da vacuidade (se a gramática gera alguma cadeia de terminais), é indecidível para gramáticas sensíveis ao contexto, mas decidível para gramáticas livres de contexto.

No entanto, muitos problemas são indecidíveis até mesmo para gramáticas livres de contexto. Alguns exemplos são : 

Universalidade[editar | editar código-fonte]

Dada uma GLC, ela gera a linguagem de todas as cadeias sobre o alfabeto de símbolos terminais utilizados nas suas regras? [17] [18]  

Uma redução pode ser mostrada desse problema para o problema indecidível bem conhecido de se determinar se uma máquina de Turing aceita uma entrada particular (o Problema da parada). A redução utiliza o conceito de um histórico de computação, uma cadeia que descreve toda a computação de uma máquina de Turing. Uma GLC pode ser construída de forma que ela gera todas as cadeias que são histórias de computação de não aceitação para uma máquina de Turing particular sobre uma determinada entrada, e, portanto, ela irá aceitar todas as cadeias apenas se a máquina não aceita essa entrada.

Igualdade de linguagem[editar | editar código-fonte]

Dado duas GLCs, eles geram a mesma língua?[18] [19]

A indecidibilidade do problema é uma consequência direta do anterior: é impossível até mesmo decidir se uma GLC é equivalente a GLC trivial que define a linguagem de todas as cadeias.

Inclusão de linguagem[editar | editar código-fonte]

Dadas duas GLCs, pode o primeiro gerar todas as cadeias que o segundo pode gerar? [18] [19]

Se este problema foi decidível, em seguida, a igualdade de linguagem pode ser decidido também: dois GLCs G1 e G2 gerar a mesma língua se L(G1) é um subconjunto de L(G2) e L(G2) é um subconjunto de L(G1).

Estar em um nível inferior ou superior da hierarquia de Chomsky[editar | editar código-fonte]

Usando o teorema de Greibach, pode ser demonstrado que os dois seguintes problemas são indecidíveis:

Ambiguidade de gramática[editar | editar código-fonte]

Dada uma GLC, ela é ambígua

A indecidibilidade deste problema resulta do fato de que, se existe um algoritmo para determinar a ambiguidade existente, o problema da correspondência de Post poderia ser decidido, que é conhecido como sendo indecidível. 

Disjunção de linguagem[editar | editar código-fonte]

Dadas duas GLCs, existe alguma cadeia produzida a partir de ambas as gramáticas? 

Se o problema era decidível, o problema indecidível da Problema da correspondência de Post poderia ser decidido, para uma dada cadeia\alpha_1, \ldots, \alpha_N, \beta_1, \ldots, \beta_N sobre algum alfabeto \{a_1, \ldots, a_k\}, let the grammar G_1 consist of the rule

S \to \alpha_1 S \beta_1^{rev} | \cdots | \alpha_N S \beta_N^{rev} | b;

onde \beta_i^{rev} denota a cadeia inversa \beta_i and b não ocorre entre o a_i; ;e deixe gramática G_2 consistir da a regra

T \to a_1 T a_1 | \cdots | a_k T a_k | b;

Então o problema de Post dado por\alpha_1, \ldots, \alpha_N, \beta_1, \ldots, \beta_N tem uma solução se e somente se L(G_1) eL(G_2) compartilham uma cadeia derivável.

Extensões[editar | editar código-fonte]

Uma maneira óbvia de estender o formalismo gramática livre de contexto é permitir não terminais de ter argumentos, cujos valores são repassados dentro das regras.Isso permite que recursos de linguagem naturais, tais como acordo e referência, e análogos de linguagens de programação, tais como o uso correto e definição de identificadores, para ser expressa de um modo natural. Por exemplo. agora podemos facilmente expressar que, em frases em inglês, o sujeito e o verbo deve concordar em número.Em ciência da computação, exemplos dessa abordagem incluem gramáticas de afixos, gramáticas de atributos, gramáticas indexada e Van Wijngaarden gramáticas de dois níveis. Extensões semelhantes existem em linguística. 

Uma gramática livre de contexto estendida (ou gramática parte direita regular) é aquele em que o lado direito das regras de produção é permitido ser uma expressão regular sobre os terminais e não terminais da gramática.Gramáticas livres de contexto estendida descrever exatamente linguagem livre de contexto.[20]

Outra extensão é permitir símbolos terminais adicionais, para aparecer no lado esquerdo de regras, restringindo a sua aplicação. Isso produz o formalismo das gramáticas sensíveis ao contexto. 

Subclasses[editar | editar código-fonte]

Há um número de subclasses importantes das gramáticas livres de contexto:  

  • Simples LR, Look-Ahead LR gramáticas são subclasses que permitem uma maior simplificação da análise. SLR e LALR são reconhecidos usando o mesmo APD como LR, mas com tabelas simples, na maioria dos casos.
  • LL (k) e LL (*) gramáticas permitem a análise por construção direta de uma derivação mais à esquerda tal como descrito acima, e descreve um número menor de linguagens. .
  • Gramáticas simples são uma subclasse da LL (1) gramáticas, são interessantes principalmente pela a sua propriedade teórica em que a igualdade de linguagem de gramáticas simples é decidível, enquanto a inclusão de linguagem não é. 
  • Gramáticas Bracketed têm a propriedade de que os símbolos terminais são divididos em pares de colchetes esquerdo e direito que sempre combinam em regras. 

LR análise estende LL análise para apoiar uma maior gama de gramáticas; por sua vez, analise generalizada LR estende LR análise para apoiar gramáticas livres de contexto arbitrárias. Em gramáticas LL e gramáticas LR, elas essencialmente executam a LL análise e a LR análise, respectivamente, enquanto que em gramáticas não determinísticas,é tão eficaz como pode ser esperado. Embora GLR análise foi desenvolvido na década de 1980 muitas novas definições de idioma e geradores de analise continuam a baseiar-se em LL, LR LALR ou analisar até os dias atuais. 

Aplicações linguísticas[editar | editar código-fonte]

Chomsky inicialmente esperou superar as limitações de gramáticas livres de contexto, adicionando regras de transformação.[3]

Tais regras são outro dispositivo padrão em linguística tradicionais; por exemplo forma passiva em inglês. Grande parte da gramática gerativa tem se dedicado a encontrar formas de aperfeiçoar os mecanismos descritivos da frase-estrutura gramatical e transformação de tal forma que governa exatamente os tipos de coisas que podem ser expressas em linguagem natural. Permitindo transformações arbitrárias não cumprem essa meta: elas são muito poderosos demais, sendo Turing completa a menos que restrições significativas são adicionados (por exemplo, não há transformações que introduzem e, em seguida, reescrever símbolos de uma forma livre de contexto). 

Posição geral de Chomsky sobre não-liberdade-de-contexto da linguagem natural tem se mantido desde então,[21] embora seus exemplos específicos sobre a inadequação de gramáticas livres de contexto, em termos de sua capacidade geradora fraca foram mais tarde desmentida.[22] Gerald Gazdar e Geoffrey Pullum argumentaram que, apesar de alguns construções não-livre de contexto em linguagem natural (tais como dependências cross-série em Suíço-alemão[21] e reduplicação em Bambara[23] ), a grande maioria dos formulários em linguagem natural são, de facto livre de contexto.[22]

Veja Também[editar | editar código-fonte]

Algoritmos de análise[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1. Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeen Motwani, Jeffrey D. Ullman, Addison Wesley, 2001, p.191
  2. a b Hopcroft & Ullman (1979), p. 106.
  3. a b Chomsky, Noam (Sep 1956), "Three models for the description of language", Information Theory, IEEE Transactions 2 (3): 113–124, doi:10.1109/TIT.1956.1056813, arquivado do original em 2013-10-18, http://www.chomsky.info/articles/195609--.pdf, visitado em 2007-06-18 
  4. The notation here is that of Sipser (1997), p. 94. Hopcroft & Ullman (1979) (p. 79) define context-free grammars as 4-tuples in the same way, but with different variable names.
  5. Hopcroft & Ullman (1979), pp. 90–92.
  6. Nijholt, Anton (1980), Context-free grammars: covers, normal forms, and parsing, Lecture Notes in Computer Science, 93, Springer, p. 8, ISBN 3-540-10245-0 .
  7. Hopcroft & Ullman (1979), p.88, Lemma 4.1
  8. Hopcroft & Ullman (1979), p.89, Lemma 4.2
  9. This is a consequence of the unit-production elimination theorem in Hopcroft & Ullman (1979), p.91, Theorem 4.4
  10. Hopcroft & Ullman (1979), p.91, Theorem 4.4
  11. Hopcroft & Ullman (1979), p.131, Theorem 6.1
  12. Hopcroft & Ullman (1979), p.131-132, Theorem 6.2
  13. Hopcroft & Ullman (1979), p.132-134, Theorem 6.3
  14. Hopcroft & Ullman (1979), p.135-136, Theorem 6.5
  15. Hopcroft & Ullman (1979), p.134-135, Theorem 6.4
  16. Hopcroft & Ullman (1979), p.137-138, Theorem 6.6
  17. Sipser (1997), Theorem 5.10, p. 181.
  18. a b c d Hopcroft & Ullman (1979), p. 281.
  19. a b c Hazewinkel, Michiel (1994), Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia", Springer, Vol. IV, p. 56, ISBN 978-1-55608-003-6, http://books.google.com/books?id=s9F71NJxwzoC&pg=PA56 .
  20. Norvell, Theodore. «A Short Introduction to Regular Expressions and Context-Free Grammars» (PDF). p. 4. Consultado em August 24, 2012. 
  21. a b Shieber, Stuart (1985), "Evidence against the context-freeness of natural language", Linguistics and Philosophy 8 (3): 333–343, doi:10.1007/BF00630917, http://www.eecs.harvard.edu/~shieber/Biblio/Papers/shieber85.pdf .
  22. a b Pullum, Geoffrey K.; Gerald Gazdar (1982), "Natural languages and context-free languages", Linguistics and Philosophy 4 (4): 471–504, doi:10.1007/BF00360802 .
  23. Culy, Christopher (1985), "The Complexity of the Vocabulary of Bambara", Linguistics and Philosophy 8 (3): 345–351, doi:10.1007/BF00630918 .

Referências[editar | editar código-fonte]

  • Hopcroft, John E.; Ullman, Jeffrey D. (1979), Introduction to Automata Theory, Languages, and Computation, Addison-Wesley . Chapter 4: Context-Free Grammars, pp. 77–106; Chapter 6: Properties of Context-Free Languages, pp. 125–137.
  • Sipser, Michael (1997), Introduction to the Theory of Computation, PWS Publishing, ISBN 0-534-94728-X . Chapter 2: Context-Free Grammars, pp. 91–122; Section 4.1.2: Decidable problems concerning context-free languages, pp. 156–159; Section 5.1.1: Reductions via computation histories: pp. 176–183.
  • J. Berstel, L. Boasson (1990). Jan van Leeuwen, ed. Context-Free Languages. Handbook of Theoretical Computer Science B. Elsevier. pp. 59–102.