Grammaire contextuelle

Une grammaire formelle ${\displaystyle G=(V,A,P,S)}$, (où ${\displaystyle V}$ est l'ensemble des variables ou symboles non terminaux et ${\displaystyle A}$ est l'alphabet terminal ou l'ensemble des symboles terminaux) est contextuelle si toutes les règles de ${\displaystyle P}$ sont de la forme

${\displaystyle uXv\to uxv}$

où ${\displaystyle u}$, ${\displaystyle v}$ et ${\displaystyle x}$ sont des mots quelconques, avec ${\displaystyle x}$ non vide, et ${\displaystyle X}$ est une variable. Ainsi, le remplacement de ${\displaystyle X}$ par ${\displaystyle x}$ se fait en présence du « contexte » ${\displaystyle (u,v)}$.

• La grammaire suivante engendre le langage non algébrique ${\displaystyle \{a^{n}b^{n}c^{n}|n\geq 1\}}$ :

1. ${\displaystyle S\to aSBC}$
2. ${\displaystyle S\to aBC}$
3. ${\displaystyle CB\to HB}$
4. ${\displaystyle HB\to HC}$
5. ${\displaystyle HC\to BC}$
6. ${\displaystyle aB\to ab}$
7. ${\displaystyle bB\to bb}$
8. ${\displaystyle bC\to bc}$
9. ${\displaystyle cC\to cc}$

Les deux premières règles servent à engendrer les mots ${\displaystyle a^{n}(BC)^{n}}$. Les trois règles suivantes permettent de remplacer ${\displaystyle CB}$ par ${\displaystyle BC}$. La dérivation pour ${\displaystyle aaabbbccc}$ est la suivante :

${\displaystyle {\begin{aligned}S&\Rightarrow _{1}aSBC\Rightarrow _{1}a{\boldsymbol {aSBC}}BC\Rightarrow _{2}aa{\boldsymbol {aBC}}BCBC\\&\Rightarrow _{3}aaaB{\boldsymbol {HB}}CBC\Rightarrow _{4}aaaB{\boldsymbol {HC}}CBC\Rightarrow _{5}aaaB{\boldsymbol {BC}}CBC\\&\Rightarrow _{3}aaaBBC{\boldsymbol {HB}}C\Rightarrow _{4}aaaBBC{\boldsymbol {HC}}C\Rightarrow _{5}aaaBBC{\boldsymbol {BC}}C\\&\Rightarrow _{3}aaaBB{\boldsymbol {HB}}CC\Rightarrow _{4}aaaBB{\boldsymbol {HC}}CC\Rightarrow _{5}aaaBB{\boldsymbol {BC}}CC\\&\Rightarrow _{6}aa{\boldsymbol {ab}}BBCCC\Rightarrow _{7}aaa{\boldsymbol {bb}}BCCC\Rightarrow _{7}aaab{\boldsymbol {bb}}CCC\\&\Rightarrow _{8}aaabb{\boldsymbol {bc}}CC\Rightarrow _{9}aaabbb{\boldsymbol {cc}}C\Rightarrow _{9}aaabbbc{\boldsymbol {cc}}\end{aligned}}}$

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

1. ${\displaystyle S\to abc}$
2. ${\displaystyle S\to aSBc}$
3. ${\displaystyle cB\to Bc}$
4. ${\displaystyle bB\to bb}$

• La grammaire croissante suivante engendre le langages non algébrique des carrés ${\displaystyle C=\{xx|x\in \{a,b\}^{+}\}}$ :

1. ${\displaystyle S\rightarrow aAS|bBS|a{\bar {A}}|b{\bar {B}}}$
2. ${\displaystyle Aa\rightarrow aA}$
3. ${\displaystyle Ba\rightarrow aB}$
4. ${\displaystyle Ab\rightarrow bA}$
5. ${\displaystyle Bb\rightarrow bB}$
6. ${\displaystyle A{\bar {A}}\rightarrow {\bar {A}}a}$
7. ${\displaystyle B{\bar {A}}\rightarrow {\bar {B}}a}$
8. ${\displaystyle A{\bar {B}}\rightarrow {\bar {A}}b}$
9. ${\displaystyle B{\bar {B}}\rightarrow {\bar {B}}b}$
10. ${\displaystyle a{\bar {A}}\rightarrow aa}$
11. ${\displaystyle b{\bar {A}}\rightarrow ba}$
12. ${\displaystyle a{\bar {B}}\rightarrow ab}$
13. ${\displaystyle b{\bar {B}}\rightarrow bb}$

La dérivation de abaaba est la suivante :

${\displaystyle {\begin{aligned}S&\Rightarrow _{1}aAS\Rightarrow _{1}aAbBS\Rightarrow _{1}aAbBa{\bar {A}}\\&\Rightarrow _{4}abABa{\bar {A}}\Rightarrow _{3}abAaB{\bar {A}}\Rightarrow _{2}abaAB{\bar {A}}\\&\Rightarrow _{7}abaA{\bar {B}}a\Rightarrow _{8}aba{\bar {A}}ba\Rightarrow _{10}abaaba\end{aligned}}}$

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

${\displaystyle X_{1}X_{2}\cdots X_{n}\to Y_{1}Y_{2}\cdots Y_{m}}$

où ${\displaystyle m\geq n\geq 1}$ et tous les symboles sont des variables. On remplace une telle règle par l'ensemble suivant :

${\displaystyle {\begin{aligned}X_{1}X_{2}\cdots X_{n}&\to Z_{1}X_{2}\cdots X_{n}\\Z_{1}X_{2}\cdots X_{n}&\to Z_{1}Z_{2}\cdots X_{n}\\&\cdots \\Z_{1}Z_{2}\cdots Z_{n-1}X_{n}&\to Z_{1}Z_{2}\cdots Z_{n-1}Y_{n}Y_{n+1}\cdots Y_{m}\\Z_{1}Z_{2}\cdots Z_{n-1}Y_{n}Y_{n+1}\cdots Y_{m}&\to Z_{1}Z_{2}\cdots Z_{n-2}Y_{n-1}Y_{n}Y_{n+1}\cdots Y_{m}\\&\cdots \\Z_{1}Z_{2}Y_{3}\cdots Y_{m}&\to Z_{1}Y_{2}Y_{3}\cdots Y_{m}\\Z_{1}Y_{2}\cdots Y_{m}&\to Y_{1}Y_{2}\cdots Y_{m}\,.\end{aligned}}}$

Par exemple, la règle suivante :

${\displaystyle X_{1}X_{2}X_{3}\to Y_{1}Y_{2}Y_{3}Y_{4}Y_{5}}$

est transformée en

${\displaystyle {\begin{aligned}X_{1}X_{2}X_{3}&\to Z_{1}X_{2}X_{3}\\Z_{1}X_{2}X_{3}&\to Z_{1}Z_{2}X_{3}\\Z_{1}Z_{2}X_{3}&\to Z_{1}Z_{2}Y_{3}Y_{4}Y_{5}\\Z_{1}Z_{2}Y_{3}Y_{4}Y_{5}&\to Z_{1}Y_{2}Y_{3}Y_{4}Y_{5}\\Z_{1}Y_{2}Y_{3}Y_{4}Y_{5}&\to Y_{1}Y_{2}Y_{3}Y_{4}Y_{5}\end{aligned}}}$

• 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].

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.

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)

• Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1996, 239 p. (ISBN 0-534-95250-X)

• Pierre Wolper, Introduction à la calculabilité : cours et exercices corrigés, Paris, Dunod, 2006, 3^e éd., 224 p. (ISBN 2-10-049981-5)

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