Gramática livre do contexto generalizada

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Wikitext.svg
Esta página ou seção precisa ser wikificada (desde abril de 2013).
Por favor ajude a formatar esta página de acordo com as diretrizes estabelecidas.
NoFonti.svg
Esta página ou secção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo. Por favor, adicione mais referências e insira-as corretamente no texto ou no rodapé. Material sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)


Gramática Livre do Contexto Generalizada (GLCG) é um formalismo de gramática que expande-se sobre as Gramáticas Livres de Contexto por adicionar composições de funções potencialmente não livres de contexto para re-escrever as regras.[1] Gramática de Cabeça (e seus equivalentes fracos) é uma instância de uma GLCG que é conhecida por ser especialmente adepta em manusear uma grande variedade de propriedades não livres do contexto da linguagem natural.

Descrição[editar | editar código-fonte]

Uma GLCG consiste de dois componentes: um conjunto de funções de composição que combina tuplas de cadeias e um conjunto de regras de re-escrita. As funções de composição todas tem a forma , onde é ou uma tupla de cadeias ou algum uso de uma (potencialmente diferente) função de composição que se reduz a uma tupla de cadeias. Regras de re-escrita se parecem com , onde , , ... são tuplas de cadeias ou símbolos não terminais.

A semântica de reescrita de uma GLCG é relativamente direta. Uma ocorrência de um símbolo não terminal é re-escrito usando as regras de re-escrita assim como numa GLC, eventualmente gerando apenas composições (funções de composições aplicadas a tuplas de cadeias ou outras composições). As funções são então aplicadas, reduzindo sucessivamente as tuplas a uma única tupla.

Exemplo[editar | editar código-fonte]

A simples tradução de uma GLC para uma GLCG pode ser feita da seguinte maneira. Dada a gramática em (1), que gera a linguagem de palíndromes , onde é a cadeira reversa de , nós podemos definir a função de composição "conc" como em (2a) e as regras de re-escrita como em (2b)

A simple translation of a context-free grammar into a GCFG can be performed in the following fashion. Given the grammar in (1), which generates the palindrome language , where is the string reverse of , we can define the composition function conc as in (2a) and the rewrite rules as in (2b).

A produção livre d contexto de "abbbba" é:

S

aSa

abSba

abbSbba

abbbba

E a produção correspondente via GLCG é

Sistemas Lineares de Re-escrita Livre do Contexto (SLRLCs)[editar | editar código-fonte]

Weir (1988)[1] descreve duas propriedades das funções de composição, linearidade e regularidade. Uma função definida como é linear sse cada variável aparece no máximo uma vez em cada lado do "=", fazendo linear mas não. Uma função definida como é regular se o lado esquero e o direito têm exatamente as mesmas variáveis, fazendo regular mas ou não.

Uma gramática em que todas as funções de composição são lineares e regulares é chamada um Sistema Linear de Re-escrita Livre do Contexto (SLRLC), um subconjunto das GLCG com estritamente menos poder computacional que as GGLC como um todo, que é fracamente equivalente a uma Gramática contígua de árvore multicomponente. Gramática de Cabeça é um exemplo de um SLRLC que é estritamente menos poderoso computacionalmente do que a classe dos SLRLC como um todo.

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

  1. a b Weir, David H. 1988. Characterizing mildly context-sensitive grammar formalisms. Dissertation, U Penn.