Linguagem indexada

Linguagens indexadas são uma classe de linguagens formais descoberta por Alfred Aho; elas são descritas por gramáticas indexadas e podem ser reconhecidas por autômatos com pilhas aninhados.

Linguagens indexadas são um subconjunto próprio de linguagens sensíveis ao contexto. Elas qualificam uma família abstrata de linguagens (Além disso, um AFL cheio) e satisfazem muitas propriedades de fechamento. No entanto, elas não são fechadas sob interseção nem complemento.

A classe de linguagens indexadas tem importância prática no processamento de linguagens naturais como computacionalmente acessível, generalização das linguagens livre-do-contexto, desde que gramáticas indexadas possam descrever muitas das restrições não locais ocorrendo em linguagem naturais.

Gerald Gazdar (1988) e Vijay-Shanker (1987) introduziram a classe da linguagem moderadamente sensível ao contexto agora conhecida como gramáticas linearmente indexadas (LIG). Gramáticas linearmente indexadas tem restrições adicionais relativas a IG. LIGs são fracamente equivalentes(geram a mesma classe de linguagem) como gramáticas árvore-adjacentes.

Exemplos

As seguintes linguagens são indexadas, mas não são livres-do-contexto:

$\{a^n{b}^n{c}^n{d}^n|n\ge 1\}$

$\{a^n{b}^m{c}^n{d}^m|m,n\ge 0\}$

Essas duas linguagens também são indexadas, mas não são nem ao menos moderadamente sensíveis a contexto sobre a caracterização de Gazdar:

$\{a^{2^n}|n\ge 0\}$

$\{www|w\in \{a,b{\}}^{+}\}$

Por outro lado, a seguinte linguagem não é indexada:

$\{(a{b}^n{)}^n|n\ge 0\}$

Propriedades

Hopcroft e Ullman tendem a considerar linguagens indexadas como uma classe natural, visto que elas são geradas por vários formalismos, tais como:

• Gramática indexada de Aho
• Automato com pilha de Aho
• Macrogramáticas de Fischer
• Caracterização algébrica de Maibaum

Hayashi generalizou o lema do bombeamento para linguagens indexadas. Reciprocamente, Gilman deu um "lema da diminuição" para as linguagens indexadas.

Ver também

• Hierarquia de Chomsky
• Gramática indexada
• Gramática moderadamente sensível ao contexto

Ligações externas

• "NLP in Prolog" chapter on indexed grammars and languages