Gramática livre de contexto

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

$A\ \to \ \alpha$

$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 combinam 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 inferiores, 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 conhecidas 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 surgiram da linguística, onde são utilizadas para descrever a estrutura das frases e palavras em linguagem natural, e elas foram, de fato, inventadas 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 usadas 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

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 descrito como as sentenças são recursivamente construídas 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 reescrita utilizando-se colchetes como meta-símbolos lógicos [], como se segue:
[João[,[cujo [carro azul]] [estava [em [a 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ídas a partir de blocos menores, capturando a "estrutura de blocos" de frases de uma forma natural. Sua simplicidade faz o formalismo passível de rigoroso estudo matemático. 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 engolidos por substantivos e verbos, são descritas 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 descrita por regras livres de contexto combinadas com regras de transformação.

A estrutura de bloco foi introduzida nas linguagens de programação de computador pelo projeto Algol (1957-1960), que, como consequência, também contou com uma gramática livre de contexto para descrever a resultante sintaxe Algol. Isto tornou-se uma característica padrão das linguagens de computador, e a notação de gramáticas usada em descrições concretas de linguagens de computador veio a ser conhecida como Formalismo de Backus-Naur, em homenagem a dois membros do comitê de design de linguagem Algol.^[2] O aspecto de "estrutura de bloco" que gramáticas livres de contexto capturam é tão fundamental à gramática, que os termos sintaxe e gramática são freqüentemente identificados com regras de gramática livre de contexto, especialmente em ciência da computação. Restrições formais não capturadas pela gramática são, então, consideradas 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 análise sintática (ou parsing) eficientes que, para uma dada sequência de caracteres, determinam se e como ela pode ser gerada a partir da gramática. Um algoritmo 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

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

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

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.
$Σ$ é 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.
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)
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

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}$ e $\alpha \rightarrow \beta _{2}$ , portanto, pode ser escrito como $\alpha \rightarrow \beta _{1}\mid \beta _{2}$ . Neste caso, $\beta _{1}$ e $\beta _{2}$ são chamadas a primeira e segunda alternativa, respectivamente.

Aplicação das Regras editar

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}$ e $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

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 que $u=\,u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}\,=v$ . Neste caso, se $k\geq 2$ (i.e., $u\neq v$ ), a relação $u{\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

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

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

nenhum símbolo inalcançável: $\forall N\in V:\exists \alpha ,\beta \in (V\cup \Sigma )^{*}:S{\stackrel {*}{\Rightarrow }}\alpha {N}\beta$
nenhum símbolo que não possa ser produzido: $\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

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

S \to aSa

,

S \to bSb

,

S \to ε

,

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

S \to aSa \to aaSaa \to aabSbaa \to aabbaa

.

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

Parênteses bem formados editar

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 formados editar

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 os símbolos terminais [] () e o não terminal S.

A sequencia a seguir pode ser derivads 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 uma separadamente em relação desprezando as outras, mas onde os dois tipos não precisam alinhar um dentro da outra, por exemplo:

[ ( ] )

ou

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

A Gramática Regular editar

Toda gramática regular é livre de contexto, mas nem todas as gramáticas 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 é formada por todas as cadeias não vazias $a$ s e $b$ s 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 descrita mais sucintamente do seguinte modo:

S → a | aS | bS

Combinando pares editar

Em uma gramática livre de contexto, podemos emparelhar 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\geq 1\}$ ,que não é regular ( de acordo com a regra dolema 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\geq 0\}$ . Esta difere apenas por conter a cadeia vazia, enquanto a gramática original não tem.

Expressões Algébricas editar

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

S → x
S → y
S → z
S → S + S
S → S - S
S → S * S
S → S / S
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 vão ser realizadas em seguida. Estas escolhas parecem bastante arbitrárias. Por uma questão de fato, elas são, no sentido de que a cadeia gerada 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 afetam 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

Exemplo 1 editar

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

Outro exemplo de uma linguagem não regular é $\{b^{n}a^{m}b^{2n}:n\geq 0,m\geq 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

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

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 determinada 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 é dada 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

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 regra $S\rightarrow \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 gramática ou não (o algoritmo CYK).

Propriedades de fechamento editar

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

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

Problemas indecidíveis editar

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

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

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

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 decidida 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

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

Dada uma gramática sensível ao contexto, ela descreve uma linguagem livre de contexto?
Dada uma gramática livre de contexto, ela descreve uma Linguagem regular?^[18]^[19]

Ambiguidade de gramática editar

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

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}Ta_{1}|\cdots |a_{k}Ta_{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})$ e $L(G_{2})$ compartilham uma cadeia derivável.

Extensões editar

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

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

LR (k) gramáticas (também conhecido como gramáticas livres de contexto determinísticos) permitem analisar (reconhecimento de cadeias) com autômatos pilha determinísticos (APD), mas eles só podem descrever linguagens livres de contexto deterministas.

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.

Gramáticas lineares não têm regras com mais do que um não terminal no lado direito.

Gramáticas regulares são uma subclasse de gramáticas lineares e descrevem as linguagens regulares, ou seja, eles correspondem a Autômatos Finitos e expressões regulares.

LR análise estende LL análise para apoiar uma maior gama de gramáticas; por sua vez, análise 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 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 análise continuam a basear-se em LL, LR LALR ou analisar até os dias atuais.

Aplicações linguísticas editar

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ísticas tradicionais; por exemplo forma passiva em inglês. Grande parte dagramá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 poderosas 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 algumas 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]

Teoria da computação editar

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

Veja Também editar

Algoritmos de análise editar

Referências editar

↑ Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeen Motwani, Jeffrey D. Ullman, Addison Wesley, 2001, p.191
↑ ^a ^b Hopcroft & Ullman (1979), p. 106.
↑ ^a ^b Chomsky, Noam (setembro de 1956), «Three models for the description of language» (PDF), Information Theory, IEEE Transactions, 2 (3): 113–124, doi:10.1109/TIT.1956.1056813, consultado em 18 de junho de 2007, cópia arquivada (PDF) em 18 de outubro de 2013
↑ 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.
↑ Hopcroft & Ullman (1979), pp. 90–92.
↑ Nijholt, Anton (1980), Context-free grammars: covers, normal forms, and parsing, ISBN 3-540-10245-0, Lecture Notes in Computer Science, 93, Springer, p. 8, MR 590047 .
↑ Hopcroft & Ullman (1979), p.88, Lemma 4.1
↑ Hopcroft & Ullman (1979), p.89, Lemma 4.2
↑ This is a consequence of the unit-production elimination theorem in Hopcroft & Ullman (1979), p.91, Theorem 4.4
↑ Hopcroft & Ullman (1979), p.91, Theorem 4.4
↑ Hopcroft & Ullman (1979), p.131, Theorem 6.1
↑ Hopcroft & Ullman (1979), p.131-132, Theorem 6.2
↑ Hopcroft & Ullman (1979), p.132-134, Theorem 6.3
↑ Hopcroft & Ullman (1979), p.135-136, Theorem 6.5
↑ Hopcroft & Ullman (1979), p.134-135, Theorem 6.4
↑ Hopcroft & Ullman (1979), p.137-138, Theorem 6.6
↑ Sipser (1997), Theorem 5.10, p. 181.
↑ ^a ^b ^c ^d Hopcroft & Ullman (1979), p. 281.
↑ ^a ^b ^c Hazewinkel, Michiel (1994), Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia", ISBN 978-1-55608-003-6, Springer, Vol. IV, p. 56 .
↑ Norvell, Theodore. «A Short Introduction to Regular Expressions and Context-Free Grammars» (PDF). 4 páginas. Consultado em 24 de agosto de 2012
↑ ^a ^b Shieber, Stuart (1985), «Evidence against the context-freeness of natural language» (PDF), Linguistics and Philosophy, 8 (3): 333–343, doi:10.1007/BF00630917 .
↑ ^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 .
↑ Culy, Christopher (1985), «The Complexity of the Vocabulary of Bambara», Linguistics and Philosophy, 8 (3): 345–351, doi:10.1007/BF00630918 .

Fontes editar

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.

[1] Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Rajeen Motwani, Jeffrey D. Ullman, Addison Wesley, 2001, p.191

[hu106-2] Hopcroft & Ullman (1979), p. 106.

[chomsky1956-3] Chomsky, Noam (setembro de 1956), «Three models for the description of language» (PDF), Information Theory, IEEE Transactions, 2 (3): 113–124, doi:10.1109/TIT.1956.1056813, consultado em 18 de junho de 2007, cópia arquivada (PDF) em 18 de outubro de 2013

[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, ISBN 3-540-10245-0, Lecture Notes in Computer Science, 93, Springer, p. 8, MR 590047 .

[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

[sipser-17] Sipser (1997), Theorem 5.10, p. 181.

[hu281-18] Hopcroft & Ullman (1979), p. 281.

[eom-19] Hazewinkel, Michiel (1994), Encyclopaedia of mathematics: an updated and annotated translation of the Soviet "Mathematical Encyclopaedia", ISBN 978-1-55608-003-6, Springer, Vol. IV, p. 56 .

[20] Norvell, Theodore. «A Short Introduction to Regular Expressions and Context-Free Grammars» (PDF). 4 páginas. Consultado em 24 de agosto de 2012

[shieber1985-21] Shieber, Stuart (1985), «Evidence against the context-freeness of natural language» (PDF), Linguistics and Philosophy, 8 (3): 333–343, doi:10.1007/BF00630917 .

[pullum-gazdar1982-22] Pullum, Geoffrey K.; Gerald Gazdar (1982), «Natural languages and context-free languages», Linguistics and Philosophy, 4 (4): 471–504, doi:10.1007/BF00360802 .

[culy1985-23] Culy, Christopher (1985), «The Complexity of the Vocabulary of Bambara», Linguistics and Philosophy, 8 (3): 345–351, doi:10.1007/BF00630918 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]