Gramática livre do contexto generalizada

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

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

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$
2. 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)

Weir (1988) 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.