cours-ir09

Publié par

AutomatesNotions de baseNotes de cours, IR1, 2009Sylvain Lombardy1 Alphabets, mots, langagesUn alphabet A est un ensemble fini de symboles appel´es lettres.Un mot est une suite finie de lettres.∗On note A l’ensemble des mots que l’on peut former avec des lettres de l’alphabet A.∗Un langage sur un alphabet A est un ensemble (fini ou infini) de mots de A .Exemples :1. L’alphabet A permettant d’´ecrire les mots usuels comporte environ soixante-dix lettres (mi-1nuscules, majuscules, lettres accentu´ees). L’ensemble des mots du fran¸cais est un langage sur A .1∗Le mot carichon appartient `a A mais n’est pas un mot fran¸cais.12. Les s´equences d’ADN se repr´esentent sur un alphabet A ={G,A,T,C}. Une s´equence d’ADN2∗ ∗est un mot de A , mais un mot de A n’est pas forc´ement une s´equence correcte.2 23. On peut prendre comme alphabet A l’ensemble des mots du fran¸cais (plusieurs centaines de3milliers de mots). Un “mot” est alors une suite finie d’´el´ements de cet alphabet, c’est donc cequ’on appelle habituellement une phrase. Les phrases correctes sont un langage sur A .32 Automates non d´eterministesD´efinition Un automate (non-d´eterministe) A sur un alphabet A est d´efini par les ´el´ementssuivants :– un ensemble fini d’´etats not´e Q;– un ensemble fini E de transitions, chaque transition ´etant d´efinie par un ´etat de d´epart p, un´etat d’arriv´ee q et une ´etiquette a appartenant `a A; on note une telle transition (p,a,q).– un sous-ensemble de Q appel´e ...
Publié le : vendredi 23 septembre 2011
Lecture(s) : 30
Nombre de pages : 8
Voir plus Voir moins
1
Automates Notions de base Notes de cours, IR1, 2009 Sylvain Lombardy
Alphabets, mots, langages
UnalphabetAseemnsnetudenieblselobmysse´leppalettres. Un mot est une suite finie de lettres. On noteAl’ensemble des mots que l’on peut former avec des lettres de l’alphabetA. Unlangagesur un alphabetAest un ensemble (fini ou infini) de mots deA. Exemples : 1. L’alphabetA1im(epstomseleocsleusunttaetrmircr´edeidaxtnrtselxteteenmpornsoiviro nuscules,majuscules,lettresaccentue´es).Lensembledesmotsdufranc¸aisestunlangagesurA1. Le motcarichonitneppraat`aAemsottpfaissnuncaimsaran¸. 1 2.Less´equencesdADNserepre´sententsurunalphabetA2={G, A, T , C}.Unsee´uqneecdDAN ∗ ∗ est un mot deA, mais un mot deA.entseutenmenero´capfsrectecoruencs´eq 2 2 3. On peut prendre comme alphabetA3iatndsenueisecsreeledmstolneesbmcais(plusdufran¸ milliersdemots).Unmotestalorsunesuiteniede´l´ementsdecetalphabet,cestdoncce qu’on appelle habituellement une phrase. Les phrases correctes sont un langage surA3.
2
Automates non
de´terministes
De´nitionondte(ntomaUnauetsi)ete´nimrAsur un alphabetAtdesmentsel´slee´e´npira suivants : – un ensemble fini d’´eatsteon´tQ; – un ensemble finiEdetransitionsntd´´etationansiatdtnue´peraeinrtpa´eedqahcrteu,p, un ´etatdarrive´eqet une´teqieutteartenant`apaapA; on note une telle transition (p, a, q). – un sousensemble deQstatepaeenspel´ed´emblinitiaux´etonI; – un sousensemble deQate´stbmesdelelppen´eaterminauxot´enT. Untelautomateestnote´A=hQ, A, E, I, Ti´dnodnauq,isniA.nnenoodate,utomtunaeni successivementsonensembled´etats,lalphabetsurlequelilestd´eni,sonensembledetransitions, sonensembled´etatsinitiauxetsonensemblede´tatsterminaux.
Repr´esentationgraphiquesteeatomutnaUmmoce´tnese´rpereorient´eungraph´t:e´eteqieu lese´tatssontdesronds(a`linte´rieurdesquelsone´critlenomdel´etat),lestransitionssont repr´esent´eespardes`echesquipartentdel´etatded´epartetpointentsurl´etatdarriv´ee,on indiqueaumilieudelae`chelalettrequienestl´etiquette.Un´etatinitialestsignale´parune petite`echequipointesurl´etat,une´tatterminalparunepetitee`chequienpart(etquipointe dans le vide). Exemple : a, c, g, t a, c, g, t g t a p q r s
L’automate cidessus est l’automateA=hQ, A, E, I, Ti, avecQ={p, q, r, s},A={a, c, g, t}, E={(p, a, p),(p, c, p),(p, g, p),(p, t, p),(p, g, q),(q, t, r),(r, a, s),(s, a, s),(s, c, s),(s, g, s),(s, t, s)}, I={p, q}etT={s}arqueque.Onremestlemmˆioitonnstsrusnarlpiseisutetperaed´datstsee´ darriv´ee,onnedessinequune`echeenindiquantlesdi´erentse´tiquettes.
1
Cheminsetlangageaccepte´sUncheminitionscons´eutenustidetearsnseetamotualsnad cutives,cest`adireunesuite(p1, a1, q1),(p2, a2, q2), ...,(pn, an, qn) telle queqi=pi+1etdta´eL. d´epartducheminestl´etatded´epartdelapremi`eretransition,l´etatdarrive´educheminestcelui deladernie`retransition.L´etiquetteduncheminestlemota1a2...annenaltsebtoueenonnct´ca e´tiquettesdestransitionsduchemin. Un chemin est´ersiusilsneecocmmnue´adsnnititatisilalet.lnUimanttre´etansunvedaarri telcheminestparfoisappele´calcul. Un mot estept´eacctsele´ldissitnoinemeur´teischunetslixeluaotampargeteetituqnaagL.le reconnumoesedblptceactsseetamotmesnelt.laupare´psraluaotamet Deux automates sonte´viuqnelastsrilonecisnantses.gegaanelemmˆle
Exemple :Le motcgtagparlpt´eacceestedssceimotaatulstti´ecauslerimehcniteuqudet re´ussisuivant: c g t a g p−→p−→q−→r−→s−→sSionregardeattentivementlautomate,onconstatequetouslescheminsr´eussispartentdes´etats pouqet arrivent enstrnadte.eLcsheminsr´eussispapte´teuqise´tostnxecatementceuxquison par un mot qui contientgta(on dit quegtaest unfacteur; ceux qui partent dedu mot) qsont ´etiquet´espardesmotsquicommencentparta(on dit quetatuesr´npgageL.)tnaleexeomud reconnu par cet automate est donc l’ensemble des mots sur{a, c, g, t}qui soit contiennent le facteur gtar´exe,itsoocmmneectnaplrpeta.
D´ecidersiunmotestaccepte´parunautomatetdedermederc´eciogirLlauqpihtemiec consiste`alirelemotlettreparlettreeta`calculertouslese´tatsquelonpeutatteindrea`partir dune´tatinitialenayantluceslettres. Formellement, soitw=w1w2...wkun mot (wiest laiteleme`otumedtrt)eA=hQ, A, E, I, Ti unautomate.Onveutd´ecidersiwaratsepeccpe´tA.Xiqueltatses´ebleduetopnesetlemns atteindre en ayant luw1w2...wi. Calcul deXk: X0=I; – pouride1`ak Xi=pour toutpdansXi1 pour toutqtel que (p, wi, q) est dansE Xi=Xi∪ {q} Le motwacstesi´eptcelumeteesinestXkT6=: – pour toutpdansXk sipest dansT retourne VRAI (watccpe´t)ees retourne FAUX 2 Lacomplexite´decetalgorithmeestO(knu`o,)kest la longueur du mot etnest le nombre d´etatsdelautomate.Eneet,Xipeut contenirnytvaioresitplue´etatntransitions partant depiquet´eeraps´etwi.
´ Etatsutiles,automatese´monde´tetaU´npd’un automateAestutiles’il existe un chemin re´ussipassantparpageutpesuleripprsmemsnaidoelregnal.Siun´etatnseptsatuli,eno reconnu. Un automate estdne´e´omseustosissatets´elitutnotuepnO.senteuanuamotome´redn supprimanttousses´etatsinutiles.
3
Automatesd´eterministes
Un automate estrmte´edetnisinititatiul´eunseqaulinstateetal,psirtout´oup, toute lettrea, il y aau plus unetransition partant depti´eraep´eetqua.
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.