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 onde

  1. é um alfabeto finito de variáveis ou símbolos não-terminais
  2. é um alfabeto finito de símbolos terminais
  3. é 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. é o conjunto finito de produções
  5. é o símbolo da sentença

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

  • Uma produção de corresponde a um não-terminal seguida por sua (possivelmente vazia) cadeia de flags . No contexto, , via , deriva para , onde where se fosse um não-terminal e a palavra vazia, caso contrário. As flags velhas de são, portanto, copiadas para cada não-terminal novo produzido por
  • Uma produção de índice corresponde a (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 para cada novo terminal: deriva para , onde é a palavra vazia quando é um não-terminal e caso contrário.

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

Uma cadeia com um símbolo não-terminal com alguns símbolos de indexação na sua pilha pode ser denotada como (usando [ e ] como metassímbolos para denotar a pilha). Numa gramática indexada, a aplicação de uma regra de produção como reescreveria a cadeia por trocar por , que copia os símbolos da pilha de para cada não-terminal em seu lugar - e 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 :

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

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 é gerada por uma gramática indexada, mas não por uma gramática indexada linear, enquanto que é gerada por uma gramática indexada linear.

Exemplo[editar | editar código-fonte]

Supondo que denota uma coleção arbitrária de símbolos de pilha, podemos definir uma gramática para a linguagem como

Para derivar a cadeia temos os passos .

Similarmente, para : .

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 , módulo a parte do empilha/desempilha de uma regra de reescrita. Os símbolos e 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 e que, mesmo tendo pilhas não-vazias, comportem-se como se tivessem pilhas vazias.

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

Podemos aplicar isso em geral para derivar uma GI de uma GIL. Como, por exemplo, se a GIL para a linguagem é como se segue:

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

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


Onde , , and são cadeiras de terminais arbitrários. Para uma cadeira ternariamente distributiva:


E assim em diante para números maiores de não-terminais no lado direito da regra de reescrita. Geralmente, se existem não-terminais na direita de uma regra de reescrita, a pilha é particionada em 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