Gramática indexada

Uma gramática indexada é uma gramática formal que descreve linguagens indexadas. Elas têm três conjuntos disjuntos de símbolos: os terminais e não-terminais comuns, assim como símbolos de indexação, que aparecem apenas em passos de derivação intermediários de numa pilha associada com os não-terminais daquele passo.

Definição

Formalmente, uma gramática indexada é uma 5-tupla $(N,T,F,P,S)$ onde

1. $N$ é um alfabeto finito de variáveis ou símbolos não-terminais
2. $T$ é um alfabeto finito de símbolos terminais
3. $F\subseteq 2^{N\times (N\cup T)^{\ast }}$ é o conjunto finito dos chamados bandeiras(ou mais conhecidos como flags) (cada flag é por si só um conjunto do que chamamos de produções de índice)
4. $P\subseteq N\times (NF^{\ast }\cup T)^{\ast }$ é o conjunto finito de produções
5. $S\in N$ é o símbolo da sentença

Derivações diretas são como se segue:

• Uma produção $p=(A,X_{1}\eta _{1}\dots X_{k}\eta _{k})$ de $P$ corresponde a um não-terminal $A\in N$ seguida por sua (possivelmente vazia) cadeia de flags $\zeta \in F^{\ast }$. No contexto, $\gamma A\zeta \delta$, via $P$, deriva para $\gamma X_{1}\theta _{1}\dots X_{k}\theta _{k}\delta$, onde where $\theta _{i}=\eta _{i}\zeta$ se $X_{i}$ fosse um não-terminal e a palavra vazia, caso contrário. As flags velhas de $A$ são, portanto, copiadas para cada não-terminal novo produzido por $P$
• Uma produção de índice $p=(A,X_{1}\dots X_{k})\in f$ corresponde a $Af\zeta$ (a flag de onde ela se origina deve corresponder ao primeiro símbolo seguindo o não-terminal) e copia o restante da cadeira de índices $\zeta$ para cada novo terminal: $\gamma Af\zeta \delta$ deriva para $\gamma X_{1}\theta _{1}\zeta \dots X_{k}\theta _{k}\zeta \delta$, onde $\theta _{i}$ é a palavra vazia quando $X_{i}$ é um não-terminal e $\zeta$ caso contrário.

Descrição

Uma cadeia com um símbolo não-terminal $X$ com alguns símbolos de indexação $abc$ na sua pilha pode ser denotada como $\alpha X[abc]\beta$ (usando [ e ] como metassímbolos para denotar a pilha). Numa gramática indexada, a aplicação de uma regra de produção como $X[\sigma ]\to \gamma Y[\sigma ]\delta Z[\sigma ]\eta$ reescreveria a cadeia por trocar $X[abc]$ por $\gamma Y[abc]\delta Z[abc]\eta$, que copia os símbolos da pilha $abc$ de $X$ para cada não-terminal em seu lugar - $Y$ e $Z$ neste caso. No processo, um símbolo pode ser empilhado, ou retirado, da pilha, antes dela ser copiada para os não-terminais introduzidos, que poderiam ser especificados na regra para a operação de reescrita.

Exemplo

Na prática, pilhas de índices podem contar e lembrar quais regras foram aplicadas e em que ordem. Por exemplo, gramáticas indexadas podem descrever a linguagem sensível ao contexto de triplas de palavras $\{www:w\in \{a,b\}^{*}\}$:

$S[\sigma ]\to S[\sigma f]~|~S[\sigma g]$

$S[\sigma ]\to T[\sigma ]T[\sigma ]T[\sigma ]$

$T[\sigma f]\to T[\sigma ]a$

$T[\sigma g]\to T[\sigma ]b$

$T[]\to \epsilon$

A derivação de $abbabbabb$ é, então:

$S[]\to S[f]\to S[fg]\to S[fgg]\to T[fgg]T[fgg]T[fgg]$

$\to T[fg]bT[fgg]T[fgg]\to T[f]bbT[fgg]T[fgg]\to T[]abbT[fgg]T[fgg]$

$\to abbT[fgg]T[fgg]\to \dotsb \to abbabbT[fgg]\to abbabbabb$

Gramáticas indexadas lineares

Gerald Gazdar definiu uma segunda classe, as gramáticas indexadas lineares, por requerer que no máximo um não-terminal em cada produção seja especificado como recebendo a pilha, enquanto que em uma gramática indexada normal, todos os não-terminais recebem cópias da pilha. Ele mostrou que essa nova classe de gramáticas define uma classe de linguagens estritamente menor, as gramáticas levemente sensíveis ao contexto. Uma associação com uma gramática indexada linear pode ser decidida em tempo polinomial.

A linguagem $\{www:w\in \{a,b\}^{*}\}$ é gerada por uma gramática indexada, mas não por uma gramática indexada linear, enquanto que $\{a^{n}b^{n}c^{n}|n\geq 1\}$ é gerada por uma gramática indexada linear.

Exemplo

Supondo que $\sigma$ denota uma coleção arbitrária de símbolos de pilha, podemos definir uma gramática para a linguagem $L=\{a^{n}b^{n}c^{n}|n\geq 1\}$ como

$S[\sigma ]\to aS[\sigma f]c$

$S[\sigma ]\to T[\sigma ]$

$T[\sigma f]\to T[\sigma ]b$

$T[]\to \epsilon$

Para derivar a cadeia $abc$ temos os passos $S[]\to aS[f]c\to aT[f]c\to aT[]bc\to abc$.

Similarmente, para $aabbcc$: $S[]\to aS[f]c\to aaS[ff]cc\to aaT[ff]cc\to aaT[f]bcc\to aaT[]bbcc\to aabbcc$.

Poder computacional

As linguagens linearmente indexadas são um subconjunto das linguagens indexadas, e todas as GIs podem ser gravadas como GIs, tornando as GILs estritamente menos poderosas que as GIs. Uma conversão de uma GIL para uma GI é relativamente simples. Regras de uma GIL normalmente parecem-se com $X[\sigma ]\to \alpha Y[\sigma ]\beta$, módulo a parte do empilha/desempilha de uma regra de reescrita. Os símbolos $\alpha$ e $\beta$ representam cadeias de símbolos terminais/não-terminais, e qualquer símbolo não-terminal em qualquer deve ter uma pilha vazia, pela definição de uma GIL. Isso é, obviamente, contrário em relação a como as GIs estão definidas: numa GI, os não-terminais cujas pilhas não estão sendo empilhadas ou desempilhadas devem ter exatamente a mesma pilha que o não-terminal reescrito. Assim, de alguma forma, precisamos ter não-terminais em $\alpha$ e $\beta$ que, mesmo tendo pilhas não-vazias, comportem-se como se tivessem pilhas vazias.

Vamos considerar a regra $X[\sigma ]\to Y[]Z[\sigma f]$ como um exemplo. Ao converter isso para uma GI, o substituto para $Y[]$ deve ser algum $Y^{\prime }[\sigma ]$ que se comporta exatamente como $Y[]$ independentemente do que $\sigma$ seja. Para alcançarmos isso, podemos simplesmente ter um par de regras que pega qualquer $Y^{\prime }[\sigma ]$ onde $\sigma$ não é vazio, e desempilhamos símbolos da pilha. Então, quando a pilha estiver vazia, pode ser reescrita como $Y[]$.

$Y^{\prime }[\sigma f]\to Y^{\prime }[\sigma ]$

$Y^{\prime }[]\to Y[]$

Podemos aplicar isso em geral para derivar uma GI de uma GIL. Como, por exemplo, se a GIL para a linguagem $\{a^{n}b^{n}c^{n}d^{m}|n\geq 1,m\geq 1\}$ é como se segue:

$S[\sigma ]\to T[\sigma ]V[]$

$V[]\to d~|~dV[]$

$T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]$

$U[\sigma f]\to bU[\sigma ]$

$U[]\to \epsilon$

A regra sentencial aqui não é uma regra de GI, mas utilizando o algoritmo de conversão acima, podemos definir novas regras para $V^{\prime }$, mudando a gramática para:

$S[\sigma ]\to T[\sigma ]V^{\prime }[\sigma ]$

$V^{\prime }[\sigma f]\to V^{\prime }[\sigma ]$

$V^{\prime }[]\to V[]$

$V[]\to d~|~dV[]$

$T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]$

$U[\sigma f]\to bU[\sigma ]$

$U[]\to \epsilon$

Cada regra agora se encaixa na definição de uma GI, na qual todos os não-terminais no lado direito de uma regra de reescrita recebem uma cópia da pilha do símbolo reescrito. As gramáticas indexadas são, portanto, capazes de descrever todas as linguagens que gramáticas linearmente indexadas conseguem descrever.

Equivalências

Vijay-Shanker and Weir (1994) demonstra que GILs, Gramáticas Categoriais Combinatórias, Gramáticas Árvore-Adjacentes, entre outras, são formalismos fracamente equivalentes, pois definem as mesmas linguagens de cadeia.

Gramáticas de Índice Distribuído(ID)

Outra forma de gramáticas indexadas, introduzida por Staudacher (1993), é a classe de gramáticas de Índice Distribuído. O que distingue GIDs de gramáticas indexadas de Ahos é a propagação de índices. Diferentemente dos IGs, que distribuem toda a pilha de símbolos para todos os não-terminais durante a reescrita, GIDs dividem a pilha em sub-pilhas e distribuem as sub-pilhas para não-terminais selecionados.

O esquema geral para uma regra de distribuição binária de GID é da forma

$X[f_{1}\dotso f_{i}f_{j}\dotso f_{n}]\to \alpha Y[f_{1}\dotso f_{i}]\beta Z[f_{j}\dotso f_{n}]\gamma$

Onde $\alpha$, $\beta$, and $\gamma$ são cadeiras de terminais arbitrários. Para uma cadeira ternariamente distributiva:

$X[f_{1}\dotso f_{i}f_{j}\dotso f_{k}f_{l}\dotso f_{n}]\to \alpha Y[f_{1}\dotso f_{i}]\beta Z[f_{j}\dotso f_{k}]\gamma W[f_{l}\dotso f_{n}]\eta$

E assim em diante para números maiores de não-terminais no lado direito da regra de reescrita. Geralmente, se existem $N$ não-terminais na direita de uma regra de reescrita, a pilha é particionada em $N$ formas diferentes e distribuída entre os novos não-terminais. Perceba que há um caso especial onde a partição é vazia, que torna a regra uma regra GIL. As DILs são, então, um superconjunto das LILs.