Langage indexé — Wikipédia
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.
Exemples
[modifier | modifier le code]Les deux langages suivants sont indexés, et ne sont pas context-free :
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 :
Enfin, le langage suivant
n'est pas indexé[6] :
Propriétés
[modifier | modifier le code]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.
Notes et références
[modifier | modifier le code]- Alfred Aho, « Indexed grammars—an extension of context-free grammars », Journal of the ACM, vol. 15, no 4, , p. 647–671 (DOI 10.1145/321479.321488, lire en ligne).
- (en) Barbara Partee, Alice ter Meulen et Robert E. Wall, Mathematical Methods in Linguistics, Kluwer Academic Publishers, , 536–542 p. (ISBN 978-90-277-2245-4, lire en ligne).
- Gerald Gazdar, « Applicability of Indexed Grammars to Natural Languages », dans U. Reyle et C. Rohrer (éditeurs), Natural Language Parsing and Linguistic Theories, D. Reidel Publishing Company, coll. « Studies in linguistics and philosophy » (no 35), (ISBN 1-55608-055-7), p. 69–94.
- K. Vijay-Shanker, « A study of tree adjoining grammars ».
- (en) Laura Kallmeyer, Parsing Beyond Context-Free Grammars, Heidelberg, Springer Science & Business Media, (ISBN 978-3-642-14846-0, lire en ligne), p. 31.
- Robert H. Gilman, « A Shrinking Lemma for Indexed Languages », Theoretical Computer Science, vol. 163, nos 1–2, , p. 277-281 (DOI 10.1016/0304-3975(96)00244-7, lire en ligne)
- (en) John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, (ISBN 0-201-02988-X), section 14.3, p. 389-390. Cette section ne figure plus dans la deuxième édition, datant de 2003.
- (en) Alfred Aho, « Nested Stack Automata », Journal of the ACM, vol. 16, no 3, , p. 383–406 (DOI 10.1145/321526.321529)
- Michael J. Fischer, « Grammars with Macro-Like Productions », Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT), , p. 131–142
- (en) Sheila A. Greibach, « Full AFL's and Nested Iterated Substitution », Information and Control, vol. 16, no 1, , p. 7–35 (DOI 10.1016/s0019-9958(70)80039-0, lire en ligne)
- (en) Thomas S. E. Maibaum, « A Generalized Approach to Formal Languages », J. Computer and System Sciences, vol. 8, no 3, , p. 409–439 (DOI 10.1016/s0022-0000(74)80031-0, lire en ligne).
- (en) Takafumi Hayashi, « On Derivation Trees of Indexed Grammars - An Extension of the uvxyz Theorem », Publication of the Research Institute for Mathematical Sciences, vol. 9, no 1, , p. 61–92 (DOI 10.2977/prims/1195192738, lire en ligne)