Grammaire linéaire

Soit ${\displaystyle L=\{a^{n}b^{n}c^{m}d^{m}\mid n,m\geq 0\}}$. Ce langage est le produit de deux langages linéaires, mais n'est lui-même pas linéaire. Supposons le contraire, et soit ${\displaystyle N}$ la constante du lemme d'itération. Soit ${\displaystyle w=a^{N}b^{N}c^{N}d^{N}}$. Il existe une factorisation ${\displaystyle w=xuyvz}$ où ${\displaystyle u}$ est composé uniquement de lettres ${\displaystyle a}$ et ${\displaystyle v}$ uniquement de lettres ${\displaystyle d}$. Mais alors, le mot ${\displaystyle xu^{2}yv^{2}z}$ a plus de ${\displaystyle a}$ que de ${\displaystyle b}$ ou plus de ${\displaystyle d}$ que de ${\displaystyle c}$ (ou les deux), donc n'est pas dans ${\displaystyle L}$.

On appelle métalinéaire un langage qui est une union finie de produits finis de langages linéaires. Le langage ${\displaystyle L=\{a^{n}b^{n}c^{m}d^{m}\mid n,m\geq 0\}}$ 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és par l'opération étoile, ni par complément.

Un raffinement de cette classe est constitué par ce que l'on appelle les grammaires et langages ${\displaystyle k}$-linéaires, où ${\displaystyle k}$ est un entier positif. Une grammaire d'axiome ${\displaystyle S}$ est ${\displaystyle k}$-linéaire si toutes les règles sont de la forme

${\displaystyle X\to uYv}$ ou ${\displaystyle X\to w}$

où ${\displaystyle X}$ et ${\displaystyle Y}$ sont des variables autres que ${\displaystyle S}$, et ${\displaystyle u,v,w}$ des mots terminaux, et de plus, il y a une règle ${\displaystyle S\to uZv}$ où ${\displaystyle Z}$ est un produit d'au plus ${\displaystyle k}$ variables et ${\displaystyle u}$ et ${\displaystyle v}$ sont des mots terminaux. Un langage est ${\displaystyle k}$-linéaire s'il est engendré par une grammaire ${\displaystyle k}$-linéaire.

Les langages ${\displaystyle 1}$-linéaires sont les langages linéaires, les langages ${\displaystyle k}$-linéaires sont tous métalinéaires, et on peut montrer[1] - [2] que les langages métalinéaires sont la réunion des langages ${\displaystyle k}$-linéaires pour ${\displaystyle k\geq 1}$.

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

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

• ${\displaystyle f(\varepsilon )=\{\varepsilon \}}$
• ${\displaystyle f(xy)=f(x)f(y)}$ pour tous les mots ${\displaystyle x,y}$ de ${\displaystyle A^{*}}$.

Dans le membre droit de la deuxième formule, le produit est le produit des parties de ${\displaystyle B^{*}}$. Une substitution ${\displaystyle f}$ est rationnelle, algébrique, linéaire, etc., si les langages ${\displaystyle f(a)}$ sont rationnels, algébriques, linéaires, etc pour toute lettre ${\displaystyle a}$ de ${\displaystyle 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 ${\displaystyle G}$ est dite expansive s'il existe une variable ${\displaystyle X}$ pour laquelle il existe une dérivation de la forme

${\displaystyle X{\xrightarrow {*}}xXyXz}$

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

${\displaystyle 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.

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

Comme conséquence, le langage ${\displaystyle E}$ n'est pas quasi-rationnel, donc il est expansif.

Manuels

• Arto Salomaa, Formal Languages, New York, Academic Press, 1973 (ISBN 978-0-12-615750-5).

• 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), p. 111--174

Articles

• Juha Kortelainen, « Every commutative quasirational language is regular », RAIRO Inform. Théor. Appl., vol. 20, n^o 3,‎ 1986, p. 319--337

• Olga Martynova et Alexander Okhotin, « Non-closure under complementation for unambiguous linear grammars », Information and Computation, vol. 292,‎ juin 2023, article n^o 05031 (DOI 10.1016/j.ic.2023.105031)

• Tullio Ceccherini-Silberstein, « On the growth of linear languages », Advances in Applied Mathematics, vol. 35, n^o 3,‎ septembre 2005, p. 243–253 (DOI 10.1016/j.aam.2005.01.002)

• Volker Diekert, Steffen Kopecki et Victor Mitrana, « Deciding regularity of hairpin completions of regular languages in polynomial time », Information and Computation, vol. 217,‎ août 2012, p. 12–30 (DOI 10.1016/j.ic.2012.04.003)