Langage indexé

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 en 1968; ces langages sont engendrés par les grammaires indexées et peuvent être reconnus par les Modèle:Lien. Les langages indexés sont un sous-ensemble strict des langages contextuels. 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.

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.

Modèle:Lien et K. Vijay-Shanker ont introduit une sous-classe de langages légèrement sensible au contexte connus sous le nom de langages indexés linéaires. Les grammaires indexées linéaires ont des contraintes additionnelles par rapport aux grammaires indexées générales.

Exemples

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

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

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 :

• $\{a^{2^n}|n\ge 0\}$
• $\{www|w\in \{a,b{\}}^{+}\}$

Enfin, le langage suivant

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

n'est pas indexé :

Propriétés

Hopcroft et Ullman, dans des notes (Modèle:P.) dans leur livre de 1979. 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 ;
• les langages engendrés par les macro-grammaires de Michael J. Fischer ;
• les langages reconnus par les automates à piles de piles de Sheila A. Greibach ;
• les langages définis par une caractérisation algébrique donnée par Modèle:Lien.

Takafumi Hayashi 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 donne un lemme de réduction pour les langages indexés.

Notes et références

Modèle:Palette Modèle:Portail