Loading AI tools
type de langage formel De Wikipédia, l'encyclopédie libre
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 :
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] :
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 :
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.