Cours sur les automates

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 [e-mail] 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

• informatique

Informations

• Publié par: Nuther
• Nombre de lectures: 60
• Langue: Français

Extrait

-1-

-3-

INF 421

Luc Maranget

Automates

[e-mail] 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 a 1 2 b 3 c 0 b b 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-9 02-35-9 024-9 02-9 1 1 2 3 3 4 4 5 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-9 02-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  

- -902 11- uepxerimrecsihrff -9- Lecturedesdes 0 1--0 -29 `irranerereedurctLeouet,re1

02-9 02-35-9 024-9 02-9 1 1 2 3 3 4 4 5 1 03-9 0 1  1  1  1 2

1 2>1 1 2 3 4

1 2 1>1 2 3 4

02-9 02-35-9 024-9 02-9 1 1 2 3 3 4 4 5 1 03-9 1 0 1  1  1 2

Lectureduresteducodeetsucc`es 02-9

02-9 02-35-9 024-9 02-9 1 1 2 3 3 4 4 5 1 0 03-9  1  1 1 2  1

Lecture de 1 , on ne bouge plus 02-9

02-9 02-35-9 024-9 02-9 1 1 2 3 3 4 4 5 1 03-9 1  1 0 1 2 1

1 2 1 1>2 3 4

-12-

1 2 1 1 2 3 4>

saisnaonecerunste’C 3→− b 2→− c 1→− a 0 rit:’´ec b 3 b s 2 a-c a 1 b 4 ap 0 raecbrude -4 3final. -1 nitialetuq0eseitcnperaec llemrofn´xe’lede - D 13- ioitfin´e q→− c niA ′ alistcel ioitffeneu´ct: q ee ′ qo,nntoletaarsn ecution Siδ(qc)= elemispmoTtu DnAF desmmbleensentl’ ceregagnaL -51- rupai)fin´e(dnuon algngare q∈q}F eLr 0 1 a 4 b 2 a econnupa psunelrarstonoce q 0 ⋆ |→ ∗ m − A.DF ∈Σ{m }b.bcabbb:{aabab -c b 3 b est

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 a 1 b 2 c 0 a  b 4 b 5 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 a 1 b 2 c a 1 b 2 c 0 a  b  3 0  a  b  3 4 b 54 b 5 >a b b a>b b b b a 1 b 2 c a 1 b 2 c 0 a  b  3 0  a  b  3 4 b 54 b 5 a b>b a b b>

’use-tecasolsrq, -21- Mai -22- b c 3 b 5 b 2 b> 0 1 a 4 a b 3 c b  a b  4 a b a b 2 b 5  a>b b 1 0 5 b 2 b b   3 c 0 1 b  a b a 4   b c 3  b>a b a 4 a b 5 b 2 2 b 5 b a 1 a 4 a>b  3 b b c b 3 c b b 2 b 5  b  0  a>bb a  4→− a a 4 a 1 0  b> )1´equlo−0 a ←−1 b ← -32 1 - − b 2→b( pede`corpnO .tome reouettriesaesar a’tusrliicedd e e´ˆıtlonnaerecomat e´nnanusate´odtnnmtu,dotomuteeat ?e lIediv uqciahgn ´elicat,entplusd ,cecch´est’e1nar > lanfisap 1 0  b b a es´ei`ers. 0 a tape →− b 1→− b 1→−1→− b 1 erayredenncoıtaˆbaeruQ.bertamerp narri`ere(backtrca)k E . expmele,ss

-24-

1 ← b − 1 − b → 2(e´chec)1 ← b − 1 ← b − 1 b b a 1 b 2 c a 1 b 2 c 0 a  b  3 0  a  b  3 4 b 54 b 5 a b>b a b b> b b a 1 b 2 c a 1 b 2 c 0 a  b  3 0  a  b  3 4 b 54 b 5 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 ) ; }

c 3 b 4 a b a b 2 b 5 3 b b c 2 b 5 b a 1 a 4 b  0   b 2 b 5 1 a 4 a  b  0  a>b pneibtse’ctE b c 3 b 0 1 b>b a  .   ..tiar

itions)e(ǫ-transpuel(tΣtsnuestx trecsianisinavtenatnsee´noitopss relatune◮ǫes NFA. ta.s´etenertitno ◮( `u)oǫFq 0 δQ nutse)F 0 qδQΣ tetaifan)l r } terunfalse;//Pastrou uterrtnr/;euorT/´euvhe(cnvmis´er FN-A,eel tumoU ǫ anninoatefitermnd´e 62- } } e´v uerocnE - edrtsoneatomut’a ruoPsuot k(tA // ;)t.txarchch e{ c=ar q(;) e}sl octniasnturnend. th()){ re ))n,1+k,txt(nur(if ){c]a[ltdeq.n:atetroS( n→ f .qe− c lsqusnteetatles´ raktinck ´e g Rrscu eme´tatndnoicabu -25- Impl >=(kif ){ nglet.tx tni,txtgqetatS,keanrbooltrinun(S nebtvimeuˆ.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 3 c  1 0 b  4   6 5 a b 7 8   a>b

-28-

a 7     5 a 2   8 c     b 4 b 3     b -A,ǫseFNneltosvuellenappre,oratu edelpmiselpmexE -27 . - rtoutcou A t NF oisnpsnotsarsntiessinele NFA-ǫ Ond.ett 6   1 0 te´eeuqisaanunucn´tassee ontanssps.Sin´eeedtslIaytioiarsnǫ,arnpio `at-esc’ nos ′ qteqtalernet erdecaract`ere,od-risenacsnoosmm ontinsDalila´ett tonn→−qe A . ′ q nett