Next: Produit de concaténation Up: Home Page Previous: Combinatoire des automates

Langages reconnaissables et automates finis

J'ai apporté plusieurs contributions majeures à ce domaine, mais je commencerai par un petit rappel historique. L'origine de ces recherches remonte aux efforts de formalisation de l'informatique des années cinquante: les langages formels ont été introduits par les linguistes pour tenter de formaliser les langues naturelles et les automates finis ont servi à modéliser la notion de machine finie. La terminologie actuelle a d'ailleurs gardé trace de cette origine : on parle d' alphabet, qui est simplement un ensemble fini dont les éléments sont appelés des lettres, de mots (suites finies de lettres) et de langages (ensembles de mots). Un langage est dit reconnaissable s'il peut être défini à l'aide d'un automate fini.

On considère généralement que le premier résultat de cette théorie est le théorème de Kleene (1954) qui montre qu'un langage est reconnaissable si et seulement si il peut être engendré, à partir des lettres de l'alphabet, à l'aide des trois opérations union, produit et étoile (passage au sous-monoïde engendré). On trouve déjà dans cet énoncé l'une des caractéristiques qui ont fait la richesse de cette théorie: la mise en parallèle de propriétés issues d'horizons différents (ici, les automates finis d'un côtéet une description purement combinatoire de l'autre). Une conséquence de ce résultat est que les langages reconnaissables sont stables par intersection finie et par complémentation.

En résumé, les langages reconnaissables sont construits comme dans un jeu de construction à partir de composants de base (les lettres de l'alphabet) et quelques opérateurs fondamentaux : les opérations booléennes (union, intersection et complément), le produit (de concaténation) et l'étoile. La complexité d'un langage se mesure généralement par la succession des opérateurs qui ont abouti à sa construction.

Ainsi Schützenberger a caractérisé les langages obtenus en utilisant uniquement les opérations booléennes et le produit (mais pas l'étoile !) que l'on appelle tout naturellement langages sans étoile. Ce résultat marque l'irruption de l'algèbre dans le domaine. On montre que l'on peut attacher à chaque langage reconnaissable un semigroupe fini, appelésemigroupe syntactique et que l'on sait calculer de façon effective. Schützenberger a montré qu'un langage est sans étoile si et seulement si son semigroupe syntactique ne contient que des sous-groupes triviaux.

Les rapports entre langages reconnaissables et semigroupes syntactiques, pour différentes classes de langages ont alors fait l'objet de travaux très poussés dans les années 70 (Schützenberger , Mc Naughton, I. Simon, J. Brzozowski, etc.). Le formalisme commun à tous ces résultats a étémis en évidence par S. Eilenberg dans son célèbre théorème des variétés, énoncé en 1976 : il existe une correspondance bijective entre certaines classes de langages reconnaissables, les variétés de langages, et certaines classes de semigroupes finis, les variétés de semigroupes. Les variétés de langages sont des classes de langages reconnaissables fermées pour les opérations booléennes et quelques autres opérations, alors que les variétés de semigroupes finis peuvent être définies par des équations algébriques. Ainsi, le résultat de Schützenberger n'est pas un hasard, mais une règle: les propriétés algébriques sur les semigroupes finis correspondent de manière très précise à des propriétés combinatoires sur les langages reconnaissables.

J'ai établi [93] une extension très simple de ce résultat qui aurait pu être découverte quinze ans plus tôt, car elle ne fait pas appel à des techniques très sophistiquées. Les classes de langages que je considère, baptisées variétés positives, possèdent les mêmes propriétés que les variétés de langages, à l'exception de la fermeture par complémentation. Du point de vue algébrique, les semigroupes finis sont remplacés par des semigroupes ordonnés finis. Une fois ces modifications faites, on obtient encore un théorème des variétés, qui étend celui d'Eilenberg.

Il s'agit là d'une avancée très importante car elle permet d'étudier par des techniques purement algébriques plusieurs familles de langages dont on savait peu de choses auparavant. Le résultat s'étend par ailleurs aux mots infinis et je poursuis actuellement mes travaux dans cette direction.

J'ai étudié de façon détaillée les opérations sur les variétés. En effet, le théorème des variétés conduit à supposer que les opérations sur les variétés de langages correspondent à des opérations sur les variétés de semigroupes et réciproquement. Expliciter cette correspondance pour diverses opérations constitue un problème fondamental qui intéresse à la fois la classification des langages reconnaissables et celle des semigroupes finis. Bien entendu, on peut partir soit d'une opération sur les variétés de langages, soit inverser le procédé. Les opérations sur les variétés de langages que l'on considère sont généralement des opérateurs de fermeture associés à des opérations classiques définies sur les langages : produit, produit non ambigu et variantes, mélange, morphismes, substitutions inverses, étoile, plus (passage au semigroupe engendré), etc. Dans une direction un peu différente, j'ai donné une caractérisation de certaines familles de langages algébriques en termes de semigroupe. [17].

Les variétés de langages fermées par mélange (ou shuffle) avaient été étudiées par Perrot, qui avait caractérisé les variétés commutatives de ce type. En revanche, on ne savait presque rien sur les variétés non commutatives. J'ai montré une série de résultats qui tendaient à accréditer la conjecture suivante, qui vient d'être prouvée par Esik et Simon : la variété des langages rationnels est la seule variété non commutative fermée par mélange.

J'ai donné la liste des quatre variétés de langages fermées pour l'opération plus (passage au semigroupe engendré), complétant ainsi le résultat correspondant de Perrot pour l'opération étoile [5,9]. J'ai par ailleurs étudié diverses restrictions des opérations étoile et plus liées à la théorie des codes (cf. plus loin).

Les morphismes entre monoïdes libres qui préservent la longueur des mots constituent l'une des opérations les plus utiles de la théorie des langages. Straubing avait montré le lien entre cette opération sur les langages et l'opération qui associe à un semigroupe S le semigroupe P(S) des parties de S. Ces opérations s'étendent naturellement aux variétés de langages et de semigroupes. En réalité la plupart des problèmes qui se présentent dans cette voie sont contenus dans le problème de la classification des variétés de la forme PV, i.e. engendrées par des semigroupes de la forme P(S), où S varie dans V.

J'ai obtenu (en partie conjointement avec Margolis) une série de résultats intéressants sur ce problème. J'ai notamment résolu une question posée par Straubing en montrant que P³V = M (Pⁿ désignant le n-ième itéré de l'opérateur P) et que P²V = M si on se restreint aux variétés de groupes [14,32]. Des résultats complémentaires figurent dans [37,46].

J'ai donné avec J. Sakarovitch une méthode générale pour l'étude des opérations sur les langages [28,43]. Notre méthode, bien que fort simple, permet de rendre compte de façon très naturelle de toutes les constructions connues antérieurement et d'éclairer en particulier la construction du produit de Schützenberger de n semigroupes. Cette méthode, jointe à certains résultats de théorie des codes, m'a également permis d'étudier avec succès les variétés de langages associées au produit de deux variétés de semigroupes. Ces théorèmes techniques mais puissants, ont de nombreux corollaires intéressants qui améliorent sensiblement les résultats de ce type mentionnés dans le traité de S. Eilenberg.

Le résultat de Schützenberger évoqué plus haut conduit directement à un problème célèbre de théorie des langages, le problème de la hauteur d'étoile (à ne pas confondre avec le problème de la hauteur d'étoile restreinte). La hauteur d'étoile d'un langage L mesure le nombre minimum d'imbrications de l'opération étoile utilisées pour donner une expression de L. Ainsi les langages de hauteur d'étoile 0 sont les langages sans étoile caractérisés par Schützenberger. On sait qu'il existe des langages de hauteur d'étoile 0 et 1, mais on ne sait toujours pas s'il existe des langages de hauteur d'étoile 2, bien que plusieurs candidats aient été proposés. J'ai étudié ce problème en collaboration avec D. Thérien et H. Straubing [60,75]. Nous avons montré que la classe des langages de hauteur d'étoile au plus n est fermée par diverses opérations classiques (résiduels, morphismes alphabétiques inverses, etc...) et prouvé que les langages reconnus par certains types de semigroupes (notamment les groupes nilpotents de classe 2, etc...) sont tous de hauteur d'étoile 1 au plus. Il en résulte en particulier que l'un des candidats à la hauteur 2 proposé il y a dix ans est en fait un langage de hauteur d'étoile 1 ! Il s'agissait de l'ensemble de tous les mots sur l'alphabet {a,b,c} contenant un nombre pair d'occurrences du sous-mot abc.

Mes travaux sur les semigroupes inversifs m'ont permis d'étudier les langages associés à ce type de semigroupes [31,61].

Next: Produit de concaténation Up: Home Page Previous: Combinatoire des automates