Idioma indexado - Indexed language

Linguagens indexadas são uma classe de linguagens formais descobertas por Alfred Aho ; eles são descritos por gramáticas indexadas e podem ser reconhecidos por autômatos de pilha aninhados .

As linguagens indexadas são um subconjunto adequado de linguagens sensíveis ao contexto . Eles se qualificam como uma família abstrata de linguagens (além disso, um AFL completo) e, portanto, satisfazem muitas propriedades de fechamento. No entanto, eles não são fechados sob interseção ou complemento.

A classe de linguagens indexadas tem importância prática no processamento de linguagem natural como uma generalização computacionalmente acessível de linguagens livres de contexto , uma vez que gramáticas indexadas podem descrever muitas das restrições não locais que ocorrem em linguagens naturais.

Gerald Gazdar (1988) e Vijay-Shanker (1987) introduziram uma classe de linguagem levemente sensível ao contexto, agora conhecida como gramáticas indexadas lineares (LIG). Gramáticas indexadas lineares têm restrições adicionais em relação ao IG. LIGs são fracamente equivalentes (geram a mesma classe de linguagem) como árvores de gramáticas adjacentes .

Exemplos

Os seguintes idiomas são indexados, mas não são livres de contexto :

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

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

Essas duas línguas também são indexadas, mas não são nem um pouco sensíveis ao contexto de acordo com a caracterização de Gazdar:

${\ displaystyle \ {a ^ {2 ^ {n}} | n \ geq 0 \}}$

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

Por outro lado, o seguinte idioma não está indexado:

${\ displaystyle \ {(ab ^ {n}) ^ {n} | n \ geq 0 \}}$

Propriedades

Hopcroft e Ullman tendem a considerar as linguagens indexadas como uma classe "natural", uma vez que são geradas por diversos formalismos, tais como:

• Aho 's indexada gramáticas
• Aho 's one-way aninhada pilha autômatos
• Macro gramáticas de Fischer
• Autômatos de Greibach com pilhas de pilhas
• Caracterização algébrica de Maibaum

Hayashi generalizou o lema do bombeamento para gramáticas indexadas. Por outro lado, Gilman fornece um "lema da redução" para linguagens indexadas.

Veja também

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

Referências

links externos

• Capítulo "PNL no Prolog" sobre gramáticas e linguagens indexadas