Cours sur les automates
13
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
13
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
-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 ...
Voir
-3-
INF 421
Luc Maranget
Automates
Luc.Maranget@inria.fr http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/
Automatefinisd´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’´etatsfinaux.
2--
-4-
Automates Tre`sutilise´seninformatique. ◮ V´erificationsdecircuits(quandcesontdesautomates!). ◮ Recherche efficace dans le texte (moteur de recherche sur le web, egrep , . . . ). ◮ V´erificationdesprotocolesdecommunication. ◮ Compilation(reconnaissancedesmotsdulangagecompile´). ◮ Biologie(motifsdansless´equencesd’ADN). ◮ Mode´lisationdescalculspossibles(de´cidabilit´e),Iciles automates(finis)de´finissentlaclassedecequ’ilestpossiblede 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 . . .
-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
L’automatereconnaˆıtuncode`aquatrechiffres,lequel? 1234 .
6--
-8-
Ex´ecutiond’unDFA ◮ De´marrerdansl’´etatinitial. ◮ Lirelescaract`eresdel’entre´eeneffectuantlestransitions(NB: siblocage,e´chec). ` ◮ Alafinlemotluestreconnusil’´etatcourantestfinal.
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
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>
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 > .
-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 estunensemblefinid’´etats; ◮ δ : Q × Σ → Q est la relation de transition; ◮ q 0 estl’e´tatinitial; ◮ F ⊆ Q estunensembled’e´tatsfinaux. Changement : Fonction → Relation. On peut avoir : c ′ c ′′ q −→ q q −→ q et q ′ 6 = q ′′
Reconnaissance par un NFA Lade´finitionnechangepas. { 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>
-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>bpneibtse’ctEbc3b01b>b a . ..tiar
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-esc’nos′qteqtalerneterdecaract`ere,od-risenacsnoosmmontinsDalila´etttonn→−qeA.′qnett
