Langage indexé

Les deux langages suivants sont indexés, et ne sont pas context-free :

• ${\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]

Les deux langages suivant sont également indexés, mais ne sont pas légèrement sensibles au contexte d'après la caractérisation de Gazdar :

• ${\displaystyle \{a^{2^{n}}|n\geq 0\}}$ [2]
• ${\displaystyle \{www|w\in \{a,b\}^{+}\}}$ [3]

Enfin, le langage suivant

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

n'est pas indexé[6] :

Hopcroft et Ullman, dans des notes (p. 394-395) dans leur livre de 1979[7]. considèrent que les langages indexés forment une classe « naturelle » de langages parce qu'ils admettent plusieurs définitions équivalents ; ce sont :

• les langages reconnus par les automates à piles emboîtées uni-directionnels de Alfred Aho[8] ;
• les langages engendrés par les macro-grammaires de Michael J. Fischer[9] ;
• les langages reconnus par les automates à piles de piles de Sheila A. Greibach[10] ;
• les langages définis par une caractérisation algébrique donnée par Thomas Maibaum (en)[11].

Takafumi Hayashi[12] a généralisé le lemme d'itération pour les langages algébriques aux grammaires indexées. Dans la direction opposée, Robert H. Gilman[6] donne un lemme de réduction pour les langages indexés.