Cours sur les automates - INF 421
52 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Cours sur les automates - INF 421

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
52 pages
Français

Description

-1-INF 421 Luc MarangetAutomatesLuc.Maranget@inria.frhttp://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-2-AutomatesTr`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.◮ 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 defaire simplement (disons sans ´ecrire dans la m´emoire).-3-Automate finis d´eterministes (DFA)Un DFA est un quintuplet (Σ,Q,δ,q ,F) ou`0◮ Σ est un alphabet;◮ Q est un ensemble fini d’´etats;◮ δ :Q×Σ→Q est la fonction (partielle) de transition;◮ q est l’´etat initial;0◮ F⊆Q est un ensemble d’´etats finaux.-4-Exemple simple de DFAId´ealement, on exprime les automates par des dessins :ab1ba2 3c0bb4q\c a b c0 1 4Ici Q ={0,1,2,3,4}, q = 0, F ={3}, et δ =01 2 2 2...-5-Notation compacteTransitions ´etiquet´ees par des ensembles de caract`eres.1a-cab0 2 3bb4La transition not´ee a-c compte pour trois.-6-Ex´ecution d’un DFA◮ D´emarrer dans l’´etat initial.◮ Lire les caract`eres de l’entr´ee en effectuant les transitions (NB :si blocage, ´echec).`◮ A la fin le mot lu est reconnu si l’´etat courant est final.-7-Exemple (utile ?) de DFACet ...

Sujets

Informations

Publié par
Nombre de lectures 243
Langue Français

Exrait

-1-
INF
421
Luc
Automates
Maranget
Luc.Maranget@inria.fr http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/
-2-
Automates
Tr`esutilise´seninformatique.
tema).s!catieriV´uq(stiucricedsnotoauestdonesdcan
Recherche efficace dans le texte (moteur de recherche sur le web,egrep . . )., .
ednoitacocotorpsierV´no.ecomlesdcatimuni
gaancogeotsmulsdnassedecoceriannpmlie´.)oCpmoi(nlita
.)NDAdsecneuqe´danslesse(motifsBoiolig
iles),Icdeontisali´eodMit´eabilecids(d´bielopssucslcsla automates(nis)de´nissentlaclassedecequilestpossiblede fairesimplement(disonssanse´criredanslam´emoire).
-3-
Automatenisd´eterministes(DFA)
Un DFA est un quintuplet (Σ Q δ q0 F)uo`
Σ est un alphabet;
Q;stetasembunenid´lentse
δ:Q×ΣQest la fonction (partielle) de transition;
q0nitiai;lestl´etat
FQseut.uxnastate´delbmesnen
-4-
Exemple simple de DFA
Id´ealement,onexprimelesautomatespardesdessins: a
0
a
b
1
4
b c b
b
2
b
q\ca IciQ={01234},q0= 0,F={3}, etδ10= 1 2 . . .
b 4 2
3
c
2
-5-
Notation compacte
Transitions´etiquete´espardesensemblesdecaracte`res.
0
a
b
1
4
a-c b
b
Latransitionnot´eea-ccompte pour trois.
2
b
3
-6-
Ex´ecutiondunDFA
D´marrerdansle´tatinitial. e
Lirelescaracte`resdelentr´eeeneectuantlestransitions siblocage,e´chec).
` Alanlemotluestreconnusil´etatcourantestnal.
(NB
:
-7-
Exemple(utile?)deDFA
Cetautomateestundigicodecable´!
0
02-9
02-35-9
024-9 1 02-912 1 03-91 1 2
02-9
33 1
1 1
4
4
Lautomatereconnˆıtuncodea`quatrechires,lequel?1234. a
5
-8-
Reconnaissancedelas´equence1211234
Initialement :
0
02-9
02-9
1
1
024-9 1 1 03-9 2
02-35-9
2 1
>1 2 1 1 2 3 4
02-9
3 1
3
1
4
4
5
-9-
0
Lecture des deux premiers chiffres
02-9
02-9
1
1
024-9 1 1 03-9 2
02-35-9
2 1
1 2>1 1 2 3 4
02-9
3 1
3
1
4
4
5
-10-
0
Lecture de1reerr`ieranouet,r
02-9
02-9
1
1
024-9 1 1 03-9 2
02-35-9
2 1
1 2 1>1 2 3 4
02-9
3 1
3
1
4
4
5
-11-
0
Lecture de1, on ne bouge plus
02-9
02-9
1
1
024-9 1 1 03-9 2
02-35-9
2 1
1 2 1 1>2 3 4
02-9
3 1
3
1
4
4
5