FacultedessciencesDepartementdemathematiquesTheoriedesautomatesetlangagesformels1acb2adcb3a,c,db4bca5dca6b,c,da7a,bc8dc9a,b,c,da,bbdddAnneeacademique20092010MichelRigoTabledesmati`eresChapitreI. Motsetlangages 11. Premi`eresdenitions 12. Langages 103. Expressionsreguli`eresetlangagesassocies 154. Exercices 22ChapitreII. Automates 271. Automatesnisdeterministes 272. Automatesnondeterministes 293. Stabilitedeslangagesacceptesparautomate 394. Produitdautomates 435. Exercices 46ChapitreIII. Langagesreguliersetautomates 511. Desexpressionsauxautomates 512. Desautomatesauxexpressionsreguli`eres 543. Stabilitedelaregularite 574. Crit`eredenon-regularite 585. Exercices 61ChapitreIV. Automateminimal 631. Introduction 632. Congruencesyntaxique 643. Automateminimal 664. Constructiondelautomateminimal 725. Applications 776. Exercices 81ChapitreV. Quelquescomplementssurleslangagesreguliers 851. Transduction 852. Recherchedunmotdansuntexte 883. Fonctiondecomplexitedunlangageregulier 924. Monodesyntaxique 995. Langagessans etoile 1056. Exercices 109ChapitreVI. Introductionauxlangagesalgebriques 1151. Premi`eresdenitions 115iii Chapitre.Tabledesmati`eres2. Arbresdanalyse 1193. Uneillustrationdelambiguite 1224. Grammairesetlangagesreguliers 1265. AproposdelahierarchiedeChomsky 1286. Formesnormales 1307. Lemmedelapompe 1408. Automates` apile 1439. Stabiliteducaract`erealgebrique 15110. Untheor`emedeSch utzenberger 15211. Exercices 155Bibliographie 159Listedesgures 161Index 165CHAPITREIMotsetlangagesCe premier chapitre introduit quelques concepts fondamentauxde latheoriedeslangages formelsetdelacombinatoiresurlesmots. Lacom-binatoiredesmotsetudielesproprietesdessuitesdesymboles. Latheoriedes langages formels englobe la theorie des automates et sinteresse aux pro-prietesmathematiquesdeslangagesqui sontdesensemblesdemots. Elletrouvenotammentdesapplicationsenvericationetpourlacompilation.1. Premi`eresdenitionsDenitionI.1.1. Unalphabetestunensembleni. Unalphabetseraengeneraldesigneparunelettregrecquemajuscule. Ainsi, = a, b, c, = , , , , = 0, 1, = , , , sont des alphabets. Les elements dun alphabetsont appeles lettresousym-bolesExempleI.1.2. LebiologisteinteresseparletudedelADNutiliseraunalphabet ` a quatre lettres A, C, G, T pour les quatre constituants des g`enes:Adenine,Cytosine,GuanineetThymine.DenitionI.1.3. Soitunalphabet. Unmot surestunesuitenie(etordonnee)desymboles. Parexemple, abbacetbasontdeuxmotssurlalphabet a, b, c. Lalongueur dunmot west le nombrede symbolesconstituantcemot;onlanote [w[. Ainsi,[abbac[ = 5 et [ba[ = 2.Luniquemotdelongueur0estlemotcorrespondant` alasuitevide. Cemotsappellelemot videetonlenote. Lensembledesmotssurestnote. Parexemple,a, b, c= , a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, . . ..DenitionI.1.4. Siestunelettredelalphabet,pourtoutmotw=w1 wk ,ondenotepar[w[= #i 1, . . . , k [ wi= le nombre de lettres iapparaissant dans le mot w. Par exemple, [abbac[a=2et [abbac[c= 1.12 ChapitreI.MotsetlangagesSi lalphabetdecardinal n 1estordonne, onpourraleconsiderercommeunn-uple=(1, . . . , n). OndenitalorslafonctiondeParikh: Nnpar(w) = ([w[1, . . . , [w[n).Len-uple(w)estappelevecteurdeParikhdew. Ilestclairquesin > 1,alorsnestpasinjectif.DenitionI.1.5. Soitw = w1 w

unmotsur. Lesmots, w1, w1w2, . . . , w1 w1, w1 w

= wsontlesprexesdew. Unprexe dewdierent deetdewestditpropre.Defa consemblable,, w

, w1w

, . . . , w2 w

, w1 w

= wsontlessuxesdew. Unsuxedewestqualiedepropresildi`eredeet de w. Soient 1 i j . Le mot wi wjest un facteur du mot w. Onlenoteparfois w[i, j]. Unefoisencore,onparledefacteurproprelorsquecedernier di`ere de w et de . Lensemble des prexes (resp. suxes, facteurs)dewestnotePref(w)(resp. Su(w),Fac(w)).RemarqueI.1.6. Onpeutobserverquepuisqueestunensembleni,estdenombrable1.Rappelonsladenitiondunmonode.DenitionI.1.7. Soient Aunensembleet : AA Auneopera-tionbinaireinterneetpartoutdenie. LensembleAmunideloperation poss`ede une structure de monode si les proprietes suivantes sont satisfaites.Loperation estassociative:x, y, z A : (x y) z= x (y z).Ilexisteunneutre(unique)e Atelquex A : x e = e x = x.RemarqueI.1.8. Unmonode(A, ) qui esttel quetoutelementdeAposs`edeuninverseestungroupe.ExempleI.1.9. Toutgroupeestunmonode;(N, +)estunmonodequinestpasungroupe.Protons-enpourrappelerladenitiondunmorphismedemonodes.1En eet, les elements de peuvent chacun etre caracterises par un nombreni dindices prenant leur valeur dansdes ensembles denombrables (ici, il sagit memedensemblesnis,` asavoir).I.1.Premi`eresdenitions 3DenitionI.1.10. Soient(A, ) et (B, )deuxmonodesdeneutrere-spectifeAeteB. Uneapplicationf:A Bestunmorphisme(ouencorehomomorphisme)demonodessi(1) x, y A : f(x y) = f(x)f(y)et(2) f(eA) = eB.RemarqueI.1.11. Danslecasdunhomomorphismedegroupes,lacon-dition(2)estuneconsequencedirectede(1)etdelexistencedinverseauseindesgroupes2. Parcontre,danslecasdemonodes,lacondition(2)faitbeletbienpartiedeladenitiondunmorphismedemonodes.Denition I.1.12. Soit unalphabet. Ondenit loperationde con-catenationsur delafa consuivante. Pour tous mots u=u1 uketv = v1 v

,ui, vi , la concatenationde u et v,noteeu.vousimplementuv,estlemot Onutiliseradorenavantlanotationmultiplicative.w = w1 wk+o` u_wi= ui, 1 i kwk+i = vi, 1 i .Ainsi, muni deloperationdeconcatenationestunmonodedeneutre. Enparticulier, ondenit lapuissance n-i`eme dunmot wcomme laconcatenationdencopiesdew,wn= w w. .nfois.Onposew0= .RemarqueI.1.13. Il estutilederemarquerquesi#>1, alorsestunmonodenoncommutatif,i.e.,ilexisteu, v telsqueuv ,= vu.ExempleI.1.14. Lapplicationlongueur[[ : Nestunmorphismedemonodesentre(, .)et(N, +). Eneet,u, v : [uv[ = [u[ +[v[et [[ = 0.Exemple I.1.15. Considerons lalphabet = a, b, cet lemorphisme: denipar(a)=abc, (b)=acet(c)=b. Eneet, pourdenir un telmorphisme, onremarquera quil sut de sedonner limagedelettres. Ona,parexemple,(abbc) = (a)(b)(b)(c)= abcacacb.2pour tout x A,f(x) = f(eA x) = f(eA)f(x). Do` ulaconclusionenmultipliantparf(x)1.4 ChapitreI.MotsetlangagesVoici ` apresentquelquesproprietesclassiquesdecombinatoiredesmots(classication68R15delAmericanMathematical Society). Onsinteresseprincipalement aux congurations des lettres, des facteurs ou encore des mo-tifs pouvant apparatre dans un cadre non commutatif (caract`ere inevitable,frequencedapparition,etc.). Voir,parexemple,lexcellentsurvol[10].Proposition I.1.16. Sur unalphabet binaire, tout mot de longueur aumoins4contientuncarre,i.e.,unfacteurdelaformeuu,u ,= .Cetteproprietetrivialemontredoncquelapparitionduncarreestin-evitable sur un alphabetde deux lettres. Par contre, sur trois lettres,il nenestrien. Ainsi, laclassicationdesmotifsevitablesounonestloindetreaisee.Un mot inni sur un alphabet est simplement une application w : N (i.e., unesuitedelettresindexeepar N). Onpeutmunirlensembledesmotsinnissurdunedistanced : Rdeniecommesuit.Si xetysontdeuxmotsinnis, alorsx ydesigneleurpluslongprexecommun. Six = y,alorsonposed(x, y) = 0,sinond(x, y) = 2|xy|.On veriera aisement quil sagit bien dune distance. Cette distance poss`edeuneproprietesupplementaire, elleest ultrametrique3(onutiliseparfoisletermenon-archimedienne):x, y, z : d(x, z) maxd(x, y), d(y, z).Ayant ` anotredispositionunespacemetrique(, d), onpeut parler desuitesconvergentesdemotsinnis,etc. Soitcunelettrenappartenantpas` a. Onpeutplongerdans( c)enidentiantlemotniw avec le mot inni wccc (c). Cette identication faite, il est licitedeparlerdunesuitedemotsnisconvergeantversunmotinnilimite.PropositionI.1.17. Le mot inni (a) o` u(a) =abc, (b) =ac et(c) = b,estsanscarre.Onremarque facilement que n(a) est prexe de n+1(a) pour toutn 0. Il sutdeproceder par recurrence. Si n+1(a) =n(a)u, alorsn+2(a) = n+1(a)(u). De plus, la suite ([n(a)[)n0est strictement crois-sante. Pour ces deuxraisons et aveclatopologie associee ` alametriquepresentee precedemment, on peut dire que la suite (n(a))n0converge versunmotinnilimite.3Onrencontrenotamment cetypedeproprieteenanalysep-adique. Latopologieassocieeestinteressante: toutpointdunebouleenestlecentre, deuxboulesontuneintersectionnonvidesi et seulement si luneest inclusedanslautre, tout triangleestisoc`ele,etc.I.1.Premi`eresdenitions 50(a) = a1(a) = abc2(a) = abcacb3(a) = abcacbabcbac...Lademonstrationdufaitquelemotinnilimite(a)estsanscarre4sera donnee en n de section. En particulier, sur un alphabet de trois lettres,il existedesmots(nis)arbitrairementlongssanscarre. Pourobtenirceresultat, nousmontreronsdabordquil existe, surdeuxlettres, desmotsarbitrairementlongssanschevauchement.PropositionI.1.18. Deuxmots uet v commutent sils sont puissancesdunmemetroisi`eme, i.e., sil existeunmot wet desentiersi, j telsqueu = wietv = wj.Demonstration. Onproc`edepar recurrencesur lalongueur deuv. Si[uv[= 0,leresultatestimmediat. Supposons` apresentleresultatsatisfaitpour [uv[ q1etsir2= r1,alorsonauraitq2= (t2t1) p +t1p +r1. .=q1.Cela signierait alors que aq2appartient ` a ap, aq1. On peut alors eectuerlamemedemarcheavec ap, aq1, aq2et denirq3si L ,= ap, aq1, aq2.Cependant, on remarque quil y a au plus p1 restes non nuls distincts lorsdunedivisioneuclidienneparp. Parconsequent,onnesauraiteectuerceraisonnementindeniment etnalementL= ap, aq1, . . . , aqs avecs p 1.

DenitionI.2.10. On peut etendre les operations dobtention de prexes,suxesetfacteursauxlangages. SoitLunlangage. OndenitPref(L) =_wLPref(w)comme lensemble des prexes des mots du langage L. De la meme mani`ere,onposeSu(L) =_wLSu(w) et Fac(L) =_wLFac(w).14 ChapitreI.MotsetlangagesEnn, un langage L est prexiel si Pref(L) = L. Il sut donc de verier quetout prexe dun mot de L est encoreun mot de L. De lameme mani`ere,Lestsuxiel(resp. factoriel)siSu(L) = L(resp. Fac(L) = L).DenitionI.2.11. Soitfunmorphismedemonodesentreet. Onremarque que fest compl`etement caracterise par les images de fsur les sym-bolesde. SiLestunlangagesur,alorslimagedeLparlemorphismefestf(L) = f(u) [ u L.Delameme mani`ere,si Mest un langagesur , alorslimageinverse de Mparlemorphismefestf1(M) = u [ f(u) M.ExempleI.2.12. Soient = a, b, c, = , et fle morphisme deniparf(a) = , f(b) = , f(c) = .SiL = ab, bc, cb, aaab, aaac, alorsf(L) = , , .SiM= , , ,alorsf1(M) = ab, ac, ba, ca, bab, bac, cab, cac.Dans notreexemple, pour tout , [f()[ =1. Neanmoins, onpeutentoutegeneraliteconsidererunmorphismedontlesimagesdeslettresdelalphabetdorigineseraientdelongueursdierentes.Remarque I.2.13. Il arrive, dans de nombreuses situations, quondis-tingue le cas o` u il existe tel que f() = (onparle de morphismeef-fa cant), du cas o` u, pour tout , f() ,= (on utilise d`es lors lexpressionmorphismenonea cant).Dans lasectionprecedente, onaintroduitlemiroir dunmot. Cetteoperationsetendnaturellementauxlangages.DenitionI.2.14. LemiroirdunlangageLestLR= uR[ u L.OnpeutavoirL=LRsanspourautantquelesmotsdeLsoienttousdespalindromes.Denition I.2.15. La cl oture commutative dun langage L est denieparCom(L) = w [ u L : , [w[= [u[.CelasigniequeCom(L)contientlesmotsobtenusenpermutant leslettresdesmotsdeL. Parexemple,siL = ab, bac, ccc,alorsCom(L) = ab, ba, abc, acb, bac, bca, cab, cba, ccc.I.3.Expressionsreguli`eresetlangagesassocies 15EnutilisantlafonctiondeParikhintroduite` aladenitionI.1.4,ilestclairqueCom(L) = 1(L).SiLestunlangagetelqueCom(L) = L,alorsLestditcommutatif.Voiciunederni`ereoperationsurlesmotsetleslangages.DenitionI.2.16. Leshue13dedeuxmotsuetvestlelangageu.. v = u1v1 unvn [ u = u1 un, v = v1 vn, ui, vi , n 1.Parexemple14,siu = abetv = cde,alorsu.. v = abcde, acbde, acdbe, acdeb, cabde,cadbe, cadeb, cdabe, cdaeb, cdeab.Leshuededeuxlangagessedenitcommesuit,L.. M=_uL,vMu.. v.3. Expressionsreguli`eresetlangagesassociesLanotiondexpressionreguli`ereestdusagefrequenteninformatique.Eneet, onasouventrecours auxexpressions reguli`eres lorsquondesirerechercher certains motifs recurrents. Un exemple banal est celui dun reper-toirecontenantdiverschiers:> ls monrepertoire/memoire.aux memoire.tex picture001.jpg rapsody.jpgmemoire.dvi picture001.jpg presentation.exe raw.jpgmemoire.old picture002.jpg price-list.txtmemoire.log picture003.jpg taches.txtSi lutilisateurdesireacheruniquementlesimagesauformat JPEG etcomportantlextension.jpg,ilauraparexemplerecours` aunecommandecommels *.jpgDelamememani`ere, silveuteacertousleschiersrelatifs` amemoire,ilexecuterarm m*Onpourraitimaginer, dansunrepertoireplusfourni, vouloirselectionnerdeschiers dontlesnomssatisfont` adescrit`eresplusns. Nousallonsvoircommentdenircegenredecrit`eresdansleformalismedeveloppelorsdesprecedentessections.13Onpourraittenterdetraduirecetermepar melange. Nousavonschoisi decon-serverladenominationanglo-saxonne.14Nous avons pris ici deux mots nayant aucune lettre en commun pour rendrelexempleplus simple. Entoutegeneralite, onpeut biens ur prendredes mots posse-dantlesmemeslettres.16 ChapitreI.MotsetlangagesDenitionI.3.1. Soitunalphabet. Supposonsque0, e, +, ., (, ),sontdes symboles nappartenant pas ` a . Lensemble des expressions reguli`eressurestdenirecursivementpar0eteappartiennent` a ,pourtout ,appartient` a ,sietappartiennent` a ,alors( +)appartient` a ,(.)appartient` a ,appartient` a .ExempleI.3.2. Si = a, b, voici quelques exemples dexpressions regu-li`eres:1= (e + (a.b)),2= (((a.b).a) +b),3= ((a +b).(a.b)).Aune expression reguli`ere,onassocieun langagegr ace` alapplication15L : 2par L(0) = , L(e) = ,si ,alors L() = ,sietsontdesexpressionsreguli`eres, L[( +)] = L() L(), L[(.)] = L()L(), L() = (L()).ExempleI.3.3. Poursuivons lexempleI.3.2. OnaL(1) = , ab,L(2) = (aba b),L(3) = a, bab.Denition I.3.4. Un langage L sur est regulier sil existe une expressionreguli`ere tellequeL = L().Sietsontdeuxexpressionsreguli`erestellesque L()= L(), alorsonditqueetsont equivalentes.Remarque I.3.5. Dans la suite, on sautorisera ` a confondre une expressionreguli`ereetlelangagequellerepresente. Si aucuneconfusionnestpossi-ble,onsautoriseraegalement` aenleverlesparenth`esesouautressymbolessuperus. Parexemple,(((b.a).(b.a)).b) = (ba ba)b15Lanotation2designelensembledespartiesde, cest-` a-direlensembledeslangagessur. Ontrouveparfoislanotation P().I.3.Expressionsreguli`eresetlangagesassocies 17represente lelangageformedesmotssur a, bcomprenantunnombre pairde a. Onse convainc aisement que ce langage est aussi represente parlexpressionb (a ba b).PropositionI.3.6. Lensemble L()deslangagesregulierssurestlapluspetitefamilledelangagescontenant lelangagevide, leslangages reduits` aunelettre( )etquieststablepourlesoperationsdunion,deconcatenationetdetoiledeKleene.Demonstration. Pardenitionde etde L,ilestclairquelensembledeslangagesregulierssurverielesproprietes enoncees.Soit /un ensemble de langages satisfaisant les proprietes enoncees. Nousdevonsverierque L() /. SoitLunlangageregulier. Il existe tel que L() =L. Onproc`ede par recurrencesur lalongueur16delexpressionreguli`ere:Si vaut0, eou( ), alors L()vaut , = ou . Parconsequent,Lappartient` a /.Si= ( +)avecetdesexpressionsreguli`eressurdelongueurinferieure` acellede,alorsonaL() = L() L().Parhypoth`esederecurrence, L()et L()appartiennent` a /. Puisque /eststablepourlunion,onenconclutqueLappartient` a /.Si= (.)ou= ,onutiliselememeraisonnement.

RemarqueI.3.7. Dans lapropositionprecedente, onaurait pu remplacerlangages reduits ` aune lettre par langagesnis. Cest equivalent,auvudesproprietesdestabiliteenoncees.Puisquenousavonsdecidedesubstituerdeslangages auxexpressionsreguli`eres,lesrelationssuivantessontimmediates.PropositionI.3.8. Soituneexpressionreguli`ere. Ona += ,e = e = ,0 = 0 = 0,()= ,= 0+1+ +k+k+1,( +)= ().Dans le cas particulier dunalphabet unaire (i.e., contenant unseulsymbole),ondisposedunecaracterisationdeslangagesreguliers.16On peut denir la longueur dune expression reguli`ere de la mani`ere suivante. Soient, deuxexpressions reguli`eres. Si =0, eou(), alors || =1. De plus,|( +)| = || +|| + 1, |(.)| = || +|| + 1et || = || + 1.18 ChapitreI.MotsetlangagesProposition I.3.9. Soit =. Les langages reguliers sur sontexactementleslangagesdelaformei[ i Ao` uA Nestuneunionniedeprogressionsarithmetiques.Rappelonsquune progression arithmetiqueest unensemble de laformep +N.q = p +n.q [ n Navecp, q N.Demonstration. Nous avons dej` a remarque (cf. exemple I.1.14) quelapplication longueur est un morphisme de monodes entre (, .) et (N, +).Ici,lapplication[[ : N : nnestmemeunisomorphisme17demonodes. Lensemble Tdesunionsniesdeprogressionsarithmetiquesjouitdesproprietessuivantes: T(casdelunionvide), 1 Tcar 1 = 1 +N.0,lunionde deuxelements de Test encore unelement de T(eneet, luniondedeuxunionsniesdeprogressionsarithmetiquesestencoreuneunionniedeprogressionsarithmetiques),la somme de deux elements de Test encore un element de T. Pourleverier,puisque Teststablepourlunion,ilsutdeconsidererlecasdedeuxprogressionsarithmetiquesp + N.qetr + N.s. Siq = 0,alors(p +N.q) + (r +N.s) = (r +p) +N.s T.Siq > 0,alors(p +N.q) + (r +N.s) =_0i 0 0.Sip = 0,(N.q)= q= N.q T. Sip > 0,(p +N.q)= 0 _0i 0. Onap +n1q + +p +nj q = p + (j 1) p + (n1 + +nj) q.En eectuant la division euclidienne de n1++njpar p, on trouven1 + +nj= mp +i, avec 0 i < petdoncp +n1q + +p +nj q = p +i q + (j 1 +mq) pavec0 i < p.Supposons` apresentque Q 2Nest unefamilledepartiesdeNquicontient et 1 et qui est stable pour lunion, la somme et letoile. Montronsque T Q. Puisque Qeststablepourlunion,ilsutdemontrerquelesprogressions arithmetiques de la forme p +N.q, p, q N, appartiennent ` a Q.Puisque Q,ona = 0 Q. Enoutre, 1 Qetenutilisantlefaitque Qeststablepourladdition, onvoitque rappartient` a Qpourtoutr > 0. Onendeduitque,pourtousp, q N,p +N.q = p +qappartient` a Q.OnconclutenutilisantlapropositionI.3.6etlefaitquelapplicationlongueurestunisomorphismeentre(N, +)et(, .).

Lacontraposeeducorollairesuivantpermetparfoisdeverierquecer-tainslangagesnesontpasreguliers.20 ChapitreI.MotsetlangagesCorollaireI.3.10. SiL estunlangagereguliersurunalphabetniarbitraire,alorslensemble[L[ = [w[ : w L Nestuneunionniedeprogressionsarithmetiques.Demonstration. Soit une lettre de . On denit le morphisme : par() = pourtout . Ilest evidentque(L) = (w) [ w Lest unlangage regulier sur unalphabet unaire et [L[ = [(L)[. Onconclutgr ace` alapropositionprecedente.

DenitionI.3.11. UnepartieX NestditeultimementperiodiquesilexisteN 0etp > 0telsquen N, n X n +p X.Le plus petit entier p satisfaisant une telle propriete est appele la periode deXetlepluspetitNcorrespondantestparfoisappelelapreperiode.PropositionI.3.12. Unepartie X Nest ultimement periodiquesi etseulementsiXestuneunionniedeprogressionsarithmetiques.Demonstration. SupposonsquilexisteN 0etp > 0telsquen N, n X n +p X.D`es lors, Xsexprime comme une union nie de progressions arithmetiques,X=_ _xXx 0et que t(m, 0) = t(0, m) = 1. Utiliser cette formule pour en deduire la valeurde#(abba .. cd).24 ChapitreI.MotsetlangagesPour calculer t(m, n) aumoyende laformuledonneeci-dessus, combiendetapessontnecessaires?ExerciceI.4.16. Soit = a, bun alphabet binaire. Un mot w estsanscarresilnecontientaucunfacteurdelaformexxavecxunmotnonvide. Enumerertouslesmotssanscarrede. (Quesepasse-t-il danslecasdunalphabetcontenantplusdedeuxlettres?)Exercice I.4.17. Soit unalphabet. Unmot west primitif silequationw = ui, u nestsatisfaitepouraucunexposanti 2. Onappelleracineprimitivedew, le plus petit mot u tel que w = ui, pour un i 1. Demontrer quunmotestprimitifsietseulementsiilest egal` asapropreracineprimitive.ExerciceI.4.18. Deuxmotsuetvsursontconjuguessilexistex, y telsqueu= xyetv=yx. Enumerertouslesconjuguesdumotabbaa.Montrerquelarelationetreconjugue estunerelationdequivalencesur. Demontrerquesiwestprimitif,alorssesconjugueslesontaussi.ExerciceI.4.19. Soitlalphabet , , , o` uchaque`echerepresenteun deplacement dune unite dans le plan muni dun rep`ere orthonorme. Car-acteriserlensembledesmotscorrespondant` aundeplacementdupointdecoordonnees (0, 0) aupoint de coordonnees (1, 1). Meme question, maiscettefois,onserestreintaudeplacementsdanslepremierquadrant(onnepeut setrouver enunpoint dont unedes coordonnees serait strictementnegative).4.2. Expressionsreguli`eres.ExerciceI.4.20. Donneruneexpressionreguli`eredulangageformedesmotsdelongueuraumoins2sur a, bpourlesquelstouslesaeventuelle-mentpresents prec`edentlesb(eventuellementpresents).ExerciceI.4.21. Meme question que la precedente, mais cette fois, le motvideappartientaulangage.ExerciceI.4.22. Donneruneexpressionreguli`eredulangageformedesmotssur a, bquinecontiennentpaslefacteurba.ExerciceI.4.23. Donneruneexpressionreguli`eredulangageformedesmots sur a, bqui contiennent simultanement lefacteur aa etle facteur bb.ExerciceI.4.24. Donneruneexpressionreguli`eredulangageformedesmotssur a, bquicontiennentlefacteuraaoulefacteurbb, maispascesdeuxfacteurssimultanement.ExerciceI.4.25. Donneruneexpressionreguli`eredulangageformedesmots sur a, b qui contiennent exactement deux fois le facteur aa. (Sugges-tion: attentionaufacteuraaa).I.4.Exercices 25ExerciceI.4.26. Donneruneexpressionreguli`eredulangageformedesmotssur a, b, cquinecontiennentpasdeuxaconsecutifs.ExerciceI.4.27. Donneruneexpressionreguli`eredulangageformedesmotssur a, bquicontiennentlefacteuraaexactementunefois.ExerciceI.4.28. Donneruneexpressionreguli`eredulangageformedesmotssur a, b, cqui debutentpara, contiennentexactementdeuxbetseterminentparcc.ExerciceI.4.29. Donneruneexpressionreguli`eredulangageformedesmotssur a, b, cquicontiennentunnombredeadivisiblepar3.ExerciceI.4.30. Donneruneexpressionreguli`eredulangageformedesmotssur a, bdelongueurimpaireetquicontiennentlefacteurbb.ExerciceI.4.31. Donneruneexpressionreguli`eredulangageformedesmotssur a, bayantauplustroisa.ExerciceI.4.32. Donneruneexpressionreguli`eredulangageformedesmots sur a, b, cqui contiennent un nombre impair doccurences du facteurab.ExerciceI.4.33. Donneruneexpressionreguli`eredulangageformedesrepresentationsenbase3desnombres pairs.ExerciceI.4.34. Donneruneexpressionreguli`eredulangageformedesrepresentationsenbase10desnombresmultiplesde5.ExerciceI.4.35. Soit un alphabet. Dans les expressions reguli`eres don-neesci-dessous, onsautorise` autiliserlexpression+(avec )quiesttelleque L(+) = (L())+= i>0(L())i. Demontrerque(ba)+(ab +a) = (ba)b a+(b +e),b+(ab +e)b = b(ba +e)b+,(a +b)= (a +b)b,(a +b)= (a +ba),(a +b)= (b(a +e)b).ExerciceI.4.36. Soit = a, b. Verierque(ab)+= (a b) (aa + bb).4.3. Langagesregulierssurunalphabetunaire.ExerciceI.4.37. Exprimer [L()[commeuneunionniedeprogressionsarithmetiqueslorsque = (ab) +bbb, = (a(ba) +a), = (ab)(ac(a +b)), = ab(bbc).26 ChapitreI.MotsetlangagesExerciceI.4.38. Construireuneexpressionreguli`eretelleque [L()[ = 5 +N.3, [L()[ = N.7 (4 +N.5).ExerciceI.4.39. Lelangage an3+2n+1[ n N est-ilregulier ?Justier.ExerciceI.4.40. Lelangage a2n+1[ n Nest-ilregulier?Justier.ExerciceI.4.41. Lelangage an[ n To` u Tdesignelensembledesnombrespremiersest-ilregulier?Justier.RemarqueI.4.42. Leresultatobtenu` alexerciceprecedentnestenrienincompatibleaveclecel`ebretheor`emedeDirichletquistipulequesiaetbsontpremiersentreeux(i.e., pgcd(a, b)=1), alorslaprogressionarithme-tiquea +N.bcontientuneinnitedenombrespremiers.CHAPITREIIAutomatesNous avons vu au premier chapitre que les expressions reguli`eres permet-tentdegenerercequelonadecidedappeler les langages reguliers. Lesautomates quenous allons introduireici sont desmachinespermettantdereconnatreexactementceslangages. Endautrestermes,lensembledeslangages acceptesparautomateni concideaveclensembledeslangagesreguliers.1. AutomatesnisdeterministesDenitionII.1.1. Unautomatenideterministe(ouAFD)estladonneedunquintuple/ = (Q, q0, F, , )o` uQestunensemblenidontles elementssontles etatsde /,q0 Qestun etatprivilegieappeleetatinitial,F Qdesignelensembledes etatsnals,estlalphabetdelautomate,: Q Qestlafonctiondetransitionde /.Noussupposeronsqueestunefonctiontotale, i.e., queestdeni pourtoutcouple(q, ) Q(onparlealorsdAFDcomplet).NousrepresentonsunAFD /delamani`eresuivante. Lesetatsde /sontlessommetsdungrapheorienteetsontrepresentespardescercles. Si(q, ) = q

,q, q

Q, ,alorsontraceunarcorientedeqvers q

etdelabelq q

.Lesetats nals sont reperes gr ace ` aundoublecercle et letat initial estdesigne par une `eche entrante sans label. Enn, si deux lettres et

sonttellesque(q, ) = q

et(q,

) = q

,onsautorise` adessiner ununique arcportantdeuxlabelsseparesparunevirgule,q,

q

.Cetteconventionsadapteaisement` aplusdedeuxlettres.2728 ChapitreII.AutomatesExempleII.1.2. Lautomate / = (Q, q0, F, , )o` uQ = 1, 2, 3,q0= 1,F= 1, 2, = a, beto` ulafonctiondetransitionestdonneepar a b1 1 22 1 33 3 2estrepresente` alagureII.1.1ab2ab3abFigureII.1. UnAFD.DenitionII.1.3. Soit /=(Q, q0, F, , )unAFD. Onetendnaturelle-mentlafonctiondetransition` aQdelamani`eresuivante:(q, ) = qet(q, w) = ((q, ), w), , w .Lelangageacceptepar /estalorsL(/) = w [ (q0, w) F.Siw L(/), onditencoreque /acceptelemotw(ouquewestacceptepar /).Ainsi, ler olefondamental dunautomateest daccepter ouderejeterdes mots. Unautomate partitionne lensemble des mots sur endeuxsous-ensemblesL(/) et L(/).ExempleII.1.4. Sionpoursuitlexempleprecedent,lautomate /delagure II.1 accepte le mot abbab car on a, partant de letat initial, le parcourssuivantauseinde /:1a1b2b3a 3b2 F.Parcontre,bbanestpasacceptepar /car1b2b3a 3 , F.ExempleII.1.5. Lautomate /represente` alagureII.2accepteexac-tement le langage forme des mots sur lalphabet a, b et contenant un nom-breimpairdea.L(/) = w a, b: [w[a 1 (mod2).II.2.Automatesnondeterministes 291ba2baFigureII.2. Unautomatenideterministe.RemarqueII.1.6. Poursimplierlesnotations,onsautorise` a ecrireq.waulieude(q, w)siaucuneconfusionnestpossible.Denition II.1.7. A tout mot w de correspond une unique suite detatsde /correspondant au chemin parcouru lors de la lecture de w dans /. Cettesuite sappelle lexecution1de wsur /. Ainsi, si w = w0 wk, avec wi ,alorslexecutiondewsur /est(q0,q0.w0,q0.w0w1, . . . ,q0.w0 wk1,q0.w0 wk).RemarqueII.1.8. Onauraitpuaussi introduiredesautomates innisen nimposant pas la restriction ` a lensemble detats Q detre ni (mais noussupposerons quand meme que lalphabet reste ni). Les notions dexecutionoudelangage acceptesetransposent sans peine` acecadreplus general.(Nousverronsunpeuplusloinquelanotiondautomate minimal nespe-cieaprioririensurlecaract`erenidelensembledetats.)2. AutomatesnondeterministesLemod`eledautomateninondeterministegeneraliselecasdesAFD.Comme nous le verrons bient ot, le non-determinisme permet une plus grandesouplessebienutiledanscertainessituations.DenitionII.2.1. Un automateninondeterministe (AFND) est la don-needunquintuple/ = (Q, I, F, , )o` uQestunensemblenidontles elementssontles etatsde /,I Qestlensembledes etatsinitiaux,F Qdesignelensembledes etatsnals,estlalphabetdelautomate, QQestunerelationdetransition(quonsupposeranie).On peut d`es ` a present noter plusieurs dierences entre les AFD et AFND.Dans lecasnondeterministe,ilestpossible davoir plus dun etatintial;leslabelsdesarcsnesontplusnecessairementdeslettresmaisbiendesmots1Laterminologieanglo-saxonneconsacrelemot run.30 ChapitreII.Automatesdeetenn,onnaplusunefonctiondetransitionmaisunerelationdetransition. Pour representer les AFND, nous utilisons les memes conventionsquepourlesAFD.ExempleII.2.2. LautomatedelagureII.3estunAFNDayant1et31a2a3baba bFigureII.3. UnAFND.comme etatsinitiaux,2comme etatnaletlarelationdetransitionest = (1, a, 1), (1, a, 3), (1, ba, 2), (2, a, 1), (2, b, 3), (3, b, 2)DenitionII.2.3. Unmotw=w1 wkestaccepteparunAFND /=(Q, I, F, , )silexisteq0 I, N 0, v1, . . . , v

,q1, . . . , q

Qtelsque(q0, v1, q1), (q1, v2, q2), . . . , (q1, v

, q

) ,w = v1 v

et q

F.Endautrestermes, cetteconditionsigniequil existeunchemindanslegraphe associe` a / debutant dans un etatinitial,de labelwet se terminantdansunetatnal. Naturellement, lelangageaccepteparunAFND /estlensembledesmotsacceptes par /etsenoteencoreL(/). Enn, deuxAFND /et Bsontdits equivalentssiL(/) = L(B).ExempleII.2.4. Si nouspoursuivonslexempleII.2.2, lemotabestac-ceptecar1 I, (1, a, 3) , (3, b, 2) et2 F. Ceci senoteschema-tiquement,1a3b2.Aunmot,ilpeutcorrespondreplusdunchemin. Parexemple,aumotbaa,ilcorrespondleschemins3b2a1a 1,3b2a1a3et1ba2a1.Cesontles trois seulespossibilites partantdunetat initial. Lemot baanestdoncpasaccepteparlautomate.II.2.Automatesnondeterministes 31RemarqueII.2.5. DansladenitiondunAFND,riennempeche davoirdestransitions vides dutype(q, , q

) .Onparleparfoisde-transitions. Enparticulier,onsupposeimplicitementquepourtout etatqdunAFND,ona(q, , q) .ExempleII.2.6. ConsideronslAFNDsuivant. Cetautomateacceptele1a2b3aFigureII.4. UnAFNDavec-transitions.motacaronalechemin1a21 F.Observons encore quil nest pas possible depuis letat initial de lire des motsdebutant par b. Donc, contrairement ` a la situation deterministe o` u, ` a chaquemot correspondait exactement une execution, ici, on peut avoir pour un motdonneplusdunchemindanslegraphe,voirememeaucun.Denition II.2.7. Un AFND / = (Q, I, F, , ) est qualie delementairesipourtout(q, w, q

) ,[w[ 1.Commelemontrelelemmesuivant, onpeutdanslecadredesAFNDserestreindreaucas dautomateselementaires. Eneet, tout AFNDestequivalent` aunAFND elementaire.Lemme II.2.8. Tout langageacceptepar unAFNDest acceptepar unAFNDelementaire.Demonstration. Soit / = (Q, I, F, , ) un AFND. Sil nest pas elemen-taire, ilexisteaumoinsunmotw= w1 wk(k 2,wi )etdesetatsq, q

telsque(q, w, q

) .Considerons de nouveaux etats q1, . . . , qk1nappartenant pas Q. Il est clairquelautomate B = (Q

, I, F, ,

)o` uQ

= Q q1, . . . , qk1et

=_ (q, w, q

)___(q, w1, q1), (q1, w2, q2), . . . , (qk2, wk1, qk1), (qk1, wk, q

)_32 ChapitreII.Automatesest tel que L(/) = L(B). En repetant cette procedure pour chaque transition(q, w, q

) telleque [w[> 1, onobtient(enunnombrenidetapes)unautomateelementaireacceptantlememelangage.

ExempleII.2.9. Appliquonslamethodedeconstructiondonneedanslapreuvedulemmeprecedent` aunexemple. SoitlAFNDnon elementaire /represente` alagureII.5.1 2b3ababaaaFigureII.5. UnAFNDnon elementaire /.Onobtientalorsunautomateelementaireequivalent` a /represente` alagureII.6,les etatssupplementaires neportantpasdenumero.1aab aabb3 2aFigureII.6. UnAFND elementaire equivalent` a /.Remarque II.2.10. Soit /=(Q, I, F, , ) unAFND. Si RQetw ,onnote Ilsagitduneextensiondelanotationq.wintroduite` alaremarqueII.1.6R.wlensemble des etats atteints ` a partir des etats de R en lisant w. Par exemple,aveclautomatedelagureII.4, 1.a = 1, 2car1a2 et 1a21.Onaaussipourcetautomate, 1.b = .Danslecasparticulierdew = ,onatoujoursR. R.II.2.Automatesnondeterministes 33Eneet, onsupposeimplicitementquepourtoutetatq, (q, , q) (cf.remarque II.2.5). Autrement dit, R. est lensemble des etats atteints depuisles etatsdeRsansliredelettres.SiLestunlangagesur,onposeR.L =_wLR.w.Le resultat suivant stipule que tout AFND est equivalent ` a un AFD. Endautres termes,lorsquon sinteresse ` alacceptationdes motsdun langage,unAFNDnestpas pluspuissant quunAFD.Proposition II.2.11 (Rabin et Scott2).Tout langage accepte par un AFNDestaccepteparunAFD.Demonstration. Vule lemme II.2.8, onpeut supposer disposer dunAFNDelementaire /=(Q, I, F, , ). Consideronslautomatenideter-ministeB = (2Q, Q0, F, , )ayantcommeensembledetats,lensembledesparties3deQettelqueletat initial Q0estegal ` aI., i.e., ` alensembledesetats de /atteints` apartirdes etatsinitiauxsansconsommerdelettres;lensembledes etatsnalsestF = G Q [ G F ,= ,i.e., lesetatsnalsde BsontlespartiesdeQcontenantaumoinsun etatnal;si G Qestunetatde Betwunmotnonvidesur, alorsondenitlafonctiondetransitionde Bpar(G, w) = G.w.Deplus,onpose(G, ) = G. G.wdesignelensembledesetatsatteints` apartirdesetatsdeGenlisantw.Tout dabord, pour verier quil sagit bien dun AFD, il sut de montrerqueestbienunefonctiondetransition,i.e.,quepourtousu, v ,(G, uv) = ((G, u), v).Siaumoinsundesdeuxmotsuouvestnul,laconclusionestimmediate.Sinon,nousdevonsmontrerqueG.uv= (G.u).v.Il estclairquelemembrededroiteestinclusdanslemembredegauche.Lautre inclusionresulte dufait que lautomate est elementaire. Enef-fet, cette proprieteest indispensable. Enguise dillustration, lautomaterepresente` alagureII.7nestpaselementaireet 1.ab= 3, 4, 1.a=2M. O. Rabin, D. Scott, Finiteautomataandtheir decisionproblems, IBMJ. ofResearchandDevelopment3(1959),114125.3Bestnicar#2Q= 2#Qet Aestni.34 ChapitreII.Automates1 2b3a4abFigureII.7. Unautomatenon elementaire.2et(1.a).b = 2.b = 3donc1.ab , (1.a).b.PourunAFNDelementaire, lesarcsayantdeslabelsdelongueurauplusun,unetellesituationnepeutseproduire.Il nous reste ` a montrer que L(/) =L(B). Onproc`ede par doubleinclusion. Soit wappartenant ` aL(/). Celasigniequil existe dans /unchemindelabelwdebutantdansun etatinitialdeI(etmemedansunetatde I.)etaboutissantdans un etatnal deF. Endautres termes,pardenitiondeQ0,Q0.w F ,= et(Q0, w)appartientdonc` aF.Soit wappartenant ` a L(B). Dans B, le chemin de label w debutant dansQ0aboutitdansun etatnaldeF,i.e.,(Q0, w) F.Donc(I.).w F ,= cequisigniequewestacceptepar /.

Remarque II.2.12. La demonstration precedente nous fournit une metho-de(unalgorithme)permettantderechercherunautomatedeterministeac-ceptant exactement le meme langagequun AFND donne. On parle souventdelaconstructionpar sous-ensembles (enanglais, subset construction).Commenousallonslemontrersurdesexemples,ilestinutiledeconsiderertouteslespartiesdeQ. Seulslesetatsquipeuvent etreatteintsdepuisQ0meritentdetreconsideres.ExempleII.2.13. SoitlAFNDrepresente` alagureII.8. Onremarquequil est elementaire. Sil ne letait pas, il faudrait tout dabordle ren-dreelementaire. Onconstruitletableausuivantdeprocheenproche, enlinitialisantavecI.quiestici1. = 1.Achaqueetape, pour unsous-ensembleXdetats nonencore traite, ondeterminelesvaleursdeX.pourtout . LaconstructionsetermineII.2.Automatesnondeterministes 351aaa2b3cFigureII.8. Unautomateninondeterministe.unefois que tous les sous-ensembles detats apparaissant ontete pris encompte.X X.a X.b X.c1 1, 2, 3 1, 2, 3 1, 2, 3 2 2, 3 2 2 2, 3 2 2, 3La construction dun tel tableau peut etre facilitee en etablissant au prealablelatabledetransitiondelautomate. Ici,pour /,cettetableestq q.a q.b q.c1 1, 2, 32 23 2 2, 3SionposeA = 1,B= 1, 2, 3,C= ,D = 2etE= 2, 3,alorsonalautomaterepresente` alagureII.9. Bienevidemment, lesetatsnalsdeaabbcb,cB AC DEba,b,ca,cacFigureII.9. AFD equivalent` alAFNDdelagureII.8.36 ChapitreII.Automatescetautomatesont les sous-ensembles detatsde / qui contiennent 2 (leseuletatnalde /).Exemple II.2.14. Considerons un AFND (elementaire) acceptant, commeil est facile de le verier, le langage a(ba)a. Cet automate est represente` alagureII.10. Ici, 1.= 1, 2, 4. Ainsi, laconstructiondutableau12a3b4aFigureII.10. unANFDacceptanta(ba) a.donneX X.a X.bA = 1, 2, 4 3, 4 B= 3, 4 4 2C= D = 4 4 E= 2 3 F= 3 2etontrouvelautomatedelagureII.11.Remarque II.2.15.Il est clair que tout AFD est un cas particulier dAFND.Par consequent, tout langage accepte par un AFD / est trivialement accepteparunAFND(` asavoir /lui-meme). DelapropositionII.2.11, nouscon-cluonsdoncqueleslangagesacceptesparlesAFDetlesAFNDconcident.Nous pourronsd`es lors, par lasuite, parler dunlangage acceptepar unautomateni(sansautreprecision).2.1. Apropos de lexplosion exponentielle. Le nombre detatspeut crotre de mani`ere exponentielle lorsquon rend deterministe un AFND.Danscertainessituations, cetteexplosiondunombredetatsestinevitableetce,memedanslecasdunalphabetunaire.DenitionII.2.16. OndenitunAFND /ksurunalphabetunaire acommesuit. Cetautomateposs`edeununiqueetatinitial ` apartirduquelonpeutsedeplacerdanskbouclesdisjointes. Pouri=1, . . . , k, lai-i`emeII.2.Automatesnondeterministes 37aba,baa babbabA B DC EFFigureII.11. unAFDacceptanta(ba) a.boucle est un cycle de longueur pio` u pirepresente le i-`eme nombre premier.Lesetatsnalssontletatinitial etunetatparcycle, demani`eretellequelelangageacceptepar /ksoitL(/k) = an[ n N.p1 N.p2 . . . N.pk =: Lk.Unexemple,danslecask = 3,estrepresente` alagureII.12.aaaaaaaaa aaaaFigureII.12. Lautomate /3.Proposition II.2.17. Le langage Lkaccepte par lAFND /kpossedant1 + p1 + p2 ++ pketatsestaccepteparunAFDayant N=p1p2 pketatsetaucunAFDayantmoinsdeNetatsnacceptecelangage.Demonstration. Toutdabord, unAFDcomposedununiquecycledelongueurNconvient. Eneet, si onnumerotelesetats decet automate0, . . . , N 1, alorsletatinitial est0etlesetatsnalscorrespondentauxindicesipourlesquelsilexistej 1, . . . , ktelquei 0 (modpj).38 ChapitreII.AutomatesIlestclairquuntelAFDaccepteexactementLk. Parexemple,danslecaso` uk=3, onalAFDrepresente` alagureII.13. Danscetautomate, estnaltout etatdontlindiceestmultiplede2,3ou5.71311117192923FigureII.13. UnAFDacceptantL3.Apresent, supposons que Best unAFDacceptant Lket poss`edantmoinsdeNetats. Puisquelalphabet est unaire, cet automateest delaformesuivante:FigureII.14. UnAFDsurunalphabetunaire.Onparleparfoisdemani`ereimagee, dautomate poele` afrire (fryingpanautomaton). Lecycleestdelongueur 1etlecheminmenantaucycleest delongueur c 0. Par hypoth`ese, ona 1,cest-` a-dire, silyaplusdunetatnal, onajouteunnouveletatf

etonpose(q, f

)=epourtoutq F. Ensuite,onredenit f

commenouvelensembledetatsnals.Ainsi, ` alandeletape1, onpeutsupposerdisposerdunAFEequi-valent /

= (Q

, q

0, f

, ,

) possedant un unique etatinitial q

0(non naletauquelnaboutitaucunetransition)etununique etatnalf

.(2) Fin ?Si Q

= q

0, f

, alors une expression reguli`ere du langage acceptepar /

estrq

0f (rf

f )o` urq

0f =

(q

0, f

)etrf

f =

(f

, f

). Lalgorithmesach`eve. Sinon, onpasse` aletape3.(3)Eliminationdunetat. Il existeq Q

q

0, f

. Onelimineqde/

parlamethodedupivotpresenteeci-dessus. Apr`espivotage,lensembledetatsestQ q. Onrecommencelepoint2. Achaque etape,lenombredetatsdecrotstrictement. Parconsequent,lalgorithmesach`evetoujours.2IlsagitdelalgorithmedeMcNaughton-Yamada.3Onnetientpascompteducastrivial(q0, q0) = e. Parcontre,siilexister = etelque(q0, q0) = r,alorsoneectuelamodicationdelautomate.III.3.Stabilitedelaregularite 57ExempleIII.2.7. Poursuivons lexempleIII.2.6. Sioneliminelesommet3delAFErepresente` alagureIII.15,ilvient

(1, 1) = r11 +r13r33r31= e + (ab +aba) e 0 = e

(1, 4) = r14 +r13r33r34= abb + (ab +aba) e b

(4, 1) = r41 +r43r33r31= 0 + (bbb) e 0 = 0

(4, 4) = r44 +r43r33r34= bbb + (bba) e b.Onobtientlautomaterepresente` alagureIII.16. Finalementuneexpres-1*4*abb+(ab+aba)eb *bbb+(bba)eb *FigureIII.16. AFE equivalentapr`es eliminationdeletat3.sionreguli`eredulangageaccepteparlautomatededepartest(abb + (ab +aba) e b)(bbb + (bba) e b).Puisqu` a toute expression reguli`ere , correspond un automate acceptantle langage L()et qu` a tout langageL acceptepar un automatecorrespondune expression reguli`ere telle que L = L(), nous avons le resultat suivant.Theor`emeIII.2.8(Kleene). Unlangageestreguliersietseulementsiilestaccepteparunautomateni.

RemarqueIII.2.9. Dunecertainemani`ere, onpeutdirequelesexpres-sions reguli`eres sont les generateurs des langages reguliers, alors que lesautomatesnisensontlesaccepteurs.3. StabilitedelaregulariteTheor`eme III.3.1. Lensemble des langages reguliers est stable par union,concatenation, etoiledeKleene, imageparmorphisme, miroir, passageaucomplementaire,intersectionetshue.Demonstration. Celaresulteimmediatementdesresultatsdemontresauchapitre II concernant les langages acceptes par automate ni et du theor`emedeKleene.

Le resultat suivant est souvent utilise pour verier que certains langagesnesontpasreguliers. IlsagitsimplementdunerediteducorollaireI.3.10.Corollaire III.3.2. Si L est un langage regulier sur = 1, . . . , n, alors[L[ = [w[ : w L Nestuneunionniedeprogressionsarithmetiques.58 ChapitreIII.LangagesreguliersetautomatesDemonstration. Soit = unalphabetunaire. Lapplicationf: : i , i 1, . . . , nestunmorphisme de monodespreservant leslongueurs, i.e.,pour toutmotw , [f(w)[ = [w[. Parconsequent,[f(L)[ = [L[.Puisque Lestregulier,parletheor`emeIII.3.1,f(L)estunlangagereguliersurunalphabetunaire. AuvudelapropositionI.3.9, [f(L)[estuneunionniedeprogressionsarithmetiques.

4. Crit`eredenon-regulariteLemmeIII.4.1(Lemme de la pompe).4Soit L un langage regulier.Il existeunentiertel quepourtout mot wdeLsatisfaisant [w[ , ilexistex, y, z telsquew = xyzet [xy[ ,y ,= ,xyz L.Demonstration. PuisqueLestregulier, il estaccepteparunAFD /=(Q, q0, F, , )possedantetats. Unmotw= w1 wn Ldelongueurncorrespond` auneexecutionpassantparn + 1 etatsq0, q1, . . . , qn,q0w1q1w2q2 qn1wnqn F.Puisque /poss`ede etats, si n , alors aumoins deuxetats dans lasuite detatssont egaux. Soient qietqjdeux tels etats(onsuppose que lonconsid`erelapremi`ererepetitiondedeuxetats, i.e., qi=qj, 0 i 0(cark2 k). Parconsequent,toutmotdelongueurk2+ni, n Nest acceptepar /. Or, lensembledes carres parfaits necontient aucuneprogressionarithmetiqueinnie. OnentirequelelangageLnepeutetreregulier.RemarqueIII.4.3. Attironslattentiondulecteursur lefaitquedeslan-gages non reguliers peuvent neanmoins satisfaire la condition du lemme de lapompe. Eneet,soitL bunlangagenonregulierarbitraire. Lelangagea+L bsatisfaitlelemmedelapompe. Il sutdeprendreaveclesnotationsdulemme, = 1.Laversionsuivantedulemmedelapompefournituneconditionneces-saireetsusantepourquunlangagesoitregulier.Lemme III.4.4 (Lemme de la pompe, version forte).5Un langage L est reguliersi et seulement si il existeuneconstantek>0tellequepourtout mot w , si [w[ k, alorsil existex, y, z telsquew=xyz,y ,= etpourtouti 0etpourtoutv ,wv L xyizv L.Demonstration. Laconditionestnecessaire. SupposonsquelelangageLestaccepteparunAFD / = (Q, q0, F, , )possedantketats. Toutmotw = w1 w

delongueur kfournituneexecutiondelaformeq0w1q1w2w

q

o` u q0est letat initial. Par un raisonnement analogue ` a celui developpe dansla preuve precedente, il existe 0 i < j tels que qi= qjet lautomate /5Ce resultat est d u ` a J. Jae (SIGACT News, 1978). Nous avons repris ici une preuveextraitedeS.Yu,RegularLanguages, Handbookofformallanguages,Springer,1997.60 ChapitreIII.Langagesreguliersetautomatesa donc une boucle. On pose x = w1 wi, y = wi+1 wjet z= wj+1 w

(sii = 0,x = etsij= ,z= ). D`eslors,pourtouti 0,(q0, xyiz) = q

etainsi,pourtouti 0,(q0, xyizv) = (q0, xyzv) = (q0, wv)cequisigniequewv L xyizv L.Passons` alareciproqueetsupposonsquil existeuneconstantek>0telle que le langage L satisfasse les proprietes enoncees. Nous devons montrerque L est regulier. Pour ce faire, nous allons construire un AFD / et verierqueL=L(/). Soit /=(Q, q0, F, , )o` uchaqueetatdeQcorrespond` aunmotw delongueurstrictementinferieure` ak,i.e.,Q = qw [ w et [w[ < k.Letatinitialde /estqetF= qw [ w L. Lafonctiondetransitionestdenieparsi [w[ < k 1,alorspourtout ,(qw, ) = qwsi [w[ = k1, alors pour tout , w est un mot de longueur k etparhypoth`ese, ilpeut sedecomposerenxyzavecynonvide ettelque pour tout v ,xyzv L si etseulement si xzv L. Il peutyavoirplusdunetelledecomposition(maisil yenatoujoursaumoins une). Sil y a plus dune decomposition,on choisit celle pourlaquelle xy est le plus court (et si une ambigute subsiste encore, onchoisitparmi lesdecompositionsayantxydelongueurminimum,celleo` uyestlepluscourt). Onpose(qw, ) = qxz.(Onremarqueque [xz[ < kpuisqueyestnonvide.)Il nousreste` amontrerqueL(/)=L. Onproc`edeparrecurrencesurlalongueur dun mot w . Par denition de lautomate /, il est clair quunmotwde longueur strictement inferieure ` akappartient ` aLsi etseulementsiilappartient` aL(/). Soitn k. Supposonslaproprietesatisfaitepourlesmotsdelongueurinferieure` anetverions-lapourlesmotswtelsque[w[ = n. D`eslors,ilexistew0etvtelsquew = w0v, avec [w0[ = k.Pardenitionde /,ilexistex, z telsque(q0, w0) = (q0, xz) = qxz, avec w0= xyz,y ,= III.5.Exercices 61etenparticulier,w0v= wappartient` aLsietseulementsixzvappartient` aL. Deplus,ona(q0, w0v) = (q0, xzv) = (qxz, v),cequi signiequew0v = wappartient ` aL(/)sietseulement sixzvappar-tient` aL(/)(eneet, onatteintlememeetatde /). Or [xzv[< n(carynon vide) et donc, par hypoth`ese de recurrence, xzvappartient ` a L(/) si etseulementsiilappartient` aL. Enconclusion,w L(/) w L.

Remarque III.4.5.Nous voulons faire observer au lecteur que cette derni`erepropositionnecessiteunedecompositiondewenxyzquidoitpouvoiretreappliqueepourtoutmotwv,v .5. Exercices5.1. Langagesreguliers.ExerciceIII.5.1. SoitlelangageL = ab2a3b4 a2n1b2n[ n N.Celangageest-ilregulier?Justier.ExerciceIII.5.2. Lelangage anbn[ n Nest-ilregulier?ExerciceIII.5.3. Lelangage anb2n[ n Nest-ilregulier?ExerciceIII.5.4. Lelangage w a, b: [w[a< [w[best-ilregulier?ExerciceIII.5.5. Lelangage a2n[ n Nest-ilregulier?ExerciceIII.5.6. Soitlemorphismef: a, b a, btelquef(a) = b et f(b) = a.LelangageL = wf(w) [ w a, best-ilregulier?Exercice III.5.7. Soit /un AFD possedant k etats, k 1. Demontrer quesilelangageacceptepar /necontientaucunmotdelongueurstrictementinferieure` ak,alorslelangageacceptepar /estvide.ExerciceIII.5.8. Soit /unAFDpossedantketats, k 1. Demontrerque si le langageacceptepar / est ni, alors tout mot acceptewest telque[w[ < k.ExerciceIII.5.9. Soit un alphabet de tailleau moins 2. Le langagedespalindromessurest-il regulier? Quesepasse-t-il danslecasparticulierdunalphabetunaire?ExerciceIII.5.10. Lelangage anbman+m[ m, n Nest-ilregulier?62 ChapitreIII.LangagesreguliersetautomatesExerciceIII.5.11. Lelangageformedesmotssur a, bquicontiennentdeuxfoisplusdeaquedeb,i.e.,L = w a, b: [w[a= 2[w[b,est-ilregulier?Quevaut(L)?ExerciceIII.5.12. Soientlesalphabets= a, b, cet= e, fetunlangageLsur. Ondonnelemorphismeh : telqueh(a) = h(b) = e et h(c) = f.Si h(L) est un langage regulier, peut-on en deduire que L est lui-memeregulier,justier?5.2. Langageaccepteparunautomate.Exercice III.5.13. Determiner une expression reguli`ere du langage accepteparlautomatereprisengureIII.18.ba,babba aFigureIII.18. Expressionreguli`eredulangageaccepte.Exercice III.5.14. Memequestionquelexerciceprecedentpour lAFDrepresente ` a la gure III.19. Si les mots acceptessont consideres comme des10,10 101001FigureIII.19. Expressionreguli`eredulangageaccepte.representationsenbase2dentiers,endeduirelesproprietesarithmetiquesdelensembledentiersaccepte.CHAPITREIVAutomateminimal1. IntroductionNoussavons ` apresent quun langageestreguliersi etseulement si ilestaccepteparunautomateni(etenparticulier, deterministe). Cependant,plusieursAFDpeuvent accepter lememelangage. Laquestionposeeiciestderechercherparmidesautomatesequivalents,unautomatequiserait,selonunsensencore` adenir,canonique. Parexemple,lesautomatessuiv-antsacceptenttouslelangageformedesmotsnecomprenantpasdeuxaconsecutifs.a abbabbaa,babbba aa,ba,ba abbbaFigureIV.1. TroisAFD equivalents.Il paratnaturel devouloirminimiserlenombredetatsdunAFDac-ceptantunlangageregulierdonne. Eneet, lorsdeconstructionscommeleproduitdautomates, il estpreferabledavoirpeudetats` atraiterpourdiminuerlatailledelautomateresultant. Nous allons montrer qu` aiso-morphismepr`es, il nexiste quunseul AFDacceptant unlangage donneet possedant unnombreminimumdetats. Notons encore que lanotiondautomateminimal peutetredeniepour unlangagequelconqueet pasuniquement pourunlangageregulier.6364 ChapitreIV.Automateminimal2. CongruencesyntaxiqueDenitionIV.2.1. SoitL unlangagearbitraire. Si westunmotsur, ondenoteparw1.Llensembledesmotsqui, concatenes avecw,appartiennent` aL,i.e.,w1.L = u [ wu L.On denit une relationsur ,notee L, de lamani`ere suivante. Pour tousx, y ,x Ly x1.L = y1.L.Endautres termes, x Ly si et seulement si pour tout mot w,xw L yw L.Notonsquelanotationlaplusrepandue danslalitteratureestw1L.RemarqueIV.2.2. Avecune telledenition, la formule suivante est alorsimmediate(o` ulasommerepresentelunion),L =

(1.L) +(L), avec(L) =_ ,si L ,sinon.et J. H. Conway decrireboth Taylors theorem and the mean value theorem.PropositionIV.2.3. Soit L unlangage. Larelation Lest unerelationdequivalence. Il sagitmemedunecongruence1` adroite,i.e.,z , x Ly xz Lyz.Demonstration. Cestimmediat.

Remarque IV.2.4. On parle souvent pour L de la congruence de Nerode.Onnote[w]Llaclassedequivalencedumotwpourlarelation L,[w]L= u [ u Lw.ExempleIV.2.5. SoitlelangageL = w a, b: [w[a 0 (mod3).Pourcelangage,onaparexempleabbaba Laaa carabbaba1.L = aaa1.L = Lb ,Lab carpouru = aa, bu , Letabu Laba ,Lbab carpouru = a, abau Letbabu , La Lababaa cara1.L = ababaa1.L = w a, b: [w[a 2 (mod3).1Pour rappel, une congruence est une relation dequivalence qui preserve les operationsdelastructurealgebriqueconsideree.IV.2.Congruencesyntaxique 65Eneet,pourw a, b,si [w[a 30, alors w1.L = u a, b: [u[ 30et [w]L= u a, b: [u[ 30,si [w[a 31, alors w1.L = u a, b: [u[ 32et [w]L= u a, b: [u[ 31,si [w[a 32, alors w1.L = u a, b: [u[ 31et [w]L= u a, b: [u[ 32.Cetexemplenousmontrequengeneral,w1.L ,= [w]L.DenitionIV.2.6. Danslecasdunautomatedeterministe(niounon)/ = (Q, q0, F, , ),paranalogieaveclanotationw1.L,onutiliselanota-tionsuivante. Siq Qestunetatde /etsiG Qestunsous-ensembledetats, onnote q1.G, lensemble des mots qui sont labels des cheminsdebutantenqetaboutissantdansun etatdeG,i.e.,q1.G = w [ (q, w) G.OndenitsurQunerelationdequivalencecommesuit: sip, q Q,alorsp Aq p1.F= q1.F.RemarqueIV.2.7. Avec la notationque nous venons dintroduire, le lan-gage accepte par lautomate deterministe / = (Q, q0, F, , ) est simplementq10.F.Lemme IV.2.8. Soit /=(Q, q0, F, , ) unautomatedeterministeac-ceptant unlangage L. Si q Qet w sont tels queL(q0, w) =q,alorsq1.F= w1.L.Demonstration. Eneet,pardenition,q1.F= u [ (q, u) F.Or(q0, w) = q. Ainsi,pourtoutu q1.F,ona(q0, wu) = ((q0, w), u) = (q, u) Fetdoncwuappartient` aL(/)=L, cest-` a-dire, uappartient` aw1.Letreciproquement.wqFuq0FigureIV.2. q1.F= w1.Lsi(q0, w) = q.66 ChapitreIV.Automateminimal

LemmeIV.2.9. SoientL unlangageetu, vdeuxmotssur. Ona(uv)1.L = v1.(u1.L).Demonstration. Si wappartient ` a (uv)1.L, celasignie que uvwappar-tient` aL. Endautrestermes,vwappartient` au1.Letainsiwappartient` av1.(u1.L). Lademonstrationdelautreinclusionestidentique.

Remarque IV.2.10. Pour loperation 1.L ( etant une lettre), on trouveparfoisuneterminologierappelantlecalcul dierentiel2. Soitunelettre.OnparleparfoisdederiveetlonnoteDLpour1.L. Laraisonenestsimple,ilestclairqueD(L +M) = DL +DMetD(LM) = (DL) M+(L) DMo` u, unefoisencore, sommeetproduitrepresententrespectivementlunionetlaconcatenation.3. AutomateminimalNous allons tirer parti de la congruence de Nerode introduite ` a la sectionprecedentepourdenirunautomateparticulier, ` asavoirlautomatemini-mal dulangageL. Ladenitionpeut` apremi`erevuesemblerarticielle,mais nous allons montrer quainsi introduit, lautomate minimal jouit deproprietesfortinteressantes.DenitionIV.3.1. Ondenitlautomateminimal/L= (QL, q0,L, FL, , L)dunlangageL commesuit:QL= w1.L [ w ,q0,L= 1.L = L,FL= w1.L [ w L = q QL [ q,L(q, ) = 1.q,pourtousq QL, .Gr aceaulemmeIV.2.9, lafonctiondetransitiondelautomatesetend` aQLparL(q, w) = w1.q , q QL, w .Nous devons verier que cette denitiona unsens enmontrant que lafonctiondetransitionnedependpasdurepresentantchoisi. Ainsi, si unetat de /Lest de laforme x1.L=y1.L(x, y), alors x Ly.2cf. J.A.Brzozowski, Derivativesofregularexpressions,J.oftheAssoc. forComp.Machinery11(1964),481494.IV.3.Automateminimal 67Puisque Lestunecongruence` adroite, pourtout , x Lyetdonc(x)1.L = (y)1.L. EnappliquantlelemmeIV.2.9,ontrouvebien1.(x1.L) = 1.(y1.L).Remarque IV.3.2. Au vu de la denition de L, il est clair que lensembledes etatsde /, w1.L [ w ,estenbijectionaveclensemblequotient/L= [w]L [ w . Eneet,` achaqueclassedequivalence[w]LpourLcorrespond un etat w1.L de lautomate minimal /L et reciproquement.Cest pour cetteraisonque, danslalitterature, ontrouveegalement unedenition de lautomateminimal en termes des classes dequivalence de L.Ainsi,onauraitpudenirlautomateminimalcommesuit:QL= [w]L [ w q0,L= []LFL= [w]L [ w LL([w]L, ) = [w]L.Cettederni`ere denitionest equivalente` acelledonnee enIV.3.1carsi[w]Lcorrespond` aw1.L, alors [w]Lcorrespond` a(w)1.L=1.(w1.L).Dans lasuite, nous utiliserons principalement ladenitiondelautomateminimaldonneeenIV.3.1.Remarquonsencorequesix Ly,alorsL(q0,L, x) = L(q0,L, y)carilsutdeserappelerqueq0,L= Letd`eslors,ilvientL(q0,L, x) = x1.L = y1.L = L(q0,L, y).ExempleIV.3.3. PoursuivonslexempleIV.2.5. Il estfaciledevoirquepour le langage Lforme des mots sur a, bcontenant unnombre de amultiple de trois, la congruence de Nerode poss`ede trois classes dequivalence[]L, [a]Let [aa]L.Ditautrement,lautomateminimal /Latrois etats1.L, a1.Let aa1.L.Pourdenirlafonctiondetransition,onaL(1.L, a) = a1.(1.L) = a1.LL(1.L, b) = b1.(1.L) = b1.L = 1.L car LbL(a1.L, a) = a1.(a1.L) = aa1.LL(a1.L, b) = b1.(a1.L) = ab1.L = a1.L cara LabL(aa1.L, a) = a1.(aa1.L) = aaa1.L = 1.L car LaaaL(aa1.L, b) = b1.(aa1.L) = aab1.L = aa1.L caraa Laab.Si onnote 1, 2, 3les trois langages 1.L=L, a1.L, aa1.L, onobtientlautomaterepresente` alagureIV.3.68 ChapitreIV.Automateminimalaaabbb1 23FigureIV.3. Unautomateminimal.RemarqueIV.3.4. Onobserve que,dans ladenitionde /L,les etatsdelautomate minimal de L sont des ensembles de mots. Dans lexemple prece-dent,onaunnombrenidetatsetchaqueetatcorrespond` aunensembleinnidemots.Exemple IV.3.5.Considerons le langage L forme des mots sur a, b ayantmemenombredeaquedeb,i.e.,L = w a, b: [w[a= [w[b.Uneapplicationimmediatedulemmedelapompemontrequecelangagenest pas regulier. Onpeut neanmoins rechercher sonautomateminimalpuisquelarelation LestdeniepourtoutlangageL. Onsaper coitquelenombredeclassesdequivalencepourlarelation Lestinni. Eneet,pourtoutn Z,cn:= [aibj]L, aveci j= nestuneclassedequivalenceetilestclairquesim ,=n,alorscm ,=cn. Deplus,L((aibj)1.L, a) = (ai+1bj)1.L = (aibj1)1.LetL((aibj)1.L, b) = (aibj+1)1.L = (ai1bj)1.L.(Dans les expressions ci-dessus, onneconsid`erequeles expressions pourlesquelles les exposants sont positifs ou nuls.)Le seul etat nal de lautomateest (aibi)1.L = L. Lautomate minimal de L est represente ` a la gure IV.4.ababaab bFigureIV.4. Lautomateminimaldunlangagenonregulier.Onpeutdores-et-dej` aremarquerquepourcelangagenonregulier, lenombredetatsdelautomateminimalestinni.IV.3.Automateminimal 69PropositionIV.3.6. Lautomateminimaldun langageL accepteL.Demonstration. Eneet,soitw ,w L(/L) L(q0,L, w) FL w1.L FL w L.OnautiliselefaitqueL(q0,L, w) = L(1.L, w) = w1.(1.L) = (w)1.L.

DenitionIV.3.7. Unautomatedeterministe / = (Q, q0, F, , )estac-cessible si pour tout etat q Q, il existe un mot w tel que (q0, w) = q.Unautomatedeterministe /=(Q, q0, F, , ) est reduit si pour tousp, q Q,p1.F= q1.F entrane p = q.En dautres termes, un AFD est reduit, si les langagesacceptesdepuis deuxetatsdistinctssontdistinctsouencoresi chaqueclassedequivalencepourlarelation AsurQestunsingleton.Leresultatsuivantjustielappellation minimal.Theor`eme IV.3.8.Soient L un langage et /L= (QL, q0,L, FL, , L)sonautomateminimal. Si B = (Q, q0, F, , )estunautomateaccessibleetdeterministeacceptant L, alorsil existeuneapplication:Q QLtellequeestsurjectif,(q0) = q0,L, , q Q : ((q, )) = L((q), ),(F) = FL.a abbabaa,babbba aba,b FigureIV.5. Uneapplicationsatisfaisantlesproprietesdutheor`emeIV.3.8.70 ChapitreIV.AutomateminimalDemonstration. Puisque Bestaccessible, pourtoutetatq Q, il exis-teunmotw tel que(q0, w) =q. Supposonstout dabordquuneapplicationsatisfaisantlesproprietes enonceesexiste. Danscecas3, Oneectuedabordlanalyse.(q) = ((q0, w)) = L((q0), w) = L(q0,L, w) = w1.L = q1.Fo` upour laderni`ereegalite, onaappliquele lemme IV.2.8. Montrons ` apresentquelapplication Passons` alasynth`ese. : Q QL: q q1.Fposs`edelesproprietesindiquees:il estclairqueest` avaleursdansQLcar Betantaccessible, ilesttoujourspossibledecrireq1.Fsouslaformew1.Lpouruncertainw .Ona(q0) = q10.F= L = q0,L.Soient etq Q. Pardenitionde,onatoutdabord((q, )) = ((q, ))1.FSiw esttelque(q0, w)= q,alors(q0, w)= (q, )etparlelemmeIV.2.8,((q, ))1.F= (w)1.L.ParlelemmeIV.2.9, (w)1.L=1.(w1.L)etsionapplique` anouveaulelemmeIV.2.8,w1.L = q1.F. Parconsequent,((q, )) = 1.(q1.F) = 1.(q) = L((q), ).Montrons que est surjectif. Soit q QL. Cet etat est de la formew1.L pour un mot w . Soitrletatde Btelque (q0, w) = r.Ilvient(r) = r1.F= w1.L = q.Unetatqde Bestnal si etseulementsi il existew Ltel que(q0, w) = q. Soitquntel etat. Ainsi,(q) = q1.F= w1.L FLet (F) FL.Considerons` apresentun etatqde /Ltelqueq FL. Puisqueest surjectif, il existe un etat p Q de Btel que (p) = p1.F= q.Pardenitiondelautomateminimal,p1.Fappartient` aFLsietseulementsi p1.Fcequisigniequepestun etatnalde B.

CorollaireIV.3.9. Si Lest unlangageregulieraccepteparunAFD B,alorslenombredetatsde Bestminoreparlenombredetatsde /L.Demonstration. Cela decoule immediatement de la surjectivite de lappli-cationintroduite` alapropositionprecedente.

3En particulier,ceci prouve que si une telle application existe, alorselleest unique.IV.3.Automateminimal 71PropositionIV.3.10. SoitL unlangage.(i) Lautomateminimal /L= (QL, q0,L, FL, , L)deLestaccessibleetreduit.(ii) Soit B=(Q, q0, F, , ) unautomate deterministe accessible ac-ceptantL. Cetautomateestreduitsietseulementsilapplication : Q QLdenieautheor`emeIV.3.8estunebijection. Danscecas,lesautomates /Let Bsontisomorphes.Demonstration. Lautomate minimal est accessible car unetat quel-conquede /Lestdelaformew1.Lpourunmotw etL(q0,L, w) = w1.L.PardenitiondelensembledetatsQL,ilestclairque /Lestreduit.Si Best un automateaccessible,lapplication : Q QLintroduite autheor`eme IV.3.8 est surjective. Cette application est injective si et seulementsipourtousp, q Q,(p) = (q) p = qcequisereecritp1.F= q1.F p = qetquisignieque Bestreduit.

PropositionIV.3.11. UnlangageL estreguliersi etseulement sisonautomateminimal /Lestni.Demonstration. Si /Lest ni, auvudelapropositionIV.3.6, Lestacceptepar /LquiestenparticulierunAFD. Parletheor`emedeKleene,Lestregulier.Passons` alareciproqueetsupposonsLregulieretaccepteparunAFD/quelonpeut, sansaucunerestriction, supposeraccessible. D`eslors, auvudutheor`emeIV.3.8,lautomateminimaldeLestni.

Cedernierresultatpeutsereenoncercommesuit.Theor`eme IV.3.12 (Myhill-Nerode). Un langage L est regulier si et seule-mentsi lacongruence Lestdindiceni (i.e., poss`edeunnombreni declassesdequivalence).Demonstration. Cela resulte immediatement de la proposition precedenteetdelaremarqueIV.3.2.

72 ChapitreIV.Automateminimal4. ConstructiondelautomateminimalLapropositionIV.3.10fournitunmoyendeconstruirelautomatemi-nimaldunlangageregulierL` apartirdunAFD /acceptantL. Eneet,il sutdepouvoir trouverunAFDaccessibleetreduitequivalent. Toutdabord,ilestfacilederendreunAFDdonneaccessible. Ilsutdepasserenrevue les etatsqui peuvent etreatteintsdepuis letatinitialetdeliminerlesautresetats(inaccessibles). Classiquement, unalgorithmederechercheen profondeur sut. On construit un arbre ayant pour racine letat initial de/. Dans cetarbre, les ls dun noeudsont les etatsaccessiblesdepuis celui-ci etonarretelaconstructionlorsqu` aunniveaudelarbre, il napparatplusdenouveaux etatsparrapportauxniveauxprecedents.Laquestionquiseposeestdoncdepouvoirdeterminersiunautomatenideterministedonne /=(Q, q0, F, , )estreduit. Pardenitiondelarelation AsurQ, lautomateestreduitsi pourtoutcouple(p, q)detatsavecp ,= q,p ,Aq.Enparticulier,p ,Aqsilexisteunmotw telque(p, w) Fet(q, w) , Fou(p, w) , Fet(q, w) F.Onditalorsquuntelmotdistingueles etatspetqouencorequelecouple(p, q)estdistingue. Danslalgorithmequisuit,onnotera ^

lensembledescouplesdetatsquisontdistinguesparunmotdelongueuretquinesontdistinguesparaucunmotpluscourt.Algorithmederecherchedesetatsequivalents(1) Initialisation: lors de cette etape, ondetermine les couples detatsdistinguesparlemotvide(seulmotdelongueur = 0).Onpose := 0.Pour tout p Fet tout q QF, la paire (p, q) est distinguee car lemotvideappartient ` ap1.Fmaispas` aq1.F. Soit ^0lensembledecespaires.(2) Incrementation : on determine les couples detats distingues par un motdelongueur + 1etnondistinguesparunmotdelongueur.Si ^

= ,lalgorithmesach`eve4.4Ondoitremarquerquesi N

estvide, alorsil enestdememepour N+1etdoncaussi pourtouslessuivants. Eneet, supposonsaucontraireque N

= et N+1 = .Ilexistedonc(r, s) N+1distingueparunmotwdelongueur + 1. D`eslors, lemotwdelongueurdistinguelesetats(r, )=r

et(s, )=s

. Puisque N

= , onenconclutquer

ets

doivent etredistinguesparunmotw

delongueur< . Maisdanscecas,retssontaussidistinguesparw

delongueur ,cequiestabsurde.IV.4.Constructiondelautomateminimal 73Sinon, pourchaquepaire(p, q) ^

, onpasseenrevuelespaires(r, s)avec r ,= s qui nappartiennent pas ` a ^0 ^

. Sil existe telque(r, ) = pet(s, ) = qou(s, ) = pet(r, ) = q,alorslapaire(r, s) estdistingueeparunmotdelongueur + 1.Soit ^+1lensembledecespaires.Remplacerpar + 1etrepeter(2).ExempleIV.4.1. Appliquonslalgorithmeprecedent` alAFDrepresente` alagureIV.6.aabba bbbbaaa5 63 2 14FigureIV.6. UnAFDdontonrecherchelesetatsequiva-lentspour A.La premi`ere etapedonne le tableausuivant. Dans cetableau,on denotesimplementpari lappartenanceduncouple` alensemble ^i, i N. Deplus,parraisondesymetrie, onsinteresserauniquement` alapartiesitueeaudessusdeladiagonaleprincipale.1 2 3 4 5 61 0 02 0 0 03 04 05 06 Puisque(1.a, 3.a)=(2, 6), (1.b, 6.b)=(1, 2), (3.a, 4.a)=(6, 5)et(4, 6)=(5, 6),ona,` aladeuxi`eme etape,letableauci-dessous.1 2 3 4 5 61 0 1 0 12 0 0 03 1 04 0 15 06 74 ChapitreIV.AutomateminimalLalgorithmesach`evecar(1.a, 4.a)=(2, 5), (1.b, 4.b)=(1, 1), (2.a, 5.a)=(1, 4), (2.b, 5.b) =(3, 6), (3.a, 6.a) =(6, 6) et (3.b, 6.b) =(2, 2). Onenconclutque1 A4,2 A5et3 A6.Puisque nous pouvons supposer avoir un AFD / accessible,le theor`emeIV.3.8nousarmequelautomate /seprojetteaumoyendelapplication sur lautomate minimal du langage L accepte par / et que des etats de /equivalentspour Asontenvoyessur unmeme etatde /L. Ainsi,les etatsde /Lvontcorrespondreauxclassesdequivalencede A.Toujoursenvertudutheor`emeIV.3.8,lestransitionsdelautomatemi-nimalsontdeniesparL((q), ) = ((q, ))si (resp. L)estlafonctiondetransitionde /(resp. /L). Traduitentermesdetatsequivalents, celasigniequesi unetatde /Lcorrespond` aune classe dequivalence [q]Apour la relation A, alors la lecture de depuiscet etatdans /Lconduit` aletatcorrespondant` alaclasse[q.]A.Exemple IV.4.2. Si nous continuonslexempleprecedent, ona[1]A=1, 4, [2]A= 2, 5et[3]A= 3, 6. Puisquedanslautomatededepart,1.a=2et1.b=1, onaL((1), a) =(2)etL((1), b) =(1). Cecisignieque,dans lautomateminimal,lalecturedea(resp. b)depuis letatcorrespondant` a 1, 4conduit` a[2]A= 2, 5(resp. [1]A= 1, 4). Encontinuantdelasorte,onobtientlautomatedelagureIV.7.ba baba{2,5} {1,4} {3,6}FigureIV.7. Unautomateminimal.Exemple IV.4.3. Soit lAFDaccessible /represente ` alagure IV.8.Nous allons lui appliquer lalgorithme de recherche des etats equivalents pour1ba2ab3ba4baFigureIV.8. UnAFDaccessible /.IV.4.Constructiondelautomateminimal 75montrer quil est reduit (et quil sagit donc dun automate minimal puisquilestvisiblementaccessible). Aveclesmemesnotationsqueprecedemment,onobtientrapidementletableausuivant.1 2 3 41 0 0 12 1 03 04 4.1. Uneautreproceduredeminimisation.Proposition IV.4.4. Soit / un AFD acceptantun langageL. Si pourtoutautomate B, (B)designelautomatedeterministeequivalent` a BRobtenupar constructiondes sous-ensemblesdetats, alors ((/)) est lautomateminimal deL.Demonstration. Si BestunAFDacceptantM,ilestclairque(B)ac-cepte MRet quil est accessible. En eet, dans la procedure de constructionpar sous-ensembles, on ne consid`ere que les etats accessibles car on recherchede proche en proche les etats atteints depuis letat initial. Il sut d`es lors demontrer que si Best un AFD accessible acceptant un langage M, alors (B)estunAFDaccessibleetreduitacceptantMR. Danscecas, (/)seraunAFDaccessibleacceptantLRet((/))seraunAFDaccessibleetreduitacceptant(LR)R= L. OnconclutalorsparlapropositionIV.3.10.Soit BunAFDaccessible. Montronsque(B)estreduit. SoientP, Qdeux etats de (B). Supposons que P1.T= Q1.T(o` u Tdesigne lensembledesetatsnalsde(B)). Deparlaconstructionparsous-ensembles,letatP(resp. Q)estconstituedetats5p1, . . . , pr(resp. q1, . . . , qs)de BRetunetatestnalsilestunsous-ensemble detatsde BRcontenant un etatnalde BR(doncici contenantletatinitial q0de B, i.e., luniqueetatnal deBR).Si w appartient ` a P1.T, cela signie que, dans (B), w est le label dunchemindebutantdansPetaboutissantdansunetatnal. Encoreunfois,de par la construction par sous-ensembles, cela signie que dans BRon a unchemin de label wdebutant dans un des etats piet aboutissant dans q0. Oudemani`ere equivalente,dans B,wRestlelabeldunchemindebutantdansq0etaboutissantdanspi. Reciproquement, pourtouti 1, . . . , r, si westlabeldun chemindans Bdebutant dans q0etaboutissantdans pi,alorsdans(B),wRappartient` aP1.F. Autrementdit,onaP1.T= (q10.p1, . . . , pr)Ro` udans lemembredegauche(resp. dedroite), onconsid`erelautomate(B)(resp. B).Dans B,pourtouti 1, . . . , r, siq0.w=pi, celasigniequilappar-tient ` a q10.p1, . . . , pr et puisque nous avons supposer que P1.T= Q1.T,5Lesautomates Bet BRontlememeensembledetats.76 ChapitreIV.Automateminimalonendeduit que wappartient ` aq10.q1, . . . , qs. Ilexistej 1, . . . , stelque,dans B,q0.w = pj. Or puisque Bestdeterministe,ontrouvepi= qjetP Q. Onproc`ededememepourlautreinclusionetainsi,P= Q.

ExempleIV.4.5. Appliquons la proposition precedente pour obtenir lau-tomateminimal dulangageacceptepar lautomaterepresente` alagureIV.9. Toutdabord, lautomatemiroir /Restdonneparlautomatedela1ab2ba3ba4abFigureIV.9. UnAFD /.gureIV.10. Pourrendre /Rdeterministe, onutiliselaconstructionpar1 2bab3b4aaabFigureIV.10. Lautomate /R.sous-ensembles. Ontrouvelesensemblesdetats2, 3,1,1, 2, 3, 4, 4,.Si on renomme ces derniers 1, . . . , 5, on obtient lAFD accessible (/) repre-sente` alagureIV.11. Considerons` apresentlemiroirdecedernierauto-matepourobtenircelui delagureIV.12. Pourconclure, il nousreste` arendre cet automate deterministe en utilisant une fois encore la constructionparsous-ensembles. Lesensemblesdetatssontici,2, 3,1, 3,3, 4.Unefoiscesensemblesrenommes1, 2, 3, onobtientlautomatedelagureIV.13qui estlautomateminimal dulangageaccepteparlautomate /dedepart.IV.5.Applications 771ab2ab3a,b4a5a,bbFigureIV.11. Lautomate(/).1 2a3a,b4a5a,bbbbaFigureIV.12. Lautomate((/))R.1a,b2ba3abFigureIV.13. Lautomate((/)).5. ApplicationsNousallonsutiliserlatheoriedelautomateminimalpourmontrerquelensembledeslangages reguliersest stableparmorphismeinverse. Nousmontrons egalement que lensemble des prexes ou des suxes dun langageregulier est regulier. Enn, la racine n-i`eme(que nous denirons le momentvoulu)dunlangageregulierestencoreunlangageregulier.PropositionIV.5.1. Soit f : unmorphismedemonodes. SiM estunlangageregulieralorsf1(M)estaussiunlangageregulier.78 ChapitreIV.AutomateminimalDemonstration. Ilsutdemontrerquelautomateminimaldulangagef1(M) estni. Soitw . Onaw1.f1(M) = u [ wu f1(M)= u [ f(wu) M= u [ f(w)f(u) M= u [ f(u) f(w)1.M= f1(f(w)1.M)Or Mest regulierdonc sonautomateminimal estni etf(w)1.Mne peutprendrequunnombreni devaleurs. Onenconclut que, quel quesoitw ,w1.f1(M)nepeutprendrequunnombrenidevaleurs. Ainsi,lautomateminimaldulangagef1.Mestni.

Remarque IV.5.2. Protons duresultat precedent pour enoncer, sansdemonstration6, un resultat assez etonnant concernant la representation deslangages reguliers. PourtoutlangageregulierLsurunalphabetquelconque,il existedesmorphismesh1, h2, h3, h4telsqueL = h4(h13(h2(h11(ab)))).On pourra comparer ce resultat avec le theor`eme de representation de Chomsky-Sch utzenbergerpourleslangagesalgebriques(cf. theor`emeVI.10.3).Ceresultatnestpasnouveau! Mais lapreuveestelegante.PropositionIV.5.3. SiL estunlangageregulier,alorsPref(L)estaussiregulier.Demonstration. IlsutdemontrerquelautomateminimaldulangagePref(L)estni. Soitw . Ilvientw1.Pref(L) = u [ wu Pref(L)= u [ v : wuv L= u [ v : uv w1.L= Pref(w1.L).LelangageLetantregulier, w1.Lnepeutprendrequunnombreni devaleurs. Parconsequent, Pref(w1.L)neprendaussiquunnombrenidevaleursetlensemblePref(w1.L) [ w estni.

6Voirparexemple,leHandbookofformal languages,vol. 1,pourdesreferences.IV.5.Applications 79CorollaireIV.5.4. Si L est unlangageregulier, alorsSu(L)estaussiunlangageregulier.Demonstration. IlsutderemarquerqueSu(L) = (Pref(LR))R.Leresultatdecouledelapropositionprecedenteetdufaitquelensembledeslangagesregulierseststableparapplicationdumiroir.

RemarqueIV.5.5. OnpourracomparercesdeuxderniersresultatsaveclespropositionsII.3.9etII.3.10etleurpreuve.DenitionIV.5.6. Soitk 1. Ondenitlaracinek-i`emedunlangageL parkL = u [ uk L.ExempleIV.5.7. SoitL = ab. IlestfaciledeverierqueL = a b.Ondisposeduresultatsuivant.Proposition IV.5.8. Si L est un langage regulier, alorskL est aussiunlangageregulier.Andedemontrerceresultat,nousavonsbesoindulemmesuivant.LemmeIV.5.9. Soit L un langage regulier. Si p est un etat de lautomateminimal deLdonnedansladenitionIV.3.1alorspetS(p) = w [ p = w1.Lsontdeuxlangagesreguliers.Demonstration. Puisque pest unetat de lautomate minimal /L=(QL, q0,L, FL, , L), il existe w tel que p = w1.L. En dautres termes,p = u [ wu L = u [ L(q0,L, wu) FLcequisigniequecelangageestaccepteparlAFD(QL, L(q0,L, w), FL, , L)etdonc,celangageestregulier.PourmontrerqueS(p)estregulier, il sutunefoisencoredeverierquesonautomateminimalestni. Soitu . Ilvientu1.S(p) = v [ uv S(p)= v [ p = (uv)1.L= v [ p = v1.(u1.L).Or Lest regulier, sonautomate minimal est doncni et u1.Lne peutprendre quunnombrenidevaleursdistinctes. Parconsequent,u1.S(p) [ u 80 ChapitreIV.Automateminimalestunensembleni.

Nouspouvons` apresentdemontrerlapropositionIV.5.8.Demonstration. Soit /Llautomate minimal de L ayant QLpour ensem-bledetats. Montronstoutdabordquek+1L =_pQL(S(p) kp).Siuappartient` ak+1L,alors,pardenitiondelaracine(k + 1)-i`eme, uukappartient` aLetdoncukappartient` au1.L. Sionposep=u1.L, celasigniequeuappartient` akpavecp QL. Deplus,pardenitionmemedeS(p),uappartient egalement` acedernierensemble.Demontrons lautre inclusion. Si u appartient au membre de droite, celasigniequepsecritu1.Letqueukappartient` ap. Parconsequent, ukappartient` au1.Letdoncuk+1appartient` aL.Pour conclurelapreuve, onproc`edepar recurrencesurk. Si k=1,alorsparhypoth`ese1L = Lestregulier. Supposons ` apresentque,siLestregulier,kL(k 1)estregulieretmontronsquek+1Llestencore. Auvudulemmeprecedent, pourtoutetat p QL, petS(p)sontreguliers.Par hypoth`ese de recurrence,kp estregulieretdonc S(p) kp estreguliercarilsagitdelintersectiondedeuxlangagesreguliers. Laformuledonneeci-dessus nefaitainsiintervenir quune unionnie delangagesreguliers(eneet, L est regulier et donc, QLest ni). Par consequent,k+1L est regulier.

Voici ` apresentquelquesremarquesconcernantlacomplexitedesalgo-rithmes ` a mettre en oeuvre pour rechercher lautomate minimal dun langageregulier` apartirdunautomatedonne.RemarqueIV.5.10. Onpeutmontrerquelalgorithmederecherchedesetats equivalents dans un AFD/est de complexite temporelle O(n2), si n estlenombredetatsdelautomate /. Eneet,enimplementantlalgorithmedemani`eresoigneuse,ilsutdepasserenrevuelesn etatsde /auplusnfois. Alapremi`ere etape, ontentededistinguerlesetatsde /enutilisantlemotvide. Aladeuxi`emeetape, onpasse` anouveauenrevuelesetatsquelontentededistingueraumoyendemotsdelongueur1etonrep`eteloperationjusquauxmotsdelongueurn 1.Il est possible7dobtenir unalgorithme de complexite temporelle enO(nlog n) en considerant quelques ranements ` a propos de la relation dequi-valence A. Cesranementssortentducadreintroductifdececours.Remarque IV.5.11. Laproceduredeminimisationdonnee` alapropo-sitionIV.4.4peutsaverer co uteusecar elledemandedeuxproceduresde7cf. J.E.Hopcroft,Annlog nalgorithmforminimizingstatesinaniteautomaton,TheoryofMachinesandComputations,AcademicPress,New-York,189196, (1971).IV.6.Exercices 81determinisationetparconsequent, lenombredetatspeutsubirunecrois-sance doublement exponentielle dans le cas le moins favorable. Notons que siL = LR, alors,dans la procedure donnee ` a la proposition IV.4.4,lautomateminimal de L est simplement (/) si / est un AFDaccessibleacceptantL.Ainsi, enresume, pouruneexpressionreguli`eredonnee, onconstruiratoutdabord unautomateni nondeterministe acceptantlelangagegenereparlexpression. CetAFNDcontiendraengeneral des-transitions. Rap-pelons une fois encore que le non determinisme est un outil puissant permet-tantdexprimerfacilementdeslangagesauxspecicationscomplexes. En-suite, onrendracetautomatedeterministe(aveclerisqueinevitableduneexplosionexponentielledunombredetats). Laprocedurededeterminisa-tionfournittoujoursunAFDaccessible. Ilneresteplusalorsqu` areduirelAFDendetectantlesensemblesdetats equivalents.6. ExercicesExercice IV.6.1. Lautomate de lagure IV.14est-il accessible et re-duit? Autrement dit, sagit-il dunautomate minimal ? Memequestion1ba2ab3a,b4ba5baFigureIV.14. UnAFD.aveclautomatedelagureIV.15. Pourcesdeuxautomates, donneruneexpressionreguli`eredulangageaccepte.ExerciceIV.6.2. Donner (enutilisant une methodeauchoix) lautomateminimaldeslangagessuivants:aba(bb),(a +b)aba(a +b),(ab +ba),lelangageformedesmotscontenantlefacteuraaoubb,lelangageformedesmotscontenantlefacteuraaetbb,(aab)(ba),le langage forme des mots de (aab)(ba) qui sont de longueur paire.ExerciceIV.6.3. Soit L = (ab+bab). Quels sont les dierents ensemblesdelaformew1.L, w a, b.82 ChapitreIV.Automateminimal1ab2a b3b4a,b5a6a7babbaFigureIV.15. UnautreAFD.EndeduirelautomateminimaldeL.ExerciceIV.6.4. Montrerque Lnestengeneralpasunecongruence` agauche,i.e.,ilexistez telquex Lyetzx ,Lzy.ExerciceIV.6.5. SoitL= ab, aab, aba, ba, bb, aaa. Quelssontlesdif-ferentsensemblesdelaformew1.L, w a, b.EndeduirelautomateminimaldeL.ExerciceIV.6.6. SoitL=(a + b)abaaba. Quelssontlesdierentsen-semblesdelaformew1.L, w a, b.EndeduirelautomateminimaldeL.ExerciceIV.6.7. Soit L,le langagesur a, bdes mots contenant exacte-mentdeuxa. Quelssontlesdierentsensemblesdelaformew1.L, w a, b.EndeduirelautomateminimaldeL.Exercice IV.6.8. Soit lautomatedeterministe /represente` alagureIV.16. Rechercher lautomate minimal dulangage accepte par /. Onprocedera par deux methodes : la recherche des etats equivalents et la proce-dure ((/)).ExerciceIV.6.9. SoitlelangageL = anbm[ n, m N : n m.Caracteriser les etats de lautomate minimal deLet donner latable detransitiondecetautomate.IV.6.Exercices 83ababababbbaa,bababaFigureIV.16. UnautreAFDdontonchercheleminimal.ExerciceIV.6.10. Soit lautomateni deterministe / represente ` alag-ure IV.17. Rechercher les etats equivalents pour larelation A. Endeduireabbaa,baabbFigureIV.17. Recherchedes etats equivalents.lautomateminimaldulangageacceptepar /.ExerciceIV.6.11. Onconsid`erelalphabet = a, b, c.Donner lautomate minimal dulangage L=abc(dans votrereponse, justierenquoi lautomatequevousproposezestmini-mal).Quelles sont les classes dequivalence de pour la relationdeNerode Let quels sont les dierents ensembles de la forme w1.L,w ?Lacl oturecommutativedeLdonneeparcom(L) = w [ v L, : [w[= [v[est-elleunlangageregulier?Justier.CHAPITREVQuelquescomplementssurleslangagesreguliers1. TransductionDanscettesection, ondenitlanotiondetransducteurqui, dunecer-taine mani`ere, peut etre vue comme une generalisation des morphismes. En-suite, nousmontronsquelensembledeslangagesregulierseststablepourlimageetlimageinversepartransduction.DenitionV.1.1. Untransducteurestun6-uple T =(Q, q0, , , , )o` uQ, q0, , sontdeniscommedanslecasdesAFD, estunalphabetni appelealphabet desortieet : Q estlafonctiondesortie.(On supposera que est une fonction totale.) Un transducteur peut etre vucommeunmoyenpourdenirdesfonctions. Ainsi, ` achaquemot dentreew=w1 w

, wi , letransducteur T associeunmot desortieT (w) donnepar(q0, w1) ((q0, w1), w2) ((q0, w1w2), w3)((q0, w1 w1), w

).Larepresentationsagitale duntransducteur sefait delafa consuivante.Pour tousq, q

Q, ,si(q, ) = q

et(q, ) = u ,alorsonnoteq/u q

.Exemple V.1.2. Voici unexemple de transducteur. Ici, =a, b,1 2a/ab/bcb/ba/aFigureV.1. Untransducteur.lalphabet de sortie est = a, b, c et lafonctionde sortie est deniepar(1, a)=a,(1, b)=b,(2, a)=aet(2, b)=bc. Considerantlemotw = bab,ona1b/b1a/a2b/bc1etdonc T (w)=babc. Il estfaciledevoirquecetransducteurins`ereuncapr`eschaqueoccurrencedeabdanslemotdentree.RemarqueV.1.3. Lafonctionsur et` avaleursdans,denie parletransducteur T ,estsouventappeleefonctionrationnelle.8586 ChapitreV.QuelquescomplementssurleslangagesreguliersExempleV.1.4. Si f : estunmorphismedemonodes, cettefonction peut etre aisement realisee par un transducteur possedant un uniqueetat. Eneet, il sutdeconsidererletransducteurrepresente` alagureV.2. /f() 1FigureV.2. Untransducteurcalculantlemorphismef.Remarque V.1.5. Dans lalitterature, ontrouvedautres mod`eles plusgenerauxde transducteurs, commeparexemple,des transducteurs constru-itsnonpassurunAFDmaissurunAFND. Danscecas, letransducteurnedenitplusunefonctiondedansmaisunerelation(rationnelle),i.e., une partie de . On peut aussi trouver des mod`eles dans lesquelsonprecise des etatsnals. Dans cedernier cas,ne sont acceptesque les cal-culsdontlalecturedumotdentreeconduit` aunetatnal. Danscecoursintroductif,nousavonsdecidedepassercesgeneralisationssoussilence.Lensembledeslangagesregulierseststablepartransduction.Theor`emeV.1.6. SoientL unlangageregulieret T untransduc-teur. LelangageT (L) = T (w) [ w L estregulier.Demonstration.1Soient /=(Q, q0, F, , ) unAFDacceptant LetT =(Q

, q

0, ,

, , ) letransducteurdonnedanslenonce. NousallonsconstruireunAFND B=(Q

, q

0, F

, ,

) acceptant exactement T (L).Onledenitcommesuit:Q

= QQ

()0, 1, . . . , k o` u k= max,q

Q [(q

, )[,q

0= (q0, q

0, , 0),larelationdetransition

Q

Q

contientleselementssuivants. Pouttout ,((q, q

, , 0), , (q, q

, , 0))

.Si(q

, ) = y1 yj,alorspourtoutitelque1 i j((q, q

, , i 1), yi, (q, q

, , i))

et((q, q

, , j), , ((q, ),

(q

, ), , 0))

.1La preuve presentee ici est issue de : J.-P. Allouche, J. Shallit, AutomaticSequences,Theory,Applications,Generalizations,CambridgeUniversityPress(2003).V.1.Transduction 87Enparticulier,si(q

, ) = alors((q, q

, , 0), , ((q, ),

(q

, ), , 0))

.Enn,F= (q, q

, , 0) : q F.Lidee` alabasedecettedenitionestlasuivante: si w T (L), il existex L tel que w = T (x). Supposons que x = x1 xr, xt , et que wt soitlasortiecorrespondant` alalecturedextdans T . Enparticulier, onaw= w1 wr. Lautomate Bpeutdevinerdemani`erenondeterministesilexisteun motx L produisant lemotw. Eneet,lapremi`ere composantedeQ

permetdesimulerlecomportementde /. Ladeuxi`emecomposantesimulelecomportementde T . Latroisi`emecomposantedeQ

estutiliseepourmemoriserlalettre=xtdumotxqui vientdetresupposee. Laquatri`emecomposantepermetdesavoircombiendelettresdewtontdej` aeterencontrees. Cettederni`erecomposantesertdecompteur, initialise` azeroet incrementeduneunite` achaquefois quunelettredewtest lue.Lorsque ce compteur atteint [wt[, on utilise une -transition pour reinitialiserlatroisi`eme composante ` aet laquatri`eme` a0. De plus, pour simulerlecomportementde /et T , lapremi`erecomposantepasse` a(q, )etladeuxi`eme` a

(q

, ). IlnoussutdemontrerqueT (L) = L(B).Soit w T (L). Il existex=x1 xr Ltel que T (x) =w. Commeprecedemment, wtest lasortiecorrespondant ` axtet onnotekt= [wt[.Lexecutiondexdans /donnelasuitedetatsq0= p0, p1, . . . , pro` upr Fcarx L. Defa consemblable,lalecturedexdans T conduit` alasuiteq

0= p

0x1/w1p

1x2/w2p

2xr/wrp

r.Onnotewt= wt1 wtkt. Ainsi,dans B,lalecturedewpeutconduire` alasuitedetats(p0, p

0, , 0). .=q

0(p0, p

0, x1, 0)w11(p0, p

0, x1, 1) w1k1(p0, p

0, x1, k1)((p0, x1),

(p

0, x1), , 0). .=(p1,p

1,,0)(p1, p

1, x2, 0)w21w2k2 (p1, p

1, x2, k2)(p2, p

2, , 0)(p2, p

2, x3, 0) ...(pr1, p

r1, , 0)(pr1, p

r1, xr, 0)wr1wrkr(pr1, p

r1, xr, kr)(pr, p

r, , 0) F

.Ceci prouvequelemotw=w11 w1k1w21 w2k2 wr1 wrkrestac-ceptepar B. Pour lautreinclusion, si w L(B), alors celasigniequepartant deletat initial q

0, ondisposeduncheminconduisant` aunetat88 ChapitreV.Quelquescomplementssurleslangagesreguliersnal deF

. Ainsi, pardenitionde B, onretrouveunmotx Ltel queT (x) = wetparconsequent,wappartientbien` a T (L).

Remarque V.1.7. Au vu de lexemple V.1.4 et du theor`eme precedent, onretrouve commecasparticulier,lefaitquelensemble des langagesregulierseststableparmorphisme(cf. propositionII.3.4).Lensembledeslangagesreguliersestaussistableparimageinversepartransduction.PropositionV.1.8. SoientL unlangageregulieret T untransduc-teur. LelangageT1(L) = x [ T (x) Lestregulier.Demonstration. Il est aisedeconstruireunAFDacceptant T 1(L) ` apartirdunAFD /=(Q, q0, F, , )acceptantLetdutransducteur T =(Q

, q

0, ,

, , )donnedanslenonce. SoitlAFD B=(Q

, q

0, F

, ,

)deniparQ

= Q

Q,q

0= (q

0, q0),F

= Q

Fetpourtout ,

((q

, q), ) = (

(q

, ), (q, (q

, ))).La premi`ere composante simule le transducteur T et la seconde composantesimulelautomate /sur lasortieproduitepar T . Ainsi, il est clair queL(B) = T1(L).

2. RecherchedunmotdansuntexteUneapplicationpratique desautomatesconcernelarecherche dun motdansuntexte. Eneet,lestraitementsdetextesquelonpeuttrouversurnimportequelleplate-forme utilisent demani`ereinternedes algorithmesbasessurlaconstructiondautomatespourimplementerlesfonctionsbienutiles derecherche(nd,ndandreplace, etc. . . ). Atitreindicatif2,Tcl,Perl,Python,GNU Emacs,ed,sed,vi, laplupart des versions degrepet certaines versionsdeegrepet awkutilisent des AFND. Par contre, lamajorite des versions de egrep etawk, lex etflex utilisent quant ` a eux desAFD.Notre but est ici de rechercher les occurrences dun mot u dans un texteTecritsurlalphabet(untexteetantunesuiteniedesymbolesde,2Pour plus de details,voir par exemple, J.E.F.Friedl, MasteringRegularExpressions,OReilly.V.2.Recherchedunmotdansuntexte 89il sagit simplement dunmot sur ). Ainsi, nous recherchons unAFDacceptantlelangageL = u.Pourcefaire, nousallons decrirelautomateminimal decelangage. Lesetatssontdelaformew1.Lavecw . Ainsi,v w1.L wv u.Pour decrire lesensembles w1.L,ilest utiledintroduire, pour toutprexepdeu,lensembleEu(p) = [

, : p =

, u =

formedessuxesdeuqui, completesparunsuxedep, donnentu. Onremarquequaveccettedenition,uappartienttoujours` aEu(p).Soitvappartenant` aw1.L. Si [v[ [u[, alorsvappartient` aLcarvposs`edeucommesuxe. Onenconclutdoncquew1.L L.Sinon, [v[< [u[. Danscecas, onposew,ucommeetantleplusgrandsuxe de w qui soit prexe de u. Il est clair que w,u et Eu(w,u) dependentuniquement deuetw.wuvFigureV.3. wvappartient` au.ExempleV.2.1. Aveclesnotationsprecedentes,siw = aabbab et u = babbaab,alorsaabbab. .wbaab et aabbab. .wabbaabappartiennent` aL = u. Ici,w,u= babcaru = bab baabw = aab bab.Deplus,onaEu(w,u) = baab, abbaab, uEneet, lessuxesdew,usont, b, ab, bab. Parmi eux, babetbsontprexesdeuetonalesfactorisationssuivantes,u =

..bab..w,ubaab et u =..ba

..b. .w,uabbaab.90 ChapitreV.QuelquescomplementssurleslangagesreguliersAinsi,onseconvaincaisementquew1.L = L Eu(w,u).Siu = u1 u

,lesprexesdeusontp0= ,p1= u1,. . . ,p

= u1 u

.Les etatsdelautomateminimaldeLsontdonclesL Eu(pi), i 0, . . . , .Auvudecequiprec`ede,ilestclairqueL Eu(pi) = p1i.L.Si on se rappelle la denition de lautomate minimal dun langage, on retrouvelescaracteristiquesdecelui-ci.Letatinitialesttelquep1i.L = L,etdonci=0. Eneet, si 0