Ouvrir le menu
Publier un document
Alternate Text
clear
fr
Ouvrir le menu
Cours sur les automates - INF 421
52 pages
Français

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
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

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

Informations

Publié par
Nombre de lectures 173
Langue Français

Extrait

-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!catierifiV´uq(stiucricedsnotoauestdonesdcan
◮Recherche efficace dans le texte (moteur de recherche sur le web,egrep . . )., .
◮ednoitacocotorpsifierV´no.ecomlesdcatimuni
◮gaancogeotsmulsdnassedecoceriannpmlie´.)oCpmoi(nlita
◮.)NDA’dsecneuqe´danslesse(motifsBoiolig
◮iles),Icdeontisali´eodMit´eabilecids(d´bielopssucslcsla automates(finis)de´finissentlaclassedecequ’ilestpossiblede fairesimplement(disonssanse´criredanslam´emoire).
-3-
Automatefinisd´eterministes(DFA)
Un DFA est un quintuplet (Σ Q δ q0 F)uo`
◮Σ est un alphabet;
◮Q;stetasembunenid’´lefintse
◮δ:Q×Σ→Qest la fonction (partielle) de transition;
◮q0nitiai;lestl’´etat
◮F⊆Qseut.uxnasfitate´’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´ecutiond’unDFA
D´marrerdansl’e´tatinitial. e
Lirelescaracte`resdel’entr´eeeneffectuantlestransitions siblocage,e´chec).
` Alafinlemotluestreconnusil’´etatcourantestfinal.
(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
L’automatereconnˆıtuncodea`quatrechiffres,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
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents
Signaler un problème
playstore
appstore
facebook twitter instagram youtube

YouScribe

Le catalogue

Le service

Les conditions

© 2010-2024 YouScribe
Livre audio en ligne - Développement personnel Livre en ligne Tout le catalogue Tous les Intérêts