Langage algébrique

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (.

En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui peut être engendré par une grammaire algébrique. De manière équivalente un langage algébrique est un langage reconnu par automate à pile.

Les langages algébriques forment les langages de type 2 dans la hiérarchie de Chomsky. Ils ont des applications importantes dans la description des langages de programmation et en linguistique. Ils interviennent également dans la description des langages XML.

Sommaire

1 Quelques exemples
2 Propriétés
3 Langages algébriques déterministes et inambigus
- 3.1 Langages déterministes
- 3.2 Langages inambigus
4 Théorèmes de représentation
5 Notes
6 Bibliographie
7 Voir aussi

Quelques exemples

Le langage
$\{a^n b^n \mid n \geqslant 0\} = \{\varepsilon, ab, aabb, aaabbb, \dots\} - Wikipedia Orange$
est l'exemple type de langage algébrique non rationnel.
Les expressions arithmétiques, utilisant les quatre opérations élémentaires, comme par exemple $a \times b + (a + b) / d - Wikipedia Orange$ , etc, forment un langage algébrique.

Pour montrer que ces langages sont algébriques, on donne une grammaire non contextuelle qui les engendre. Voir le paragraphe d'exemples de l'article en question pour plus de détails. Pour des langages plus compliqués, on peut utiliser des méthodes plus puissantes, comme les transductions rationnelles ou le fait que les langages algébriques forment une famille abstraite de langages.

Le langage
$\{a^nc^{m_1}d^{m_1}c^{m_2}d^{m_2}\cdots c^{m_n}d^{m_n}\mid n,m_1,\ldots,m_n\ge1\} - Wikipedia Orange$
est algébrique: il est obtenu à partir du langage $\{a^n b^n \mid n \ge1\}$ , en substituant, à chaque lettre $b$ , le langage $\{c^n d^n \mid n \ge1\} - Wikipedia Orange$ . Et comme les langages algébriques sont fermés par substitution (voir ci-dessous), le langage obtenu est algébrique.

Le langage de Goldstine $G$ sur deux lettre $a, b - Wikipedia Orange$ est l'ensemble des mots
$a^{n_1}ba^{n_2}b\cdots a^{n_p}b - Wikipedia Orange$
où $\scriptstyle p\ge1$ , $\scriptstyle n_i\ge0$ et $\scriptstyle n_j\ne j$ pour un $j$ avec $\scriptstyle 1\le j\le p - Wikipedia Orange$ . Pour vérifier que ce langage est algébrique, on part du langage algébrique
$\{a^pb^qc\mid p,q\ge0, q\ne p+1\} - Wikipedia Orange$
et on applique la substitution
$a\mapsto a^*b,\quad b\mapsto a,\quad c\mapsto b(a^*)b^*. - Wikipedia Orange$
Le langage $G - Wikipedia Orange$ est le résultat de cette substitution.
Le langage $G - Wikipedia Orange$ est lié au mot infini
$x=aba^2ba^3b\cdots a^nb\cdots - Wikipedia Orange$ .

En effet, le langage $G$ est l’ensemble des mots qui ne sont pas préfixes de mots de $x$ et qui se terminent par la lettre $b - Wikipedia Orange$ .

Propriétés

Tout langage rationnel est algébrique car il peut être décrit par une grammaire régulière, qui est un cas particulier de grammaire non contextuelle.

Propriétés de clôture

La classe des langages algébriques possède certaines propriétés de clôture :

L'union et la concaténation de deux langages algébriques sont des langages algébriques.
L'étoile d'un langage algébrique est algébrique.
L'intersection de deux langages algébriques ne l'est pas nécessairement. Par exemple, l'intersection des langages $\{a^n b^n c^m \mid n,m > 0\}$ et $\{a^n b^m c^m \mid n,m > 0\}$ est $\{a^n b^n c^n \mid n > 0\} - Wikipedia Orange$ . Ce langage n'est pas algébrique (on le prouve traditionnellement à l'aide d'un lemme d'itération pour les langages algébriques). Par conséquent, la classe des langages algébriques n'est pas non plus close par complémentaire.
L'image miroir d'un langage algébrique est un langage algébrique^{[a 1]}.
L'intersection d'un langage algébrique et d'un langage rationnel est toujours algébrique ^{[a 1]}.
L'image homomorphe, l'image homomorphe inverse d'un langage algébrique est algébrique.

De ces propriétés, il résulte que

Les langages algébriques sont fermées par transduction rationnelle, donc forment un cône rationnel.
Les langages algébriques sont fermées pour les opérations rationnelles (union, produit, étoile), donc forment une famille abstraite de langages.

Clôture par substitution

Une substitution de $A^*$ dans $B^*$ est une application $\sigma$ de $A^*$ dans l'ensemble des parties de $B^* - Wikipedia Orange$ qui est un morphisme de monoïde, c'est-à-dire vérifie les deux propriétés:

$\sigma(\varepsilon)=\{\varepsilon\} - Wikipedia Orange$
$\sigma(xy)=\sigma(x)\sigma(y)$ pour des mots $x$ et $y - Wikipedia Orange$ .

Dans la deuxième formule, le produit est le produit des parties de $B^* - Wikipedia Orange$ .

Un substitution $\sigma$ est algébrique si $\sigma(a)$ est un langage algébrique pour toute lettre $a - Wikipedia Orange$ .

Le théorème de substitution affirme que si $\sigma$ est une substitution algébrique, alors $\sigma(L)$ est un langage algébrique pour tout langage algébrique $L - Wikipedia Orange$ .

Propriétés indécidables

L'appartenance d'un mot à un langage algébrique est décidable; elle peut être testée grâce à l'algorithme CYK. On sait également décider si un langage algébrique (défini à partir d'une grammaire) est vide^{[a 2]}.

Mais contrairement aux langages rationnels, de nombreux autres problèmes sont les langages algébriques sont indécidables. Par exemple, il n'existe pas d'algorithme pour tester l'égalité de deux langages algébriques^{[a 3]}. Plus précisément, les propriétés suivantes sont indécidables. Soient $L$ , $L_1$ , $L_2$ des langages algébriques, donnés par exemple par leurs grammaires, sur un alphabet $A$ , et soit $R - Wikipedia Orange$ un langage rationnel. Il est indécidable

si $L_1\cap L_2 = \emptyset - Wikipedia Orange$ ;
si $L= A^* - Wikipedia Orange$ ;
si $L_1 = L_2 - Wikipedia Orange$ ;
si $L_1 \subset L_2 - Wikipedia Orange$ ;
si $L = R - Wikipedia Orange$ ;
si $R \subset L - Wikipedia Orange$ ;
si le complémentaire de $L - Wikipedia Orange$ est algébrique ;
si $L_1 \cap L_2 - Wikipedia Orange$ est algébrique ;
si $L - Wikipedia Orange$ est rationnel ;
si $L - Wikipedia Orange$ est inhéremment ambigu. Il est même indécidable si une grammaire donnée est inambiguë.

Langages algébriques déterministes et inambigus

Langages déterministes

Un langage algébrique est dit déterministe s'il est reconnu par un automate à pile déterministe.

La classe des langages algébriques déterministes contient la classe des langages rationnels et est strictement incluse dans celle des langages algébriques. Le contre-exemple type de langage algébrique non déterministe est l'ensemble des palindromes.

La définition implique que l'appartenance d'un mot à un langage algébrique déterministe peut être testée en temps linéaire, contrairement au cas des langages algébriques quelconques. En outre, tout langage algébrique déterministe peut être décrit par une grammaire LR(1) et réciproquement. Cela permet de les utiliser pour des applications pratiques. Ainsi, la plupart des langages de programmation sont des langages algébriques déterministes.

La classe des langages algébriques déterministes est close par complémentaire^{[b 1]}. Cependant :

elle n'est pas close par intersection (même contre-exemple que dans le cas non déterministe) ;
elle n'est pas close par union (conséquence des deux propriétés précédentes) ;
elle n'est pas close par concaténation (la fermeture de Kleene $L_1^*$ du langage $L_1$ défini plus haut est algébrique déterministe, mais pas $L_1^* . L_2 - Wikipedia Orange$ )
elle n'est pas close par miroir, par exemple, $\{c a^n b^n\} \cup \{d a^{2n} b^n\}$ est algébrique déterministe mais pas $\{b^n a^n c\} \cup \{b^n a^{2n} d\} - Wikipedia Orange$ .

Langages inambigus

Un langage algébrique est inambigu ou non ambigu s'il existe une grammaire inambigue qui l'engendre. Un langage qui n'est pas inambigu est inhéremment ambigu.

Tout langage déterministe est inambigu, mais les langages inambigus sont fermés par miroir, donc l'inclusion est stricte. Il existe des langages algébriques inhéremment ambigus, comme le langage $\{a^nb^nc^m\mid n,m\ge0\}\cup \{a^nb^mc^m\mid n,m\ge0\} - Wikipedia Orange$ . Ceci se prouve à l'aide du lemme d'Ogden.

Théorèmes de représentation

Trois théorèmes donnent une façon générale de représenter les langages algébriques^[1].

Théorème de Chomsky-Schützenberger

Article détaillé : Théorème de Chomsky-Schützenberger (langage formel).

Le théorème affirme que les langages de Dyck sont des langages algébriques « typiques ».

Théorème de Chomsky-Schützenberger — Un langage $L$ sur un alphabet $A$ est algébrique si et seulement s'il existe un langage de Dyck $D$ , un langage rationnel $K$ et un morphisme alphabétique $\varphi - Wikipedia Orange$ (c'est-à-dire tel que l'image d'une lettre est une lettre ou le mot vide) tels que

$L=\varphi(D\cap K) - Wikipedia Orange$ .

Théorème de Shamir

Théorème de Shamir — Un langage $L$ sur un alphabet $A$ est algébrique si et seulement s'il existe un alphabet $B$ , une lettre $b\in B$ et un morphisme $\Phi$ de $A^*$ dans l'ensemble des parties de $(B\cup\bar B)^* - Wikipedia Orange$ tels que

$L=\{u\in A^*\mid b\Phi(u)\cap D_B^*\ne\emptyset\} - Wikipedia Orange$ .

Ici, $\bar B$ est une copie disjointe de $B$ , et $D_B^*$ est le langage de Dyck sur $B\cup \bar B - Wikipedia Orange$

Théorème du langage le plus difficile, de Greibach

Le « langage le plus difficile » (hardest language en anglais) a été défini par Sheila Greibach (en) en 1973. C'est un langage où le test d'appartenance est le plus difficile, au sens que tout algorithme de test d'appartenance se traduit en un test d'appartenance pour tout autre langage algébrique.

Étant donné un langage $L$ sur un alphabet $A$ , la version non déterministe de $L$ , et le langage noté $N(L)$ défini comme suit. On ajoute à $A$ les trois nouvelles lettres $[,],{+}$ . Sur ce nouvel alphabet, on considère le langage $K=([(A^*{+})*A^*])^*$ . Tout mot $h$ de $K - Wikipedia Orange$ admet une factorisation

$h=[h_1][h_2]\cdots [h_n] - Wikipedia Orange$

et chaque mot $h_i - Wikipedia Orange$ lui-même s'écrit sous la forme

$h_i=h_{i,1}{+}h_{i,2}{+}\cdots{+}h_{i,k_i} - Wikipedia Orange$

où les mots $h_{i,j}$ sont sur l'alphabet $A$ . Un choix dans $h - Wikipedia Orange$ est un mot

$h_{1,j_1}h_{2,j_2}\cdots h_{n,j_n} - Wikipedia Orange$

obtenu en choisissant un facteur $h_{i,j_i}$ dans chaque $[h_i]$ . Notons $\chi(h)$ l'ensemble des choix dans $h$ . La version no déterministe de $L - Wikipedia Orange$ est défini par

$N(L)=\{h\mid \chi(h)\cap L\ne\emptyset\} - Wikipedia Orange$

Le langage le plus difficile est par définition le langage $H$ qui est la version non déterministe du langage de Dyck $D_2^* - Wikipedia Orange$ sur deux paires de parenthèses.

Théorème du langage le plus difficile (Greibach) — Un langage $L$ sur un alphabet $A$ est algébrique si et seulement s'il existe un morphisme $\varphi - Wikipedia Orange$ tel que l'on ait

$\$L=\varphi^{-1}(H) - Wikipedia Orange$ ,

où $H$ est le langage le plus difficile et $\$$ est une lettre qui n'est pas dans $A - Wikipedia Orange$ .

Le terminologie vient du fait que le test d'appartenance d'un mot $x$ à $L$ se réduit au test d'appartenance du mot $\varphi(\$x)$ au langage $H$ . Ainsi, tout algorithme de test d'appartenance à $H - Wikipedia Orange$ fournit un algorithme général de test d'appartenance, pour les langages algébriques, de même complexité.

Notes

↑ Autebert, Berstel, Boasson (1997)

Bibliographie

(en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley 2001. (ISBN 0-201-44124-1).

↑ ^{a et b} Chapitre 7, p. 285
↑ Chapitre 7, p. 296
↑ Chapitre 7, p. 302

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

↑ Section 4.4.4, p. 97

Jean-Michel Autebert, Langages algébriques, Masson, 1987 (ISBN 978-2-225-81087-9)

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

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)

Voir aussi

[4] Autebert, Berstel, Boasson (1997)

[p285-0] {a et b} Chapitre 7, p. 285

[p296-1] Chapitre 7, p. 296

[p302-2] Chapitre 7, p. 302

[3] Section 4.4.4, p. 97

[a 1]

[a 2]

[a 3]

[b 1]

[1]

encyclopédie par wikipédia

Affichages