Grammaire contextuelle

Une grammaire contextuelle est une grammaire formelle dans laquelle les substitutions d'un symbole non terminal sont soumises à la présence d'un contexte gauche et d'un contexte droit. Elles sont plus générales que les grammaires algébriques. Les langages formels engendrés par les grammaires contextuelles sont les langages contextuels. Ils sont reconnus par les automates linéairement bornés.

Les grammaires contextuelles ont été décrites par Noam Chomsky[1]. Ce sont les grammaires de type 1 dans la hiérarchie de Chomsky. Elles peuvent servir à décrire la syntaxe de langages naturels où il apparaît qu'un mot est approprié dans un certain contexte, mais ne l'est pas par ailleurs.

Définition formelleModifier

Une grammaire formelle  , (où   est l'ensemble des variables ou symboles non terminaux et   est l'alphabet terminal ou l'ensemble des symboles terminaux) est contextuelle si toutes les règles de   sont de la forme

 

 ,   et   sont des mots quelconques, avec   non vide, et   est une variable. Ainsi, le remplacement de   par   se fait en présence du « contexte »  .

VarianteModifier

Parfois, on permet la règle

 

  désigne le mot vide, sous réserve que   n'apparaisse pas dans un membre droit de règle. Cette convention technique permet de considérer les langages contextuels comme un sur-ensemble des langages algébriques, sans devoir préciser que l'inclusion est limitée aux langages ne contenant pas le mot vide.

Grammaire croissanteModifier

Une grammaire est croissante ou monotone si, pour toute règle  , la longueur de   est inférieure ou égale à la longueur de  . On sait transformer une grammaire croissante en une grammaire contextuelle (voir ci-dessous). Par conséquent, Les langages engendrés par les grammaires croissantes sont exactement les langages contextuels ne contenant pas le mot vide.

Une grammaire est en forme normale de Kuroda si les règles sont de l'une des formes suivantes :

 
 
 
 

  sont des variables et   est une lettre terminale. Les grammaires en forme normale de Kuroda sont croissantes. Réciproquement, on sait transformer une grammaire croissante en une grammaire en forme normale de Kuroda. Par conséquent, ces grammaires engendrent exactement les langages contextuels ne contenant pas le mot vide. Elles sont ainsi nommées d'après Sige-Yuki Kuroda.

ExemplesModifier

  • La grammaire suivante engendre le langage non algébrique   :
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  

Les deux premières règles servent à engendrer les mots  . Les trois règles suivantes permettent de remplacer   par  . La dérivation pour   est la suivante :


 


Le même langage peut être engendré par la grammaire croissante suivante :

  1.  
  2.  
  3.  
  4.  


  • La grammaire croissante suivante engendre le langages non algébrique des carrés   :
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  


La dérivation de abaaba est la suivante :

 

Grammaires croissantes et grammaires contextuellesModifier

Voici comment on peut transformer une grammaire croissante en une grammaire contextuelle[2]. Quitte à introduire de nouvelles règles de la forme  , où   est une lettre, on peut supposer toutes les règles de la forme

 

  et tous les symboles sont des variables. On remplace une telle règle par l'ensemble suivant :

 

Par exemple, la règle suivante :

 

est transformée en

 


Problèmes de décisionModifier

  • Le problème de savoir si un mot x appartient au langage engendré par une grammaire contextuelle donnée est décidable et PSPACE-complet[3], au sens de la complexité algorithmique.
  • Le problème de décider si le langage engendré par une grammaire contextuelle est vide est indécidable[4].

ApplicationsModifier

On a constaté[5] que les langues naturelles peuvent être décrites, en général, par des grammaires contextuelles. Toutefois, la classe des langages contextuels est bien plus large que celle des langues naturelles. De plus, comme le problème de décision est complet pour PSPACE, cette description n'est pas utilisable en pratique. C'est pourquoi la linguistique s'est orientée vers l'élaboration de modèles de grammaires plus spécifiques, comme les grammaire d'arbres adjoints, les grammaires catégorielles combinatoires (en), ou d'autres systèmes. Les langages engendrés par ces grammaires sont légèrement contextuels (en) et se rangent strictement entre les langages algébriques et les langages contextuels.

NotesModifier

  1. (en) Noam Chomsky, « Three models for the description of language », IRE Transactions on Information Theory, no 2,‎ , p. 113–124 (lire en ligne)
  2. Carton (2008), page 158-159
  3. Michael R. Garey et David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, New York, W. H. Freeman, (ISBN 0-7167-1045-5) — Problème AL3, « Linear bounded automaton acceptance », page 265.
  4. John E. Hopcroft et Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley, (ISBN 0201029839, SUDOC 004772571) — Section 14.7 pages 230-23.
  5. Voir par exemple Solomon Marcus, « Contextual Grammars and Natural Languages », dans Grzegorz Rozenberg et Arto Salomaa (éditeurs), Handbook of Formal Languages, vol. 2 : Linear Modeling: Background and Application, Springer Science & Business Media, , 528 p. (ISBN 9783540606482), ​Chap. 5, p. 215-236.

RéférencesModifier

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

Source de la traductionModifier