Grammaire linéaire

Grammaire linéaire

En informatique théorique, et notamment en théorie des langages, on appelle grammaire linéaire une grammaire algébrique dont tous les membres droits de règles contiennent au plus un symbole non terminal. Un langage linéaire est un langage qui est engendré par une grammaire linéaire.

Les langages linéaires sont une sous-famille des langages algébriques. Les langages rationnels sont contenus dans cette famille.

Sommaire

Exemple

La grammaire dont les règles sont

S\to aSb\mid\varepsilon

est linéaire. Le langage engendré est

\{a^nb^n\mid n\ge0\}

qui est donc un langage linéaire non rationnel (comme on peut le voir en utilisant le lemme de l'étoile).

Rapport avec les grammaires rationnelles

Deux cas particuliers des grammaires linéaires sont les suivantes:

  • les grammaires linéaires gauches, aussi appelés grammaires rationnelles gauches, sont les grammaires où les variables, dans les membres droits de règles, se trouvent toutes au début du mot.
  • les grammaires linéaires droites, aussi appelés grammaires rationnelles droites, sont les grammaires où les variables, dans les membres droits de règles, se trouvent toutes à la fin du mot.

Ces grammaires engendrent des langages rationnels. En revanche, les grammaires où les variables se trouvent soit au début, soit à la fin du mot, c'est-à-dire telles que, dans une règle de la forme:

X\to uYv

on a u = ε ou v = ε, sont simplement une sorte de forme normale des grammaires linéaires, et permettent d'engendrer toute la famille. En effet, une règle de la forme

X\to uYv

se remplace simplement par

X\to uZ,\quad Z\to Yv.

Propriétés de clôture

La famille des langages linéaires est fermée par les opérations suivantes:

  • intersection avec un langage rationnel
  • image homomorphe
  • image homomorphe inverse

De manière équivalente, elle est fermée par transduction rationnelle, et elle constitue donc un cône rationnel (full trio en anglais).

De plus, les langages linéaires son fermés par union. En revanche, le produit de deux langages linéaires n'est pas nécessairement un langage linéaire.

Lemme d'itération pour les langages linéaires

Le lemme d'itération pour les langages algébriques adment une forme plus précise pour les langages linéaires:


Lemme d'itération pour les langages linéaires — Soit L un langage linéaire. Il existe un entier N tel que tout mot w de L de longueur |w|\ge N possède une factorisation w = xuyvz telle que

  1. 0 < | uv | ,
  2.  |xuvz|\le N et
  3. xu^nyv^nz \in L pour tout entier n\ge0.

Ainsi, le couple (u,v) de la paire itérante peut être choisie près du « bord » du mot.

Exemple d'application

Soit L=\{a^nb^nc^md^m\mid n,m\ge0\}. Ce langage est le produit de deux langages linéaires, mais n'est lui-même pas linéaire. Supposons le contraire, et soit N la constante du lemme d'itération. Soit w = aNbNcNdN. Il existe une factorisation w = xuyvzu est composé uniquement de lettres a et v uniquement de lettres d. Mais alors, le mot xu2yv2z a plus de a que de b ou plus de d que de c (ou les deux), donc n'est pas dans L.

Extensions

Langages métalinéaires

On appelle métalinéaire un langage qui est une union finie de produits finis de langages linéaires. Le langage L=\{a^nb^nc^md^m\mid n,m\ge0\} est métalinéaire.

Les langages métalinéaires forment un cône rationnel. En revanche, les langages métalinéaires ne sont pas fermées par l'opération étoile.

Langages quasi-rationnels

Les langages quasi-rationnels sont la fermeture, par substitution, des langages linéaires. Ces langages sont exactement les langages non expansifs.

Soient A et B deux alphabets. Un substitution de A * dans B * est un morphisme du monoïde libre A * dans le monoïde des parties de B * , donc une application f vérifiant les deux conditions suivantes:

  • f(ε) = {ε}
  • f(xy) = f(x)f(y) pour tous les mots x,y de A * .

Dans le membre droit de la deuxième formule, le produit est le produit des parties de B * . Un substitution f est rationnelle, algébrique, linéaire, etc, si les langages f(a) sont rationnels, algébriques, linéaires, etc pour toute lettre a de A. Dire que les langages quasi-rationnels sont la fermeture, par substitution, des langages linéaires revient à dire que cette famille contient les langages linéaires et est fermée par substitution linéaire.

Une grammaire algébrique G est dite expansive s'il existe une variable X pour laquelle il existe une dérivation de la forme

X\xrightarrow* xXyXz

pour des mots x,y,z. Dans cette définition, on suppose que X est une variable utile, c'est-à-dire qu'il existe une dérivation S\xrightarrow* uXv pour des mots u,v, et qu'il existe un mot w tel que X\xrightarrow*w. Par exemple, la grammaire

S\to aSbS\mid\varepsilon

qui engendre le langage de Dyck est expansive. Un langage est dit expansif si toutes les grammaires qui l'engendrent sont expansives. Le langage de Dyck est expansif.

Langages commutatifs

Pour vérifier qu'un langage est expansif, on peut parfois se servir du théorème de Kortelainen cité ci-dessous. Deux mots u et v sont commutativement équivalents si chaque lettre apparaît autant de fois dans u que dans v, en d'autres termes si u et v sont des anagrammes. Un langage L est commutatif s'il est fermé pour la relation d'équivalence commutative, c'est-à-dire si u et v sont commutativement équivalents et si u est dans L, alors v est dans L. Par exemple, le langage E sur {a,b} composé des mots qui ont autant de a que de b est commutatif.

Théorème (Kortelainen) — Un langage quasi-rationnel commutatif est rationnel.

Comme conséquence, le langage E n'est pas quasi-rationnel, donc il est expansif.


Bibliographie

  • Jean-Michel Autebert, Jean Berstel et Luc Boasson, « Context-free languages and pushdown automata », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 1 : Word, Language, Grammar, Springer Verlag, 1997 (ISBN 978-3540604204) 
  • Juha Kortelainen, « Every commutative quasirational language is regular », dans RAIRO Inform. Théor. Appl., vol. 20, no 3, 1986, p. 319--337 

Voir aussi



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Grammaire linéaire 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 D'égyptien Hiéroglyphique — Ce projet de grammaire d égyptien hiéroglyphique est le pendant du Lexique d égyptien hiéroglyphique. Il nécessite au préalable une connaissance des principes fondamentaux (phonèmes, signes figuratifs, déterminatifs) ; voir Hiéroglyphe.… …   Wikipédia en Français

  • Grammaire d'egyptien hieroglyphique — Grammaire d égyptien hiéroglyphique Ce projet de grammaire d égyptien hiéroglyphique est le pendant du Lexique d égyptien hiéroglyphique. Il nécessite au préalable une connaissance des principes fondamentaux (phonèmes, signes figuratifs,… …   Wikipédia en Français

  • Grammaire d'arbres adjoints — La grammaire d arbres adjoints, grammaire TAG, ou légèrement sensible au contexte est un formalisme d analyse grammaticale introduit par A.K. Joshi et ses collègues[1] en 1975. Ce formalisme a été utilisé à différentes fins, et particulièrement… …   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

  • Hieroglyphe lineaire — Hiéroglyphe linéaire Un hiéroglyphe linéaire est une version simplifié d un hiéroglyphe. L écriture linéaire (ou écriture réduite), fut inventée pour pallier deux problèmes majeurs de l écriture hiéroglyphique sacrée, à savoir un temps d… …   Wikipédia en Français

  • Hiéroglyphe Linéaire — Un hiéroglyphe linéaire est une version simplifié d un hiéroglyphe. L écriture linéaire (ou écriture réduite), fut inventée pour pallier deux problèmes majeurs de l écriture hiéroglyphique sacrée, à savoir un temps d exécution très long pour… …   Wikipédia en Français

  • Hiéroglyphe linéaire — Pour les articles homonymes, voir Hiéroglyphe (homonymie). Un hiéroglyphe linéaire est une version simplifiée d un hiéroglyphe. L écriture linéaire (ou écriture réduite), fut inventée pour pallier deux problèmes majeurs de l écriture… …   Wikipédia en Français

  • Equivalence faible — 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… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”