cours-ir09

Description

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 ...

Informations

• Publié par: Udru
• Nombre de lectures: 30
• Langue: Français

Extrait

1

Automates Notions de base Notes de cours, IR1, 2009 Sylvain Lombardy

Alphabets, mots, langages

UnalphabetAseemnsnetudeniefiblselobmysse´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’alphabetA 1 im(epstomseleocsleusunttaetrmircr´ed’eidaxtnrtselxteteenmpornsoiviro nuscules,majuscules,lettresaccentue´es).L’ensembledesmotsdufranc¸aisestunlangagesurA 1 . ∗ Le motcarichonitneppraat`aAemsottpfaissnu’ncaimsaran¸. 1 2.Less´equencesd’ADNserepre´sententsurunalphabetA 2 ={G, A, T , C}.Unsee´uqneec’dDAN ∗ ∗ est un mot deA, mais un mot deA.entse’utenmenero´capfsrectecoruencs´eq 2 2 3. On peut prendre comme alphabetA 3 iatndsenueisecsreeledmsto’lneesbmcais(plusdufran¸ milliersdemots).Un“mot”estalorsunesuitefinied’e´l´ementsdecetalphabet,c’estdoncce qu’on appelle habituellement une phrase. Les phrases correctes sont un langage surA 3 .

2

Automates non

de´terministes

De´finitionondte(ntomaUnauetsi)ete´nimrAsur un alphabetAtdesmentsel´slee´e´nfipira suivants : – un ensemble fini d’´eatsteon´tQ; – un ensemble finiEdetransitionsntd´´etationansiatdtnue´perafieinrtpa´eedqahcrteu,p, un ´etatd’arrive´eqet une´teqieutteartenant`apaapA; on note une telle transition (p, a, q). – un sousensemble deQstatepaeenspel´ed’´emblinitiaux´etonI; – un sousensemble deQate´stbmes’delelppen´eaterminauxot´enT. Untelautomateestnote´A=hQ, A, E, I, Ti´dnodnauq,isniA.nnenoodate,utomtunaefini successivementsonensembled’´etats,l’alphabetsurlequelilestd´efini,sonensembledetransitions, sonensembled’´etatsinitiauxetsonensembled’e´tatsterminaux.

Repr´esentationgraphiquesteeatomutnaUmmoce´tnese´rpereorient´eungraph´t:e´eteqieu lese´tatssontdesronds(a`l’inte´rieurdesquelsone´critlenomdel’´etat),lestransitionssont repr´esent´eespardesfl`echesquipartentdel’´etatded´epartetpointentsurl’´etatd’arriv´ee,on indiqueaumilieudelafle`chelalettrequienestl’´etiquette.Un´etatinitialestsignale´parune petitefl`echequipointesurl’´etat,une´tatterminalparunepetitefle`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´ d’arriv´ee,onnedessinequ’unefl`echeenindiquantlesdiff´erentse´tiquettes.

1

Cheminsetlangageaccepte´sUncheminitionscons´eutenustidetearsnseetamotua’lsnad cutives,c’est`adireunesuite(p 1 , a 1 , q 1 ),(p 2 , a 2 , q 2 ), ...,(p n , a n , q n ) telle queq i =p i+1 etdta´e’L. d´epartducheminestl’´etatded´epartdelapremi`eretransition,l’´etatd’arrive´educheminestcelui deladernie`retransition.L’´etiquetted’uncheminestlemota 1 a 2 ...a n nenaltsebtoueenonnct´ca e´tiquettesdestransitionsduchemin. Un chemin est´ersiusils’neecocmmnue´adsnnititatis’ilalet.lnUimanttre´etansunvedaarri telcheminestparfoisappele´calcul. Un mot estept´eacctsele´’ldissitnoinemeur´teischunet’slixe’luaotampargeteetituqnaagL.le reconnumoesedblptceactsseetamotmesne’lt.l’aupare´psra’luaotamet Deux automates sonte´viuqnelastsrilonecisnantse’s.gegaanelemmˆle

Exemple :Le motcgtagparlpt´eacceestedssceimotaa’tul’stti´ecauslerimehcniteuqudet re´ussisuivant: c g t a g →p−→p−→q−→r−→s−→s→ Sionregardeattentivementl’automate,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.)tnaleexfieomud reconnu par cet automate est donc l’ensemble des mots sur{a, c, g, t}qui soit contiennent le facteur gtar´efixe,itsoocmmneectnaplrpeta.

D´ecidersiunmotestaccepte´parunautomatetdedermederc´eciogir’Llauqpihtemiec consiste`alirelemotlettreparlettreeta`calculertouslese´tatsquel’onpeutatteindrea`partir d’une´tatinitialenayantluceslettres. Formellement, soitw=w 1 w 2 ...w k un mot (w i est laiteleme`otumedtrt)eA=hQ, A, E, I, Ti unautomate.Onveutd´ecidersiwaratsepeccpe´tA.X i queltatses´ebledueto’pnes’etlemns atteindre en ayant luw 1 w 2 ...w i . Calcul deX k : –X 0 =I; – pouride1`ak X i =∅ pour toutpdansX i−1 pour toutqtel que (p, w i , q) est dansE X i =X i ∪ {q} Le motwacstesi´eptcelumeteesinestX k ∩T6=∅: – pour toutpdansX k sipest dansT retourne VRAI (watccpe´t)ees retourne FAUX 2 Lacomplexite´decetalgorithmeestO(knu`o,)kest la longueur du mot etnest le nombre d’´etatsdel’automate.Eneffet,X i peut contenirnytvaioresitplue´etatntransitions partant depiquet´eeraps´etw i .

´ Etatsutiles,automatese´monde´tetaU´npd’un automateAestutiles’il existe un chemin re´ussipassantparpageutpesuleripprsmemsnafiidoelregnal.Siun´etat’nseptsatuli,eno reconnu. Un automate estdne´e´omseustosissatets´elitutnotuepnO.senteuanuamotome´redn supprimanttousses´etatsinutiles.

3

Automatesd´eterministes

Un automate estrmte´edetnisinititatiul´eunseqa’uli’n’stateetal,psirtout´oup, toute lettrea, il y aau plus unetransition partant depti´eraep´eetqua.

2