Linguagem indexada

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

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

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

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:

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

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

Por outro lado, a seguinte linguagem não é indexada:^[7]

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

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

• Gramática indexada de Aho^[1]
• Automato com pilha de Aho^[10]
• Macrogramáticas de Fischer^[11]
• Caracterização algébrica de Maibaum^[12]

Hayashi^[13] generalizou o lema do bombeamento para linguagens indexadas. Reciprocamente, Gilman^[7][14] deu um "lema da diminuição" para as linguagens indexadas.

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