Langage algébrique

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 ${\displaystyle \{a^{n}b^{n}c^{m}\mid n,m>0\}}$ et ${\displaystyle \{a^{n}b^{m}c^{m}\mid n,m>0\}}$ est ${\displaystyle \{a^{n}b^{n}c^{n}\mid n>0\}}$. 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[2] ;
• l'intersection d'un langage algébrique et d'un langage rationnel est toujours algébrique[2] ;
• 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és par transduction rationnelle, donc forment un cône rationnel ;
• les langages algébriques sont fermés pour les opérations rationnelles (union, produit, étoile), donc forment une famille abstraite de langages.

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

1. ${\displaystyle \sigma (\varepsilon )=\{\varepsilon \}}$ ;
2. ${\displaystyle \sigma (xy)=\sigma (x)\sigma (y)}$ pour des mots ${\displaystyle x}$ et ${\displaystyle y}$.

Dans la deuxième formule, le produit est le produit des parties de ${\displaystyle B^{*}}$.

Une substitution ${\displaystyle \sigma }$ est algébrique si ${\displaystyle \sigma (a)}$ est un langage algébrique pour toute lettre ${\displaystyle a}$.

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

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[3].

Mais contrairement aux langages rationnels, de nombreux autres problèmes sur les langages algébriques sont indécidables. Par exemple, il n'existe pas d'algorithme pour décider si deux langages algébriques donnés sont égaux[4]. Plus précisément, les propriétés suivantes sont indécidables. Soient ${\displaystyle L}$, ${\displaystyle L_{1}}$, ${\displaystyle L_{2}}$ des langages algébriques, donnés par exemple par leurs grammaires, sur un alphabet ${\displaystyle A}$, et soit ${\displaystyle R}$ un langage rationnel. Sont indécidables :

• ${\displaystyle L_{1}\cap L_{2}=\emptyset }$ ;
• ${\displaystyle L=A^{*}}$ ;
• ${\displaystyle L_{1}=L_{2}}$ ;
• ${\displaystyle L_{1}\subset L_{2}}$ ;
• ${\displaystyle L=R}$ ;
• ${\displaystyle R\subset L}$ ;
• Le complémentaire de ${\displaystyle L}$ est algébrique ;
• ${\displaystyle L_{1}\cap L_{2}}$ est algébrique ;
• ${\displaystyle L}$ est rationnel ;
• ${\displaystyle L}$ est inhéremment ambigu. Il est même indécidable qu'une grammaire donnée soit inambiguë.

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[5]. 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 de la clôture par complémentaire et de la non-clôture par intersection) ;
• elle n'est pas close par concaténation (l'étoile de Kleene ${\displaystyle L_{1}^{*}}$ du langage ${\displaystyle L_{1}}$ défini plus haut est algébrique déterministe, mais pas ${\displaystyle L_{1}^{*}.L_{2}}$) ;
• elle n'est pas close par miroir, par exemple, ${\displaystyle \{ca^{n}b^{n}\}\cup \{da^{2n}b^{n}\}}$ est algébrique déterministe mais pas ${\displaystyle \{b^{n}a^{n}c\}\cup \{b^{n}a^{2n}d\}}$.

Un langage algébrique est inambigu ou non ambigu s'il existe une grammaire inambiguë 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 ${\displaystyle \{a^{n}b^{n}c^{m}\mid n,m\geq 0\}\cup \{a^{n}b^{m}c^{m}\mid n,m\geq 0\}}$. Ceci se prouve à l'aide du lemme d'Ogden.

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

Le « langage le plus difficile » (hardest language en anglais) a été défini par Sheila Greibach 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 ${\displaystyle L}$ sur un alphabet ${\displaystyle A}$, la version non déterministe de ${\displaystyle L}$, et le langage noté ${\displaystyle N(L)}$ défini comme suit. On ajoute à ${\displaystyle A}$ les trois nouvelles lettres ${\displaystyle [,],{+}}$. Sur ce nouvel alphabet, on considère le langage ${\displaystyle K=([(A^{*}{+})^{*}A^{*}])^{*}}$. Tout mot ${\displaystyle h}$ de ${\displaystyle K}$ admet une factorisation

${\displaystyle h=[h_{1}][h_{2}]\cdots [h_{n}]}$

et chaque mot ${\displaystyle h_{i}}$ lui-même s'écrit sous la forme

${\displaystyle h_{i}=h_{i,1}{+}h_{i,2}{+}\cdots {+}h_{i,k_{i}}}$

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

${\displaystyle h_{1,j_{1}}h_{2,j_{2}}\cdots h_{n,j_{n}}}$

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

${\displaystyle N(L)=\{h\mid \chi (h)\cap L\neq \emptyset \}}$

Le langage le plus difficile est par définition le langage ${\displaystyle H}$ qui est la version non déterministe du langage de Dyck ${\displaystyle D_{2}^{*}}$ sur deux couples de parenthèses.

La terminologie vient du fait que le test d'appartenance d'un mot ${\displaystyle x}$ à ${\displaystyle L}$ se réduit au test d'appartenance du mot ${\displaystyle \varphi (\$x)}$ au langage ${\displaystyle H}$. Ainsi, tout algorithme de test d'appartenance à ${\displaystyle H}$ fournit un algorithme général de test d'appartenance, pour les langages algébriques, de même complexité. Des extensions du théorème à des grammaires plus générales ont été proposées par Alexander Okhotin[7].