Gramática livre do contexto generalizada

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Wikitext.svg
Este artigo ou seção precisa ser wikificado (desde abril de 2013).
Por favor ajude a formatar este artigo de acordo com as diretrizes estabelecidas no livro de estilo.
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto.
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.


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 f(\langle x_1, ..., x_m \rangle, \langle y_1, ..., y_n \rangle, ...) = \gamma, onde \gamma é 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 X \to f(Y, Z, ...), onde Y, Z, ... 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 \{ ww^R : w \in \{a, b\}^{*} \}, onde w^R é a cadeira reversa de w, 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 \{ ww^R : w \in \{a, b\}^{*} \}, where w^R is the string reverse of w, we can define the composition function conc as in (2a) and the rewrite rules as in (2b).

  1. S \to \epsilon ~|~ aSa ~|~ bSb
    1. conc(\langle x \rangle, \langle y \rangle, \langle z \rangle) = \langle xyz \rangle
    2.  S \to conc(\langle \epsilon \rangle, \langle \epsilon \rangle, \langle \epsilon \rangle) ~|~ conc(\langle a \rangle, S, \langle a \rangle) ~|~ conc(\langle b \rangle, S, \langle b \rangle)

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

S

aSa

abSba

abbSbba

abbbba

E a produção correspondente via GLCG é

S \to conc(\langle a \rangle, S, \langle a \rangle)

conc(\langle a \rangle, conc(\langle b \rangle, S, \langle b \rangle), \langle a \rangle)

conc(\langle a \rangle, conc(\langle b \rangle, conc(\langle b \rangle, S, \langle b \rangle), \langle b \rangle), \langle a \rangle)

conc(\langle a \rangle, conc(\langle b \rangle, conc(\langle b \rangle, conc(\langle \epsilon \rangle, \langle \epsilon \rangle, \langle \epsilon \rangle), \langle b \rangle), \langle b \rangle), \langle a \rangle)

conc(\langle a \rangle, conc(\langle b \rangle, conc(\langle b \rangle, \langle \epsilon \rangle, \langle b \rangle), \langle b \rangle), \langle a \rangle)

conc(\langle a \rangle, conc(\langle b \rangle, \langle bb \rangle, \langle b \rangle), \langle a \rangle)

conc(\langle a \rangle, \langle bbbb \rangle, \langle a \rangle)

\langle abbbba \rangle

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 f(x_1, ..., x_n) = ... é linear sse cada variável aparece no máximo uma vez em cada lado do "=", fazendo f(x) = g(x, y) linear mas f(x) = g(x, x) não. Uma função definida como f(x_1, ..., x_n) = ... é regular se o lado esquero e o direito têm exatamente as mesmas variáveis, fazendo f(x, y) = g(y, x) regular mas f(x) = g(x, y) ou f(x, y) = g(x) 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.