Grammaire contextuelle

Une grammaire contextuelle (en anglais context-sensitive grammar) 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.

Sommaire

1 Définition formelle
- 1.1 Variante
- 1.2 Grammaire croissante
2 Exemples
3 Grammaires croissantes et grammaires contextuelles
4 Problèmes de décision
5 Applications
6 Notes
7 Références
8 Voir aussi
9 Traduction

Définition formelle

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

$uXv\to uxv$

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

Variante

Parfois, on permet la règle

$S\to\varepsilon$

où $ε$ désigne le mot vide, sous réserve que $S$ 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 être devoir préciser que l'inclusion est limitée aux langages ne contenant pas le mot vide.

Grammaire croissante

Une grammaire est croissante ou monotone si, pour toute règle $\alpha\to\beta$ , 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:

$XY\to ZT$

$X\to ZT$

$X\to Y$

$X\to a$

où $X, Y, Z, T$ sont des variables et $a$ 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 nommées ainsi d'après Sige-Yuki Kuroda (en).

Exemples

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

$S \to aSBC$
$S \to aBC$
$CB \to HB$
$HB \to HC$
$HC \to BC$
$aB \to ab$
$bB \to bb$
$bC \to bc$
$cC \to cc$

Les deux premières règles servent à engendrer les mots $a n (B C) n$ . Les trois règles suivantes permettent de remplacer $C B$ par $B C$ . La dérivation pour $a a a b b b c c c$ est la suivante:

$\begin{align} 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{align}$

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

$S \to abc$
$S \to aSBc$
$cB \to Bc$
$bB \to bb$

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

$S \rightarrow aAS | bBS | a\bar A|b\bar B$
$Aa \rightarrow aA$
$Ba \rightarrow aB$
$Ab \rightarrow bA$
$Bb \rightarrow bB$
$A\bar A \rightarrow \bar A a$
$B\bar A \rightarrow \bar B a$
$A\bar B \rightarrow \bar A b$
$B\bar B \rightarrow \bar B b$
$a\bar A \rightarrow aa$
$b\bar A \rightarrow ba$
$a\bar B \rightarrow ab$
$b\bar B \rightarrow bb$

La dérivation de abaaba est la suivante:

$\begin{align} 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 Aba \Rightarrow_{10} abaaba \end{align}$

Grammaires croissantes et grammaires contextuelles

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

$X_1X_2\cdots X_n\to Y_1Y_2\cdots Y_m$

où $m\ge n\ge1$ et tous les symboles sont des variables. On remplace une telle règle par l'ensemble suivant:

$\begin{align} X_1X_2\cdots X_n&\to Z_1X_2\cdots X_n\\ Z_1X_2\cdots X_n&\to Z_1Z_2\cdots X_n\\ &\cdots\\ Z_1Z_2\cdots Z_{n-1}X_n&\to Z_1Z_2\cdots Z_{n-1} Y_nY_{n+1}\cdots Y_m\\ Z_1Z_2\cdots Z_{n-1}Y_nY_{n+1}\cdots Y_m&\to Z_1Z_2\cdots Z_{n-2}Y_{n-1} Y_nY_{n+1}\cdots Y_m\\ &\cdots\\ Z_1Z_2Y_3\cdots Y_m&\to Z_1Y_2Y_3\cdots Y_m\\ Z_1Y_2\cdots Y_m&\to Y_1Y_2\cdots Y_m\,. \end{align}$

Par exemple, la règle suivante:

$X_1X_2X_3\to Y_1Y_2Y_3Y_4Y_5$

est transformée en

$\begin{align} X_1X_2X_3&\to Z_1X_2X_3\\ Z_1X_2X_3&\to Z_1Z_2X_3\\ Z_1Z_2X_3&\to Z_1Z_2Y_3Y_4Y_5\\ Z_1Z_2Y_3Y_4Y_5&\to Z_1Y_2Y_3Y_4Y_5\\ Z_1Y_2Y_3Y_4Y_5&\to Y_1Y_2Y_3Y_4Y_5 \end{align}$

Problèmes de décision

Le problème de savoir si un mot x appartient au langage engendré par une grammaire contextuelle donnée est décidable, mais il est complet dans la classe PSPACE, 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.

Applications

On a constaté que les langues naturelles peuvent être décrites, en général, par des grammaries contextuelles. Toute fois, 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 grammaires faiblement contextuelles (en), les grammaire d'arbres adjoints, les grammaires catégorielles combinatoire (en), ou d'autres systèmes. Le langages engendrés par ces grammaires se rangent strictement entre les langages algébriques et les langages contextuels.

Notes

↑ Noam Chomsky, « Three models for the description of language », dans IRE Transactions on Information Theory, n^o 2, 1956, p. 113–124 [texte intégral]
↑ Carton (2008), page 158-159

Références

Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008 (ISBN 978-2-7117-2077-4)

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

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

Voir aussi

Traduction

(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)

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Grammaire contextuelle de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

Grammaire Formelle — Une grammaire est un formalisme permettant de définir une syntaxe et donc un langage formel, c est à dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation… … Wikipédia en Français
Grammaire formelle — Une grammaire est un formalisme permettant de définir une syntaxe et donc un langage formel, c est à dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation… … Wikipédia en Français
Grammaire Non Contextuelle — En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement… … Wikipédia en Français
Grammaire Indépendante du Contexte — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… … Wikipédia en Français
Grammaire algébrique — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… … Wikipédia en Français
Grammaire hors-contexte — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… … Wikipédia en Français
Grammaire hors contexte — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… … Wikipédia en Français
Grammaire indépendante du contexte — Grammaire non contextuelle En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de… … Wikipédia en Français
Grammaire Universelle — La grammaire universelle, sous sa forme actuelle, a été pensée par Noam Chomsky, elle a pour but de s appliquer à n importe quel langage humain, que ce soit sous sa forme écrite ou verbale. L origine de cette conception, reconnue par Chomsky,… … Wikipédia en Français
Grammaire non contextuelle — En linguistique et en informatique, une grammaire non contextuelle, grammaire hors contexte ou grammaire algébrique (type 2 dans la hiérarchie de Chomsky) est une grammaire formelle dans laquelle chaque règle de production (ou simplement… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Grammaire contextuelle

Sommaire