En informatique théorique, et notamment en théorie des langages, et en traitement automatique du langage naturel, les langages indexés forment une classe de langages formels décrite par Alfred Aho^[1] en 1968; ces langages sont engendrés par les grammaires indexées et peuvent être reconnus par les automates à piles emboîtées (en)^[2]. Les langages indexés sont un sous-ensemble strict des langages contextuels^[1]. Ils forment une famille abstraite de langages (et jouissent donc de nombreuses propriétés de fermeture); en revanche, ils ne sont pas fermés par complémentation ni par inteersection^[1].

Les langages indexés sont une généralisation des langages algébriques et ont une relevance en traitement automatique du langage naturel puisque les grammaires indexées peuvent décrire de nombreuses contraintes non-locales apparaissant dans les langues naturelles.

Gerald Gazdar (en)^[3] et K. Vijay-Shanker^[4] ont introduit une sous-classe de langages légèrement sensible au contexte connus sous le nom de langages indexés linéaires^[5]. Les grammaires indexées linéaires ont des contraintes additionnelles par rapport aux grammaires indexées générales.

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.

• Portail de la linguistique
• Portail de l'informatique théorique