Cours sur les automates

Cours sur les automates

Documents
13 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

-1- -2-AutomatesINF 421 Luc MarangetTr`es utilis´es en informatique.◮ V´erifications de circuits (quand ce sont des automates !).◮ Recherche efficace dans le texte (moteur de recherche sur leweb, egrep, ...).◮ V´erification des protocoles de communication.Automates◮ Compilation (reconnaissance des mots du langage compil´e).◮ Biologie (motifs dans les s´equences d’ADN).◮ Mod´elisation des calculs possibles (d´ecidabilit´e), Ici lesautomates (finis) d´efinissent la classe de ce qu’il est possible deLuc.Maranget@inria.fr faire simplement (disons sans ´ecrire dans la m´emoire).http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-3- -4-Exemple simple de DFAAutomate finis d´eterministes (DFA)Id´ealement, on exprime les automates par des dessins :Un DFA est un quintuplet (Σ,Q,δ,q ,F) ou`0a◮ Σ est un alphabet;b◮ Q est un ensemble fini d’´etats; 1ba2 3c◮ δ :Q×Σ→Q est la fonction (partielle) de transition;0b◮ q est l’´etat initial;0b4◮ F⊆Q est un ensemble d’´etats finaux.q\c a b c0 1 4Ici Q ={0,1,2,3,4}, q = 0, F ={3}, et δ =01 2 2 2...-5- -6-Notation compacte Ex´ecution d’un DFA◮ D´emarrer dans l’´etat initial.Transitions ´etiquet´ees par des ensembles de caract`eres.◮ Lire les caract`eres de l’entr´ee en effectuant les transitions (NB :1a-c si blocage, ´echec).ab`0 2 3 ◮ A la fin le mot lu est reconnu si l’´etat courant est final.bb4La transition not´ee a-c compte pour trois.-7- -8-Reconnaissance de la ...

Sujets

Informations

Publié par
Ajouté le 24 septembre 2011
Nombre de lectures 59
Langue Français
Signaler un problème
-1-
-3-
INF 421
Luc Maranget
Automates
Luc.Maranget@inria.fr http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/
Automatenisd´eterministes(DFA) Un DFA est un quintuplet (Σ  Q δ q 0  F )ou` Σ est un alphabet; Q est un ensemble fini d’´tats; e δ : Q × Σ Q est la fonction (partielle) de transition; q 0 est l’´tat initial; e F Q estunensembled´etatsnaux.
2--
-4-
Automates Tre`sutilise´seninformatique. V´ericationsdecircuits(quandcesontdesautomates!). Recherche efficace dans le texte (moteur de recherche sur le web, egrep , . . . ). V´ericationdesprotocolesdecommunication. Compilation(reconnaissancedesmotsdulangagecompile´). Biologie(motifsdansless´equencesdADN). Mode´lisationdescalculspossibles(de´cidabilit´e),Iciles automates(nis)de´nissentlaclassedecequilestpossiblede fairesimplement(disonssans´ecriredanslame´moire).
Exemple simple de DFA Id´ealement,onexprimelesautomatespardesdessins: a b a12b3 c 0bb 4 q \ c a b c } 0 1 4 Ici Q = { 0 1 2 3 4 } , q 0 = 0, F = { 3 , et δ = 1 2 2 2 . . .
-5-
-7-
Notation compacte Transitio´tiet´eespardesensemblesdecaract`er ns e qu es. a 1 a-c b 0 b b 2 4
La transition not´e a-c compte pour trois. e
Exemple (utile ?) de DFA Cetautomateestundigicodecabl´e! 02-9
3
02-902-35-9 024-9 02-911233445 1 0 1 03-9 1 1 2 1
Lautomatereconnaˆıtuncode`aquatrechires,lequel? 1234 .
6--
-8-
Ex´ecutiondunDFA De´marrerdansl´etatinitial. Lirelescaract`eresdelentre´eeneectuantlestransitions(NB: siblocage,e´chec). ` Alanlemotluestreconnusil´etatcourantestnal.
Reconnaissancedelas´equence 1211234 Initialement : 02-9
02-902-35-9 024-9 1 02-9 1 2 3 3 4 4 5 1 0 03-9 1 1 1 2 1
>1 2 1 1 2 3 4  
--90211-uepxerimrecsihr-9-Lecturedesdes01--0-29`irranerereedurctLeouet,re1
02-902-35-9 024-9 02-911233445 1 03-9 0 1 1 1 1 2
1 2>1 1 2 3 4
1 2 1>1 2 3 4
02-902-35-9 024-9 02-911233445 1 03-91 0 1 1 1 2
Lectureduresteducodeetsucc`es 02-9
02-902-35-9 024-9 02-911233445 1 0 03-9 1 1 1 2 1
Lecture de 1 , on ne bouge plus 02-9
02-902-35-9 024-9 02-911233445 1 03-9 1 1 0121
1 2 1 1>2 3 4
-12-
1 2 1 1 2 3 4>
saisnaonecerunsteC3b2c1a0rit:´ecb3bs2a-ca1b4ap0raecbrude-43nal.-1nitialetuq0eseitcnperaecllemrofn´xelede-D13-ioitn´eqcniAalistcelioiteneu´ct:qeeqo,nntoletaarsnecutionSiδ(qc)=elemispmoTtuDnAFdesmmbleensentlceregagnaL-51-rupai)n´e(dnuonalgngareqq}FeLr01a4b2aeconnupapsunelrarstonoceq0|mA.DFΣ{m}b.bcabbb:{aabab-cb3best
Consommation des mots Soit un mot m = a 0 a 1    a n 1 et une lecture a 0 a 1 a n 1 q 0 −→ q 1 −→    q n 1 −→ q n On abr`ege en : m q 0 −→ q n Un mot est reconnu par l’automate si et seulement si q 0 m q n avec q n F
-16-
Impl´ementationpossibledesDFA Une classe Auto . class Auto { State init ; Set < State > end ; . . . } Classedese´tats: class State { /* Identifiant unique (pratique) */ int id ; /*Tableaudestransitions,index´eparchar(dans[0..256[)*/ State [] delta ; . . . } Structure creuse pour les transitions ? Map < Character , State > .
1--7
-19-
Impl´ementationdelareconnaissance Me´thodedesobjets Auto . boolean isAccepted ( String txt ) { State q = init ; for ( int k = 0 ; k < txt . length () ; k ++) { char c = txt . charAt ( k ) ; i f ( q . delta [ c ] == null ) return false ; //Bloqu´e q = q . delta [ c ] ; } return end . contains ( q ) ; }
Exemple simple de NFA b a1b2c 0 a b 4b5 Ousontlesambiguıt´es? ¨ On a 0 a 1 et 0 a 4. On a 1 b 1 et 1 b 2.
3
-18-
-20-
Automates finis non-deterministes (NFA) Un NFA est un quintuplet (Σ  Q δ q 0  F )o`u Σ est un alphabet; Q estunensemblenid´etats; δ : Q × Σ Q est la relation de transition; q 0 estle´tatinitial; F Q estunensemblede´tatsnaux. Changement : Fonction Relation. On peut avoir : c c ′′ q −→ q  q −→ q  et q 6 = q ′′
Reconnaissance par un NFA Lade´nitionnechangepas. { m Σ | q 0 m q F } q Exemple, reconnaissance de abb . b b a1b2ca1b2c 0 a b 3 0 a b 3 4b54b5 >a b b a>b b b b a1b2ca1b2c 0 a b 3 0 a b 3 4b54b5 a b>b a b b>
use-tecasolsrq,-21-Mai-22-bc3b5b2b>01a4ab3cb a b 4abab2b5 a>b b105b2bb 3c01b aba4 bc3 b>aba4ab5b22b5ba1a4a>b 3bbcb3cbb2b5 b 0 a>bb a 4aa4a10 b>)1´equlo0a1b-321-b2b(pede`corpnO.tomereouettriesaesaratusrliiceddee´ˆıtlonnaerecomate´nnanusate´odtnnmtu,dotomuteeat?elIedivuqciahgn´elicat,entplusd,cecch´este1nar>lansap10 b b aes´ei`ers.0atapeb1b11b1erayredenncoıtaˆbaeruQ.bertamerpnarri`ere(backtrca)kE.expmele,ss
-24-
1 b 1 b 2(e´chec)1 b 1 b 1 b b a1b2ca1b2c 0 a b 3 0 a b 3 4b54b5 a b>b a b b> b b a1b2ca1b2c 0 a b 3 0 a b 3 4b54b5 a b>b a>b b
Impl´ementationdelareconnaissanceparNFA Representation de la relation δ : une fonction vers un ensemble. ´ class State { . . . Set < State > [] delta ; . . . } Essaietretourenarri`ere,veutdiretoutessayer. boolean isAccepted ( String txt ) { return run ( txt , 0, init ) ; }
c3b4abab2b53bbc2b5ba1a4b 0 b2b51a4a b 0 a>bpneibtsectEbc3b01b>b a . ..tiar
itions)e(ǫ-transpuel(tΣtsnuestxtrecsianisinavtenatnsee´noitopssrelatuneǫesNFA.ta.s´etenertitno(`u)oǫFq0δQnutse)F0qδQΣtetaifan)lr}terunfalse;//Pastrouuterrtnr/;euorT/´euvhe(cnvmis´erFN-A,eeltumoUǫanninoatetermnd´e62-}}e´vuerocnE-edrtsoneatomutaruoPsuotk(tA//;)t.txarchche{c=arq(;)e}sloctniasnturnend.th()){re))n,1+k,txt(nur(if){c]a[ltdeq.n:atetroS(nf.qeclsqusnteetatles´raktinck´egRrscueme´tatndnoicabu-25-Impl>=(kif){nglet.txtni,txtgqetatS,keanrbooltrinun(Snebtvimeuˆ.reisn
Reconnaissance par un NFA-ǫ Exemple, reconnaissance de ab . 0 −→ 6 a 7 −→ 8 −→ 5 b 4 2 b 2 b  a 3 c a 3 c  1 1 0 b 4 0 b 4    6 5 6 5 a b a b 7 8 7 8   >a b >a b 2 b a 3c  1 0 b 4  6 5 ab 7 8  a>b
-28-
a7  5a2 8c  b4b3  b-A,ǫseFNneltosvuellenappre,oratuedelpmiselpmexE-27.-rtoutcouAtNFoisnpsnotsarsntiessineleNFA-ǫOnd.ett6 10te´eeuqisaanunucn´tasseeontanssps.Sin´eeedtslIaytioiarsnǫ,arnpio`at-escnosqteqtalerneterdecaract`ere,od-risenacsnoosmmontinsDalila´etttonnqeA.qnett