Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Avant-propos Qui trop embrasse, mal ´ etreint. Adage populaire On ne peut faire

Avant-propos Qui trop embrasse, mal ´ etreint. Adage populaire On ne peut faire l’amour avec toutes les femmes, mais il faut essayer. Autre adage L ongtemps, je me suis imagin´ e le bonheur de r´ ediger cet avant-propos. J’en roulais par avance des phrases enti` eres, pour me donner du cœur ` a l’ouvrage. Maintenant que j’y suis rendu, je comprends que la tˆ ache n’est pas moins ardue que le cœur de l’ouvrage. Comment justiﬁer la r´ edaction d’un livre sur la th´ eorie des automates ? encore un ! et si ´ epais ! Justiﬁer ? on peut toujours rˆ ever ; pr´ esenter peut-ˆ etre. ´ Etoile de la recherche en informatique dans les ann´ ees soixante, chapitre oblig´ e de l’enseignement de la discipline dans les ann´ ees soixante-dix quatre-vingt, la th´ eorie des automates semble avoir disparu des estrades et des amphith´ eatres. Et pourtant, on la retrouve, explicitement ou implicitement, au cœur ou en pr´ emisses de nombre des sujets de l’informatique qui font la mode ou l’actualit´ e. Pour tenter une expli- cation, je dirai que la th´ eorie des automates est l’alg` ebre lin´ eaire de l’informatique. Ceci est ` a double entente. Au sens propre, la th´ eorie des automates est de l’alg` ebre lin´ eaire ou peut ˆ etre vue comme telle, th´ eorie des matrices ` a coeﬃcients dans des alg` ebres idoines. Mais c’est plutˆ ot le sens ﬁgur´ e qui m’int´ eresse. La th´ eorie des au- tomates comme connaissance de base, fondamentale, connue de tous et utilis´ ee par tous, qui fait partie du « paysage intellectuel » depuis si longtemps qu’on ne l’y re- marquerait plus. Et pourtant, elle y est, elle le structure, elle l’organise ; la connaˆ ıtre permet de s’y orienter. Les automates ﬁnis sont le mod` ele de machine le plus simple, si simple qu’il prend des formes, qu’il apparaˆ ıt dans des contextes, qu’il se cache dans des utilisations aussi nombreux que divers. Je ne d´ ecrirai pas les avatars du mod` ele ni les applications de la th´ eorie des automates — tout au plus en ´ evoquerai-je quelques-uns. Je voudrais pr´ esenter cette th´ eorie pour elle-mˆ eme et je vais chercher ` a rendre sa richesse. Mais si ce livre est ´ epais, ce n’est pas seulement, ce n’est pas tellement parce que les automates ﬁnis posent tant de probl` emes, donnent lieu ` a tant de r´ esultats — dont je suis d’ailleurs loin de rendre compte en totalit´ e — mais parce que j’ai voulu donner de chaque propri´ et´ e l’explication la plus directe sans renoncer ` a la replacer VII VIII AVANT - PROPOS ensuite dans le cadre le plus g´ en´ eral. Les propri´ et´ es simples seront d´ emontr´ ees de fa¸ con simple puis interpr´ et´ ees comme des cas particuliers de propositions globales exprim´ ees dans des formulations plus abstraites, qu’elles aideront ` a comprendre. C’est pourquoi, dans la premi` ere partie de cet ouvrage, organis´ ee autour des notions de rationalit´ e et de reconnaissabilit´ e, je d´ eroule trois fois la mˆ eme histoire, chaque fois avec un point de vue, avec un bagage th´ eorique, diﬀ´ erents. La mati` ere prend du relief sous des ´ eclairages crois´ es. La seconde partie traite des relations entre mots r´ ealis´ ees par automate ﬁni. Ce sujet est exemplaire de la th´ eorie des automates, de la vari´ et´ e de ses m´ ethodes comme de celle de ses champs d’application. Les automates « avec sortie » sont susceptibles d’une pr´ esentation tr` es ´ el´ ementaire et pourtant certaines de leurs propri´ et´ es rel` event des m´ ethodes les plus alg´ ebriques. Leur ´ etude illustre l’utilit´ e de chacun des aspects de la th´ eorie qui auront ´ et´ e d´ evelopp´ es dans la premi` ere partie. Carte Apr` es le chapitre 0 qui regroupe les d´ eﬁnitions des structures qui seront utilis´ ees tout au long du livre, le chapitre I pr´ esente une « th´ eorie na¨ ıve » des automates ﬁnis, celle qui est enseign´ ee dans tous les ouvrages et qui commence — et souvent ﬁnit — avec la version ´ el´ ementaire du th´ eor` eme dit « de Kleene ». Je me suis in- terdit d’y utiliser tout autre structure que celle du mono¨ ıde libre : pas le moindre morphisme, pas le plus petit semigroupe ﬁni. J’y pr´ esente la notion d’expression rationnelle et aborde, prolongement naturel du th´ eor` eme de Kleene, le probl` eme de la transformation d’une expression en un automate soit, pour prendre une formu- lation plus vendeuse, la recherche d’un motif dans un texte. ´ El´ ementaire ne signiﬁe pas simpliste, et cette th´ eorie est d´ ej` a foisonnante. J’ai inclus dans ce chapitre deux belles propri´ et´ es combinatoires : la version n´ ecessaire et suﬃsante du « lemme de l’´ etoile » et la preuve que la « hauteur d’´ etoile » d’un langage rationnel peut ˆ etre arbitrairement grande. Le chapitre II reprend le sujet avec pour guide l’alg` ebre — c’est-` a-dire d’abord la notion de morphisme (de mono¨ ıdes, d’automates). La premi` ere cons´ equence de ce point de vue est la distinction entre action et automate, entre partie reconnaissable et partie rationnelle d’un mono¨ ıde quelconque, ce qui ´ eclaire d’un jour nouveau et la notion d’automate et le th´ eor` eme de Kleene. L’horizon s’ouvre si largement qu’il faut faire des choix et, en particulier, je n’aborde pas la th´ eorie dite « des vari´ et´ es » d´ ej` a trait´ ee dans plusieurs ouvrages. En revanche, j’ai d´ evelopp´ e deux points plus originaux : la notion de morphisme d’automates d’abord, qui me permet de d´ eﬁnir ce que j’appelle « le revˆ etement de Sch¨ utzenberger » d’un automate et qui me servira ` a plusieurs reprises dans la suite, et la d´ eﬁnition de ce que j’appelle « l’automate universel » d’un langage ensuite, qui est la reprise d’une construction due ` a Conway et qui permet, entre autres, de donner ` a la ﬁn du chapitre une nouvelle pr´ esentation du th´ eor` eme de McNaughton sur la hauteur d’´ etoile des langages ` a groupe. Une section est consacr´ ee ` a la structure de bon ordre partiel, structure fondamentale pour toute l’informatique th´ eorique et qui sera utilis´ ee ici en deux points cruciaux. AVANT - PROPOS IX J’´ etudie ensuite la famille des parties rationnelles dans deux structures : le groupe libre et le mono¨ ıde commutatif libre. Dans les deux cas, cette famille est une alg` ebre de Boole eﬀective et cela explique, au moins en partie, que c’est souvent dans un tel cadre que les automates ﬁnis permettent de d´ ecrire le comportement de proces- sus dont l’ensemble des ´ etats est inﬁni (comme les r´ eseaux de Petri, les automates temporis´ es, etc.) Le groupe libre est aussi la structure alg´ ebrique sous-jacente au comportement des automates ` a pile, tous sujets qui ne font pas partie de cet ou- vrage. Le chapitre III reprend encore une fois le sujet ` a la base. Il s’agit moins de g´ en´ eraliser encore que d’ajouter une dimension avec la prise en compte de la multi- plicit´ e des calculs : les « langages (formels) » deviennent des s´ eries formelles, les ac- tions des repr´ esentations (matricielles). L’´ epaisseur ainsi donn´ ee aux r´ esultats en fait mieux comprendre la nature profonde, les rattache ` a des domaines math´ ematiques plus classiques, aux m´ ethodes puissantes. Mˆ eme si je cherche ` a donner les ´ enonc´ es les plus g´ en´ eraux et traite des s´ eries sur les mono¨ ıdes gradu´ es, c’est le cas des s´ eries sur le mono¨ ıde libre, ` a coeﬃcients dans un corps, qui reste le plus riche et dans lequel il est possible de pr´ esenter la th´ eorie de la r´ eduction des repr´ esentations (due ` a Sch¨ utzenberger). Les deux derniers chapitres sont consacr´ es aux relations et fonctions r´ ealis´ ees par automate ﬁni. Le chapitre IV porte sur les relations en g´ en´ eral, ´ etudi´ ees d’abord de fa¸ con « na¨ ıve »— c’est-` a-dire en utilisant a minima les r´ esultats des chapitres II et III — puis de fa¸ con g´ en´ erale, ce qui pose le d´ elicat probl` eme de la d´ eﬁnition et du traitement des relations avec multiplicit´ e. ` A la place de la solution — due ` a Jacob et reprise par les autres auteurs qui traitent du sujet — de se restreindre aux seules re- lations dites « r´ egul´ ees », je propose de restreindre la multiplicit´ e aux semi-anneaux que j’appelle « raisonnables », ce qui n’´ elimine aucun des semi-anneaux usuels et suf- ﬁt ` a uploads/Litterature/ avant-propos-ext.pdf