Gramática Indexada

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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 A f \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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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)[editar | editar código-fonte]

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.



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