Théorie des automates et langages formels

FacultedessciencesDepartementdemathematiquesTheoriedesautomatesetlangagesformels1acb2adcb3a,c,db4bca5dca6b,c,da7a,bc8dc9a,b,c,da,bbdddAnneeacademique2009{2010MichelRigoTabledesmatieresChapitreI.Motsetlangages11.Premieresdenitions12.Langages103.Expressionsregulieresetlangagesassocies154.Exercices22ChapitreII.Automates271.Automatesnisdeterministes272.Automatesnondeterministes293.Stabilitedeslangagesacceptesparautomate394.Produitd'automates435.Exercices46ChapitreIII.Langagesreguliersetautomates511.Desexpressionsauxautomates512.Desautomatesauxexpressionsregulieres543.Stabilitedelaregularite574.Criteredenon-regularite585.Exercices61ChapitreIV.Automateminimal631.Introduction632.Congruencesyntaxique643.Automateminimal664.Constructiondel'automateminimal725.Applications776.Exercices81ChapitreV.Quelquescomplementssurleslangagesreguliers851.Transduction852.Recherched'unmotdansuntexte883.Fonctiondecomplexited'unlangageregulier924.Monodesyntaxique995.Langagessansetoile1056.Exercices109ChapitreVI.Introductionauxlangagesalgebriques1151.Premieresdenitions115iiiChapitre.Tabledesmatieres2.Arbresd'analyse1193.Uneillustrationdel'ambiguite1224.Grammairesetlangagesreguliers1265.AproposdelahierarchiedeChomsky1286.Formesnormales1307.Lemmedelapompe1408.Automatesapile1439.Stabiliteducaracterealgebrique15110.UntheoremedeSchutzenberger15211.Exercices155Bibliographie159Listedesgures161Index165CHAPITREIMotsetlangagesCepremierchapitreintroduitquelquesconceptsfondamentauxdelatheoriedeslangagesformelsetdelacombinatoiresurlesmots.Lacom-binatoiredesmotsetudielesproprietesdessuitesdesymboles.Latheoriedeslangagesformelsenglobelatheoriedesautomatesets'interesseauxpro-prietesmathematiquesdeslangagesquisontdesensemblesdemots.Elletrouvenotammentdesapplicationsenvericationetpourlacompilation.1.PremieresdenitionsDenitionI.1.1.Unalphabetestunensembleni.Unalphabetseraengeneraldesigneparunelettregrecquemajuscule.Ainsi,=fa;b;cg;=f~;};|;g;=f0;1g;=f!; ;";#gsontdesalphabets.Leselementsd'unalphabetsontappeleslettresousym-bolesExempleI.1.2.Lebiologisteinteresseparl'etudedel'ADNutiliseraunalphabetaquatrelettresfA;C;G;Tgpourlesquatreconstituantsdesgenes:Adenine,Cytosine,GuanineetThymine.DenitionI.1.3.Soitunalphabet.Unmotsurestunesuitenie(etordonnee)desymboles.Parexemple,abbacetbasontdeuxmotssurl'alphabetfa;b;cg.Lalongueurd'unmotwestlenombredesymbolesconstituantcemot;onlanotejwj.Ainsi,jabbacj=5etjbaj=2:L'uniquemotdelongueur0estlemotcorrespondantalasuitevide.Cemots'appellelemotvideetonlenote".L'ensembledesmotssurestnote.Parexemple,fa;b;cg=f";a;b;c;aa;ab;ac;ba;bb;bc;ca;cb;cc;aaa;aab;:::g:DenitionI.1.4.Siestunelettredel'alphabet,pourtoutmotw=w1wk2,ondenoteparjwj=#fi2f1;:::;kgjwi=glenombredelettresiapparaissantdanslemotw.Parexemple,jabbacja=2etjabbacjc=1.12ChapitreI.MotsetlangagesSil'alphabetdecardinaln1estordonne,onpourraleconsiderercommeunn-uple=(1;:::;n).OndenitalorslafonctiondeParikh :!Nnpar (w)=(jwj1;:::;jwjn):Len-uple (w)estappelevecteurdeParikhdew.Ilestclairquesin>1,alors n'estpasinjectif.DenitionI.1.5.Soitw=w1w`unmotsur.Lesmots";w1;w1w2;:::;w1w`1;w1w`=wsontlesprexesdew.Unprexedewdierentde"etdewestditpropre.Defaconsemblable,";w`;w`1w`;:::;w2w`;w1w`=wsontlessuxesdew.Unsuxedewestqualiedepropres'ildierede"etdew.Soient1ij`.Lemotwiwjestunfacteurdumotw.Onlenoteparfoisw[i;j].Unefoisencore,onparledefacteurproprelorsquecedernierdieredewetde".L'ensembledesprexes(resp.suxes,facteurs)dewestnotePref(w)(resp.Su(w),Fac(w)).RemarqueI.1.6.Onpeutobserverquepuisqueestunensembleni,estdenombrable1.Rappelonsladenitiond'unmonode.DenitionI.1.7.SoientAunensembleet:AA!Auneopera-tionbinaireinterneetpartoutdenie.L'ensembleAmunidel'operationpossedeunestructuredemonodesilesproprietessuivantessontsatisfaites.IL'operationestassociative:8x;y;z2A:(xy)z=x(yz):IIlexisteunneutre(unique)e2Atelque8x2A:xe=ex=x:RemarqueI.1.8.Unmonode(A;)quiesttelquetoutelementdeApossedeuninverseestungroupe.ExempleI.1.9.Toutgroupeestunmonode;(N;+)estunmonodequin'estpasungroupe.Protons-enpourrappelerladenitiond'unmorphismedemonodes.

1) Eneet,leselementsdepeuventchacun^etrecaracterisesparunnombrenid'indicesprenantleurvaleurdansdesensemblesdenombrables(ici,ils'agitm^emed'ensemblesnis,asavoir).I.1.Premieresdenitions3DenitionI.1.10.Soient(A;)et(B;r)deuxmonodesdeneutrere-spectifeAeteB.Uneapplicationf:A!Bestunmorphisme(ouencorehomomorphisme)demonodessi(1)8x;y2A:f(xy)=f(x)rf(y)et(2)f(eA)=eB:RemarqueI.1.11.Danslecasd'unhomomorphismedegroupes,lacon-dition(2)estuneconsequencedirectede(1)etdel'existenced'inverseauseindesgroupes2.Parcontre,danslecasdemonodes,lacondition(2)faitbeletbienpartiedeladenitiond'unmorphismedemonodes.DenitionI.1.12.Soitunalphabet.Ondenitl'operationdecon-catenationsurdelafaconsuivante.Pourtousmotsu=u1uketv=v1v`,ui;vi2,laconcatenationdeuetv,noteeu:vousimplementuv,estlemotOnutiliseradorenavantlanotationmultiplicative.w=w1wk+`ouwi=ui;1ikwk+i=vi;1i`:Ainsi,munidel'operationdeconcatenationestunmonodedeneutre".Enparticulier,ondenitlapuissancen-iemed'unmotwcommelaconcatenationdencopiesdew,wn=ww|{z}nfois:Onposew0=".RemarqueI.1.13.Ilestutilederemarquerquesi#>1,alorsestunmonodenoncommutatif,i.e.,ilexisteu;v2telsqueuv6=vu.ExempleI.1.14.L'applicationlongueurjj:!Nestunmorphismedemonodesentre(;:)et(N;+).Eneet,8u;v2:juvj=juj+jvjetj"j=0.ExempleI.1.15.Consideronsl'alphabet=fa;b;cgetlemorphisme':!denipar'(a)=abc,'(b)=acet'(c)=b.Eneet,pourdeniruntelmorphisme,onremarqueraqu'ilsutdesedonnerl'imagedelettres.Ona,parexemple,'(abbc)='(a)'(b)'(b)'(c)=abcacacb:2pourtoutx2A,f(x)=f(eAx)=f(eA)rf(x).D'oulaconclusionenmultipliantparf(x)1.

4) ChapitreI.MotsetlangagesVoiciapresentquelquesproprietesclassiquesdecombinatoiredesmots(classication68R15del'AmericanMathematicalSociety).Ons'interesseprincipalementauxcongurationsdeslettres,desfacteursouencoredesmo-tifspouvantappara^tredansuncadrenoncommutatif(caractereinevitable,frequenced'apparition,etc.).Voir,parexemple,l'excellentsurvol[10].PropositionI.1.16.Surunalphabetbinaire,toutmotdelongueuraumoins4contientuncarre,i.e.,unfacteurdelaformeuu,u6=".Cetteproprietetrivialemontredoncquel'apparitiond'uncarreestin-evitablesurunalphabetdedeuxlettres.Parcontre,surtroislettres,iln'enestrien.Ainsi,laclassicationdesmotifsevitablesounonestloind'^etreaisee.Unmotinnisurunalphabetestsimplementuneapplicationw:N!(i.e.,unesuitedelettresindexeeparN).Onpeutmunirl'ensemble!desmotsinnissurd'unedistanced:!!!Rdeniecommesuit.Sixetysontdeuxmotsinnis,alorsx^ydesigneleurpluslongprexecommun.Six=y,alorsonposed(x;y)=0,sinond(x;y)=2jx^yj:Onverieraaisementqu'ils'agitbiend'unedistance.Cettedistancepossedeuneproprietesupplementaire,elleestultrametrique3(onutiliseparfoisletermenon-archimedienne):8x;y;z2!:d(x;z)maxfd(x;y);d(y;z)g:Ayantanotredispositionunespacemetrique(!;d),onpeutparlerdesuitesconvergentesdemotsinnis,etc.Soitcunelettren'appartenantpasa.Onpeutplongerdans([fcg)!enidentiantlemotniw2aveclemotinniwccc2([fcg)!.Cetteidenticationfaite,ilestlicitedeparlerd'unesuitedemotsnisconvergeantversunmotinnilimite.PropositionI.1.17.Lemotinni'!(a)ou'(a)=abc,'(b)=acet'(c)=b,estsanscarre.Onremarquefacilementque'n(a)estprexede'n+1(a)pourtoutn0.Ilsutdeprocederparrecurrence.Si'n+1(a)='n(a)u,alors'n+2(a)='n+1(a)'(u).Deplus,lasuite(j'n(a)j)n0eststrictementcrois-sante.Pourcesdeuxraisonsetaveclatopologieassocieealametriquepresenteeprecedemment,onpeutdirequelasuite('n(a))n0convergeversunmotinnilimite.

3) Onrencontrenotammentcetypedeproprieteenanalysep-adique.Latopologieassocieeestinteressante:toutpointd'unebouleenestlecentre,deuxboulesontuneintersectionnonvidesietseulementsil'uneestinclusedansl'autre,touttriangleestisocele,etc.I.1.Premieresdenitions5'0(a)=a'1(a)=abc'2(a)=abcacb'3(a)=abcacbabcbac...Lademonstrationdufaitquelemotinnilimite'!(a)estsanscarre4seradonneeenndesection.Enparticulier,surunalphabetdetroislettres,ilexistedesmots(nis)arbitrairementlongssanscarre.Pourobtenirceresultat,nousmontreronsd'abordqu'ilexiste,surdeuxlettres,desmotsarbitrairementlongssanschevauchement.PropositionI.1.18.Deuxmotsuetvcommutents'ilssontpuissancesd'unm^emetroisieme,i.e.,s'ilexisteunmotwetdesentiersi;jtelsqueu=wietv=wj.Demonstration.Onprocedeparrecurrencesurlalongueurdeuv.Sijuvj=0,leresultatestimmediat.Supposonsapresentleresultatsatisfaitpourjuvj

6) ChapitreI.Motsetlangagesavecxnonvide,alorsilexistedesmotsu;vetunentierk0telsquex=uv;y=(uv)ku=u(vu)ketz=vu:Demonstration.Sijxjjyj,alorsnousavonslasituationsuivante.Ainsi,yyxzyvFigureI.2.xy=yz,jxjjyj.ilexisteunmotvtelquex=yv(sijxj=jyj,alorsv=").Danscecas,onpeutprendreu=yetk=0.Si00.Soitjxjjwjetonappliquelapremierepartiedelapreuve,soitjxj0telquefj(0)=0(unteljexistetoujourscarfestunepermutationetsedecomposedoncenproduitdecycles).Pardenitionm^emedef,celasigniequ'ilexistea;b2Ntelsquej=a+betapbq=0.Puisqueap=bqetquepetqsontpremiersentreeux,onenconclutquepjb,qjaetdoncjp+q.Parconsequent,lapermutationdef0;:::;p+q1ginduiteparfsecomposed'ununiquecycledelongueurp+q.Remarquonsapresentquel'applicationfestenrelationetroiteavecnoshypothesesdeperiodicite:wi=wi+ppourtout1i 5) N.J.Fine,H.S.Wilf,Uniquenesstheoremsforperiodicfunctions,Proc.Amer.Math.Soc.16(1965),109{114.

6) Denirfsurf0;:::;p+q1getnonsurf1;:::;p+q1gcommecelaauraitpusemblernaturel,nousserabienutile.Auvudelapreuve,pourquoi?8ChapitreI.MotsetlangagesNouspouvonsapresentprocederalapreuvedutheoremedeFineetWilf.Demonstration.Onpeutsupposerquejwj=p+qpgcd(p;q).Enfait,silemotwestpluslong,onconsideresonprexevdelongueurp+qpgcd(p;q).Sil'onmontrequevpossedepgcd(p;q)commeperiode,alorsgr^aceaulemmeI.1.22,leresultats'etendawtoutentiercarwpossededejapouqcommeperiode.Onpeutdeplussupposerqued=pgcd(p;q)=1,carsinon,enprenantunelettresurddansw,onestpresencededmotsdelongueurk=p=d+q=d1wiwi+dwi+(k1)d;i=1;:::;detdeperiodesp=detq=dpremieresentreelles.AuvudulemmeI.1.24,chacundesdmotsestconstantetonentirelad-periodicitedew.ExempleI.1.25.LabornedonneedansletheoremedeFineetWilfestoptimale:abaab|{z}abaab|{z}abaab|{z}aest5-periodique,13-periodiquemaisestdelongueur16=5+13pgcd(5;13)1.Pourterminercettesection,ondenit,parrecurrencesurlalongueurdew,l'operationmiroir7delamanieresuivante:sijwj=0,alorsw="etwR=";sinonjwj>0etw=u,2,u2etwR=uR.SiwesttelquewR=w;alorswestunpalindrome.DenitionI.1.26.Unmotnidelaformeauauaouu2eta2estunchevauchement(enanglais,overlap).a u a u aOnremarquequetoutchevauchementcontientuncarre.Dem^eme,uncube(i.e.,motdelaformeuuu)estunchevauchementparticulier.Nousavonsvuquesurunalphabetbinaire,toutmotdelongueur4contientuncarre.Lefaitdecontenirunchevauchementestuneproprieteplusforte.Cetteproprieteest-elleevitablesurdeuxlettres?PropositionI.1.27.LemotdeThue-Morse,denicommet=f!(a)ouf(a)=abetf(b)=ba,estunmotinnisanschevauchement.

7) OnutiliselalettreRcarlaterminologieanglo-saxonnefaitsouventreferenceaumot\reversal"ou\reverse".Danslalitterature,ontrouveparfoislanotationew.I.1.Premieresdenitions9t=abbabaabbaababbabaababbaabbabaabLapreuvedeceresultatestcalqueesurcellepresenteedans[21].PourdesapplicationsdumotdeThue-Morse,onlira[4].LemmeI.1.28.SoitX=fab;bag.SixappartientaX,alorsaxaetbxbn'appartiennentpasaX.Demonstration.Onprocedeparrecurrencesurjxj.Six=",ilestclairqueaa;bb62X.Supposonsleresultatveriepourlesmotsdelongueur

8) Onremarqueraquefa;ab;abbgestuncode.I.2.Langages11DenitionI.2.1.Unlangagesurestsimplementunensemble(niouinni)demotssur.End'autrestermes,unlangageestunepartiede.Ondistingueenparticulierlelangagevide9;.ExempleI.2.2.Consideronsl'alphabet=fa;b;cg.L'ensemblefa;aa;bbc;ccca;abababgestunlangageni.L'ensembleL2adesmotssurcomprenantunnombrepairdeaestaussiunlangage(inni),L2a=f";b;c;aa;bb;bc;cb;cc;aab;aac;aba;aca;:::;abaacaaa;:::g:L'ensemblePal()formedespalindromesdeestaussiunlangageinni,Pal()=f";a;b;c;aa;bb;cc;aaa;aba;aca;bab;bbb;bcb;cac;cbc;ccc;aaaa;abba;acca;baab;bbbb;bccb;caac;cbbc;cccc;:::g:Soitl'alphabet=f0;1g.L'ensembleconstituedesecrituresbinaires10desentierspositifspairsestunlangagesurf10;100;110;1000;1010;1100;1110;:::gdem^emequelelangageformedesecrituresbinairesdesnombrespremiersf10;11;101;111;1011;1101;10001;:::g:Passonsapresentenrevuequelquesoperationssurleslangages.Toutd'abord,puisqu'unlangageestunensemble,ondisposedesoperationsen-semblistesusuellescommel'union,l'intersectionouencorelacomplementa-tion.DenitionI.2.3.SoientL;Mdeuxlangages.LaconcatenationdeslangagesLetMestlelangageLM=fuvju2L;v2Mg:Enparticulier,onpeutdenirlapuissancen-iemed'unlangageL,n>0,parLn=fw1wnj8i2f1;:::;ng;wi2LgetonposeL0=f"g.Parexemple,siL=fa;ab;ba;acg,alorsL2=faa;aab;aba;aac;abab;abba;abac;baa;baab;baba;baac;aca;acab;acba;acacg:9Nepasconfondrelelangagevidenecontenantaucunelementetlelangagef"gcontenantuniquementlemotvide.10Unmotw=w`w02f0;1grepresentel'entiernsin=P`i=0wi2i.Engeneral,onneconsiderequedesmotsdontlepremiersymbolew`dierede0.Parconvention,l'entierzeroestalorsrepresenteparlemotvide.12ChapitreI.MotsetlangagesRemarqueI.2.4.Soitn0.L'ensembledesmotsdelongueurnsurestn.NotonsaussiquesiunmotuvappartientaLMavecu2Letv2M,cettefactorisationn'estpasnecessairementunique.Parexemple,avecL=fa;ab;bag,L2contientlemotabaquisefactoriseena(ba)et(ab)a.Demanderl'unicitedelafactorisationdebouchesurlanotiondecode.Ainsi,Xestuncode,sitoutmotdeXsefactorisedemaniereuniquecommeconcatenationdemotsdeX.PropositionI.2.5.Laconcatenationdelangagesestuneoperationasso-ciative,ellepossedef"gpourneutre,;pourabsorbantetestdistributiveadroiteetagauchepourl'union,i.e.,siL1;L2;L3sontdeslangagesL1(L2L3)=(L1L2)L3;L1f"g=f"gL1=L1;L1;=;L1=;;L1(L2[L3)=(L1L2)[(L1L3);(L1[L2)L3=(L1L3)[(L2L3):Demonstration.C'estimmediat.DenitionI.2.6.SoitL.L'etoiledeKleene11deLestdonneeparL=[i0Li:Ainsi,lesmotsdeLsontexactementlesmotsobtenusenconcatenantunnombrearbitrairedemotsdeL.RemarqueI.2.7.Onremarquequelanotationintroduiteprecedem-mentestcoherentepuisqu'ils'agitenfaitdel'etoiledeKleenedulangageni.Onditparfoisqueestlemonodelibreengendrepar.Onrencontreparfoisl'operationL+denieparL+=[i1Li:Parexemple,siestunalphabet,alors+=nf"g.D'unemanieregenerale,siLestunlangagenecontenantpaslemotvide,alorsL+=Lnf"g.PropositionI.2.8.SoitLunlangage.LelangageLestlepluspetit12langageMtelque"2M,LMetM2M.11StephenColeKleene(1909{1994),logicien,est,avecK.Godel,A.Turing,A.Church,E.Post,l'undesperesfondateursdel'informatiquetheorique.Onluidoitnotam-mentleconceptd'expressionreguliere.S.C.Kleene,RepresentationofEventsinNerveNetsandFiniteAutom