Remerciez-le!

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

“Automates” — 2006/4/16 — 11:20 — page 1 — #1 i i i i i i i i Automates ﬁnis Je

“Automates” — 2006/4/16 — 11:20 — page 1 — #1 i i i i i i i i Automates ﬁnis Jean- ´ Eric Pin Mots-cl´ es : automate, langage, expression rationnelle, reconnaissable, automate s´ equentiel, industrie de la langue, v´ eriﬁcation, sp´ eciﬁcation. R´ esum´ e : introduits vers 1950, les automates ﬁnis constituent le mod` ele le plus ´ el´ ementaire de machine. Ce chapitre pr´ esente d’une part les automates usuels, qui se contentent de lire un mot en entr´ ee pour l’accepter ou le rejeter, et les automates s´ equentiels, munis d’une entr´ ee et d’une sortie. Apr` es une br` eve pr´ esentation du th´ eor` eme de Kleene, cl´ e de voˆ ute de la th´ eorie des automates, nous d´ ecrivons les applications des automates dans divers domaines, notamment la mod´ elisation et les industries de la langue. 1 Un bref historique La th´ eorie des automates est n´ ee de la conver- gence de plusieurs courants scientiﬁques. Le pre- mier est issu des tentatives de logiciens tels que Church, G¨ odel ou Turing pour formaliser la notion de calcul et de machine. Cet eﬀort a occup´ e toute la premi` ere moiti´ e du vingti` eme si` ecle et pourtant, les automates ﬁnis, qui constituent le mod` ele le plus simple de machine, ne seront d´ eﬁnis formel- lement que bien apr` es les machines de Turing. Les syst` emes dynamiques discrets forment la seconde source d’inspiration. Bien que leur ´ etude remonte aux travaux de Morse datant de la premi` ere moiti´ e du vingti` eme si` ecle, leurs liens avec les automates ﬁnis font encore ` a ce jour l’objet de recherches tr` es actives. Le troisi` eme courant, proche cou- sin du pr´ ec´ edent, est la th´ eorie de l’information bˆ atie par Shannon en 1948. Les probl` emes de co- dage, ´ etudi´ es notamment par Sch¨ utzenberger d` es les ann´ ees cinquante, ont en eﬀet profond´ ement inﬂuenc´ e la th´ eorie des automates. La quatri` eme source provient de linguistes tels que Chomsky qui, en cherchant ` a formaliser les langues natu- relles, ont introduit les concepts de mots, lan- gages, grammaires, que nous utilisons aujourd’hui. Le domaine des circuits ´ electroniques a ´ et´ e la cin- qui` eme source d’inspiration. Il a conduit notam- ment ` a la notion d’automate avec sortie et au concept de sp´ eciﬁcation du comportement d’un circuit. Les cinq domaines que nous venons d’´ evoquer bri` evement ont eu une inﬂuence consid´ erable sur la g´ en` ese et le d´ eveloppement de la th´ eorie des au- tomates. Mais historiquement, c’est un article sur les r´ eseaux neuronaux publi´ e en 1943 par McCul- loch et Pitts qui est ` a l’origine de la notion d’au- tomate. Il semble en eﬀet que le terme « th´ eorie des automates » ait ´ et´ e introduit en 1948 par Von Neumann en r´ ef´ erence ` a cet article. Par ailleurs, ` a la demande de la RAND Corporation, Kleene a longuement analys´ e cet article dans un m´ emoire r´ edig´ e durant l’´ et´ e 1951, mais publi´ e seulement en 1956. Cet article marque la naissance de la th´ eorie des automates. Kleene y d´ emontre un th´ eor` eme qui aﬃrme que les langages reconnus par un automate sont exactement les langages rationnels, appel´ es aussi langages r´ eguliers, que l’on peut d´ ecrire ` a par- tir des lettres de l’alphabet eu utilisant trois op´ erations : l’union (qui joue le rˆ ole de l’addi- tion), le produit et l’´ etoile. On obtient ainsi un proc´ ed´ e descriptif tout ` a fait diﬀ´ erent des auto- mates, et ce r´ esultat est assez surprenant. Il a pour cons´ equence que l’ensemble des langages ra- tionnels est ferm´ e par intersection et compl´ ement. Les automates avec sortie ont ´ et´ e introduits eux aussi ` a la ﬁn des ann´ ees cinquante. Un auto- mate avec sortie lit un mot en entr´ ee et produit un mot en sortie. Les mod` eles les plus int´ eressants sont les automates s´ equentiels, qui permettent d’obtenir la sortie au fur et ` a mesure de la lecture du mot d’entr´ ee. Ces automates sont tr` es proches des circuits ´ electroniques et leur synth` ese en cir- cuit peut d’ailleurs ˆ etre enti` erement automatis´ ee. 2 Mots et langages En informatique, mais aussi en math´ emati- ques, en linguistique ou en biologie, les informa- tions sont souvent repr´ esent´ ees par des chaˆ ınes de caract` eres. Par exemple pour les donn´ ees in- formatiques, on utilise des suites de 0 et de 1, pour l’information g´ en´ etique, des suites form´ ees des quatre caract` eres A (Ad´ enine), C (Cytosine), G (Guanine) et T (Thymine) et pour les langues naturelles, les mots ﬁgurant dans un dictionnaire. La formalisation commune ` a ces exemples est 1 “Automates” — 2006/4/16 — 11:20 — page 2 — #2 i i i i i i i i 2 Automates finis la suivante. Un alphabet est un ensemble ﬁni dont les ´ el´ ements sont appel´ es des lettres. Ainsi, on parle de l’alphabet binaire {0, 1}, de l’alphabet du g´ enome {A, C, G, T}, de l’alphabet latin usuel {a, . . . , z, A, . . . , Z}. Dans les exemples qui vont suivre, on utilisera le plus souvent des alphabets assez petits tels que {a, b} ou {a, b, c} et on notera A l’alphabet tout entier. Un mot sur l’alphabet A est une suite ﬁnie de lettres de A. On note ces lettres par simple juxtaposition : ainsi le mot abracadabra est un mot sur l’alphabet {a, b, c, d, r}. La longueur d’un mot u, not´ ee |u|, est ´ egale au nombre de lettres ﬁgurant dans u, chaque lettre ´ etant compt´ ee au- tant de fois qu’elle apparaˆ ıt. Ainsi, |abaabb| = 6 et |abracadabra| = 11. Il existe aussi un mot de longueur 0, que l’on note ε. Le produit (ou concat´ enation) de deux mots est le mot obtenu en mettant ces mots bout ` a bout. Par exemple, le produit des mots abra et cadabra est le mot abracadabra. On note aussi un le produit de n mots ´ egaux ` a u. Ainsi, (ab)3 = ababab. On appelle langage tout ensemble de mots sur un alphabet donn´ e. Par exemple, les ensembles {aba, babaa, bb} et {anbn | n ⩾0} sont des lan- gages sur l’alphabet {a, b}. 3 Automates d´ eterministes La ﬁgure 1.1 repr´ esente un automate d´ eterministe. Cet automate poss` ede trois ´ etats, 1, 2 et 3, entour´ es par des cercles sur la ﬁgure. L’´ etat 1 est l’´ etat initial, ce qu’on indique par une ﬂ` eche entrante. Les ´ etats 2 et 3 sont des ´ etats ﬁnaux, ce qui est indiqu´ e par une ﬂ` eche sortante. Cet automate poss` ede aussi des transi- tions, repr´ esent´ ees par des ﬂ` eches ´ etiquet´ ees par des lettres. De plus, de chaque ´ etat sort au plus une ﬂ` eche d’´ etiquette donn´ ee. 1 2 3 a a b a Fig. 1.1 – Un automate Pour savoir si un mot est accept´ e ou non par l’au- tomate, on lit de gauche ` a droite les lettres de ce mot en partant de l’´ etat initial et en suivant les transitions. Si on parvient dans un ´ etat ﬁnal, ce mot est accept´ e, sinon, il est rejet´ e. Prenons par exemple le mot aab. En lisant ce mot en partant de l’´ etat initial 1, on utilise d’abord la transition d’´ etiquette a qui va de 1 vers 2, puis celle de 2 vers 2 d’´ etiquette a et enﬁn celle d’´ etiquette b de 2 vers 3. Comme 3 est un ´ etat ﬁnal, le mot aab est accept´ e par l’automate. Si on lit maintenant le mot aba en partant de l’´ etat initial 1, on utilise successivement les tran- sitions de 1 vers 2, de 2 vers 3 et enﬁn de 3 vers 1. ` A l’issue de la lecture du mot aba on arrive donc dans l’´ etat 1, qui n’est pas un ´ etat ﬁnal : le mot est rejet´ e par l’automate. Enﬁn, examinons le mot abb. Comme pour le mot aba, on commence par utiliser les transitions de 1 vers 2, puis de 2 vers 3, mais arriv´ e dans l’´ etat 3, on constate qu’il n’y a pas de transition d’´ etiquette b issue de 3. La lecture du mot ne peut donc se poursuivre et le mot est ´ egalement rejet´ e. 4 Langages reconnaissables L’ensemble des mots accept´ es par un auto- mate est par d´ eﬁnition le langage reconnu par l’automate. On dit qu’un langage est reconnais- sable s’il existe un uploads/Litterature/ automates-pdf.pdf