Langage contextuel

En informatique théorique, et spécialement en théorie des langages, un langage contextuel (en anglais context-sensitive langauge) est un langage formel engendré par une grammaire contextuelle. C'est un langage de type 1 dans la hiérarchie de Chomsky. Les langages contextuels sont les langages reconnus par les automates linéairement bornés, c'est-à-dire les machines de Turing dont la mémoire de travail est linéairement bornée en fonction de la taille de l'entrée. Parmi les quatre classes de la hiérarchie de Chomsky, les langages contextuels sont les moins utilisés, à la fois en théorie et en pratique.

Puissance d'expression

Du point de vue de la théorie des automates, les langages contextuels sont reconnus par les machines de Turing non déterministes à mémoire linéairement bornée, appelés communément automates linéairement bornés. Une telle machine dispose, pour une entrée de taille n, d'une bande de mémoire kn, où k est une constante indépendante de n. Sur cette bande, ma machine a toutes les propriétés usuelles d'une machine de Turing.

Les langages reconnus par ces machines sont aussi appelés les langages NLIN-SPACE, pour signifier que la reconnaissance est non déterministe (N) et en espace linéaire. La classe LIN-SPACE est définie de même, sauf que les machines de Turing sont supposés être déterministes. Bien entendu, LIN-SPACE est contenue dans NLIN-SPACE, mais il n'est pas connu si on a ou non l'égalité LIN-SPACE=NLIN-SPACE. On conjecture généralement que ces classes sont distinctes. C'est l'un des deux célèbres problèmes posés par Kuroda (en), voir l'article « automate linéairement borné ».

Exemples

• Le langage L = { a^p : p est un nombre premier } est contextuel. On peut montrer qu'il n'est pas algébrique, soit en appliquant le lemme d'itération, soit en utilisant le fait que tout langage algébrique sur une lettre est un langage rationnel, et que l'ensemble des exposants des mots d'un tel langage est une union finie de progressions arithmétiques finies ou infinies^[1].

• Des exemples de langages qui ne sont pas contextuels sont donnés par des langages récursifs dont le problème d'appartenance est un problème EXPSPACE. Un exemple est le test d'équivalence d'une paire d'expression rationnelle.

Propriétés des langages contextuels

• Les langages contextuels forment une théorie des langages, et sont donc fermés par les opérations rationnelles, c'est-à-dire l'union, le produit et l'étoile de Kleene. Ils sont aussi fermés par morphisme non effaçant, par morphisme, et par intersection avec un langage rationnel: il forment donc un cône rationnel fidèle. En revanche, ils ne sont pas fermés par morphisme général.

• Le complémentaire d'un langage contextuel est contextuel. Ce résultat, longtemps ouvert, a été établi en 1988 par Immerman^[2] et Szelepcsényi^[3], et leur a valu le prix Gödel en 1995.

• Les langages contextuels sont donc clos par intersection.

Voir aussi

• Automate linéairement borné
• Hiérarchie de Chomsky
• Langage algébrique
• Langage rationnel
• Grammaire non contractante – ces grammaires engendrent exactement les langages contextuels
• Langage indexé – plus généraux que les langages algébriques, ils forment un sous-ensemble propre des langages contextuels.

Notes

1. ↑ Hopcroft et al. (2001)
2. ↑ Immerman (1988)
3. ↑ Szelepcsényi (1988)

References

• Neil Immerman, « Nondeterministic space is closed under complementation », dans Journal on Computing, vol. 17, n^o 5, 1988, p. 935–938 [texte intégral, lien DOI] 
• R. Szelepcsényi, « The method of forcing for nondeterministic automata », dans Acta Informatica, vol. 26, n^o 3, 1988, p. 279-284 

Bibliographie

• (en) Michael Sipser, Introduction to the Theory of Computation, Boston, PWS Publishing Company, 1996 (ISBN 978-0-534-95250-1) (LCCN 95020694) 

• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Boston, Addison-Wesley, 2001, 2^e éd., poche (ISBN 978-0-201-44124-6) 

• Pierre Wolper, Introduction à la calculabilité, Paris, Dunod, 2006, 3^e éd. (ISBN 978-2-10-049981-6) 

Traduction

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