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^[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

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

$\{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}$ ^[3]
$\{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 :

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

Enfin, le langage suivant

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

n'est pas indexé^[6] :

Propriétés modifier

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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Indexed language » (voir la liste des auteurs).

↑ ^{a b et c} Alfred Aho, « Indexed grammars—an extension of context-free grammars », Journal of the ACM, vol. 15, n^o 4,‎ 1968, p. 647–671 (DOI 10.1145/321479.321488, lire en ligne).
↑ ^{a b et c} (en) Barbara Partee, Alice ter Meulen et Robert E. Wall, Mathematical Methods in Linguistics, Kluwer Academic Publishers, 1990, 536–542 p. (ISBN 978-90-277-2245-4, lire en ligne).
↑ ^{a b et c} 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 » (n^o 35), 1988 (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, 2010 (ISBN 978-3-642-14846-0, lire en ligne), p. 31.
↑ ^{a et b} Robert H. Gilman, « A Shrinking Lemma for Indexed Languages », Theoretical Computer Science, vol. 163, n^os 1–2,‎ 1996, 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, 1979 (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, n^o 3,‎ 1969, 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),‎ 1968, p. 131–142
↑ (en) Sheila A. Greibach, « Full AFL's and Nested Iterated Substitution », Information and Control, vol. 16, n^o 1,‎ 1970, 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, n^o 3,‎ 1974, 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, n^o 1,‎ 1973, p. 61–92 (DOI 10.2977/prims/1195192738, lire en ligne)

[aho1968-1] {a b et c} Alfred Aho, « Indexed grammars—an extension of context-free grammars », Journal of the ACM, vol. 15, n^o 4,‎ 1968, p. 647–671 (DOI 10.1145/321479.321488, lire en ligne).

[partee_etal_1990-2] {a b et c} (en) Barbara Partee, Alice ter Meulen et Robert E. Wall, Mathematical Methods in Linguistics, Kluwer Academic Publishers, 1990, 536–542 p. (ISBN 978-90-277-2245-4, lire en ligne).

[gazdar1998-3] {a b et c} 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 » (n^o 35), 1988 (ISBN 1-55608-055-7), p. 69–94.

[4] K. Vijay-Shanker, « A study of tree adjoining grammars ».

[Kallmeyer2010-5] (en) Laura Kallmeyer, Parsing Beyond Context-Free Grammars, Heidelberg, Springer Science & Business Media, 2010 (ISBN 978-3-642-14846-0, lire en ligne), p. 31.

[Gilman.1996-6] {a et b} Robert H. Gilman, « A Shrinking Lemma for Indexed Languages », Theoretical Computer Science, vol. 163, n^os 1–2,‎ 1996, p. 277-281 (DOI 10.1016/0304-3975(96)00244-7, lire en ligne)

[Hopcroft_and_Ullman-7] (en) John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979 (ISBN 0-201-02988-X), section 14.3, p. 389-390. Cette section ne figure plus dans la deuxième édition, datant de 2003.

[8] (en) Alfred Aho, « Nested Stack Automata », Journal of the ACM, vol. 16, n^o 3,‎ 1969, p. 383–406 (DOI 10.1145/321526.321529)

[9] Michael J. Fischer, « Grammars with Macro-Like Productions », Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT),‎ 1968, p. 131–142

[10] (en) Sheila A. Greibach, « Full AFL's and Nested Iterated Substitution », Information and Control, vol. 16, n^o 1,‎ 1970, p. 7–35 (DOI 10.1016/s0019-9958(70)80039-0, lire en ligne)

[11] (en) Thomas S. E. Maibaum, « A Generalized Approach to Formal Languages », J. Computer and System Sciences, vol. 8, n^o 3,‎ 1974, p. 409–439 (DOI 10.1016/s0022-0000(74)80031-0, lire en ligne).

[Hayashi.1973-12] (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, n^o 1,‎ 1973, p. 61–92 (DOI 10.2977/prims/1195192738, lire en ligne)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]