12Licence Info MI BIM
7
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
7
pages
Français
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Niveau: Supérieur
Automates & Langages Sandrine Julia 2011/12Licence 3 Info/MI/BIM Organisation 1,5h de cours et 2h de TD hebdomadaires sur 12 semaines + 6 TP de 2h Cours : S. Julia lundi 10h30-12h salle P.4.2 TD gr.1 : F. Guingne/E. Formenti mercredi 8h-10h salle M.2.7 TD gr.2 : S. Julia mercredi 10h15-12h15 salle M.2.7 TP gr.A : S. Julia mercredi 8h-10h salle PV.312 TP gr.B : J.-V. Millo mercredi 10h15-12h15 salle PV.312 TP gr.C : E. Formenti mercredi 16h45-18h45 salle PV.312 Bibliographie • Introduction à la calculabilité Wolper, InterEditions, 3e éd., 2006. • Logique et automates Bellot/Sakarovitch, Ellipses, 1998. • Introduction to Automata theory, Languages, and Computation Hopcroft, Ullman, Addison-Wesley, 1979. • A Second Course in Formal Languages and Automata Theory Jeffrey Shallit, Cambridge Univ.Press, 2009. • Introduction to the theory of computation Sipser, PWS publishing company, 1997. • Simulateur JFLAP : à la BU ! Utilisation (plutôt pratique) • spécification des langages de programmation • compilation • recherche de motifs dans un texte dans une base de données sur le web
Voir
Automates & Langages Sandrine Julia 2011/12Licence 3 Info/MI/BIM Organisation 1,5h de cours et 2h de TD hebdomadaires sur 12 semaines + 6 TP de 2h Cours : S. Julia lundi 10h30-12h salle P.4.2 TD gr.1 : F. Guingne/E. Formenti mercredi 8h-10h salle M.2.7 TD gr.2 : S. Julia mercredi 10h15-12h15 salle M.2.7 TP gr.A : S. Julia mercredi 8h-10h salle PV.312 TP gr.B : J.-V. Millo mercredi 10h15-12h15 salle PV.312 TP gr.C : E. Formenti mercredi 16h45-18h45 salle PV.312 Bibliographie • Introduction à la calculabilité Wolper, InterEditions, 3e éd., 2006. • Logique et automates Bellot/Sakarovitch, Ellipses, 1998. • Introduction to Automata theory, Languages, and Computation Hopcroft, Ullman, Addison-Wesley, 1979. • A Second Course in Formal Languages and Automata Theory Jeffrey Shallit, Cambridge Univ.Press, 2009. • Introduction to the theory of computation Sipser, PWS publishing company, 1997. • Simulateur JFLAP : à la BU ! Utilisation (plutôt pratique) • spécification des langages de programmation • compilation • recherche de motifs dans un texte dans une base de données sur le web
- automate fini
- instances positives du problème
- choix existant dans l'automate de départ
- problème du loup, de la chèvre et des choux
- alphabet binaire
Publié par
Langue
Français
Automates & Langages
Sandrine Julia
Licence 3 Info/MI/BIM
•
•
•
•
•
•
Bibliographie
Introduction à la calculabilité Wolper,InterEditions, 3e éd., 2006.
Logique et automates Bellot/Sakarovitch,Ellipses, 1998.
à la BU !
Introduction to Automata theory, Languages, and Computation Hopcroft, Ullman,Addison-Wesley, 1979.
2011/12
A Second Course in Formal Languages and Automata TheoryJeffrey Shallit,Cambridge Univ.Press, 2009.
Introduction to the theory of computation Sipser,PWS publishing company, 1997.
Simulateur JFLAP:http://www.jflap.org/
Organisation
http://deptinfo.unice.fr/~julia/AL
1,5h de cours et 2h de TD hebdomadaires sur 12 semaines + 6 TP de 2h
Cours :S. Julia
lundi 10h30-12hsalle P.4.2
TD gr.1 :F. Guingne/E. Formentimercredi 8h-10h
salle M.2.7
TD gr.2 :S. Juliamercredi 10h15-12h15salle M.2.7
TP gr.A :S. Julia
TPgr.B:J.-V. Millo
TP gr.C :E. Formenti
• • •
• • • • • • • • • •
mercredi 8h-10hsalle PV.312
mercredi 10h15-12h15salle PV.312
mercredi 16h45-18h45salle PV.312
Utilisation(plutôt pratique)
spécification des langages de programmation compilation recherche de motifs dans un texte dans une base de données sur le web systèmes dexploitation, éditeurs compression de textes cryptographie électronique des ordinateurs codage pour la transmission images de synthèse biologie, génétique linguistique( TALN ) sciences cognitives ...
Machines de Turing et plus particulièrement en TP : Reconnaissance de motifs Compression de texte Analyseur lexicaux Automates cellulaires
!
Utilité théorique
!
!
!
!
! ! ! !
Langages rationnels
Où se situent les limites de linformatique ?
C
HC/LX
/HLCX
Spécification de programmes Vérification Complexité
Langages non-contextuels
Expressions régulières Grammaires Automates à pile
Automates finis
1 - Automates finis déterministes
Contenu du cours
Calculabilité :A. Church A. Turing 1903-1995 1912-1954
HLC/X
C
C
!
C
!
LX/HC
• • •
HLCX/
C
Les solutions dun problème vues comme un langage
HLX/C
Problème du loup, de la chèvre et des choux ...
L
-
L
HCX/L
X
X
-
lesmotsreprésentent lesinstancesdun problème unlangagereprésentent lesinstances positivesdu problème unautomateou autre machine de Turingreprésentent le programme.
X/HLC
L
X
L/HCX
X
C
C
L
-
-
C/HLX
C
•
•
•
• • • • • •
• • • • • • • •
Matériel de base
symbole, lettre alphabet!fini mot langage mot vide noté"(ou!ou même"): lunique mot à aucune lettre ! longueur dun mot m notée|m|représentation binaire b de n :|b |=#log (n)$+1 nn 2 nombre doccurrences du symbole a» dans m notée|m| a e icaractère du mot m notém[i] préfixe(propre) suffixe(propre) facteur(propre) sous-mot miroir ordres sur les mots :préfixe, lexicographique, hiérarchique
* Ensemble des langages rationnels
plus petit ensemble contenant les langages finis et clos par union, intersection et étoile définition inductive : (B)(%R {&}%R {a}%R, pour tout a%) (I)si L, M%R alors L'M%R L.M%R * L%R par construction, lensemble des langages rationnels estdénombrable
Exemple :les lexèmes des langages de programmation
(les entiers, les hexadécimaux, les identificateurs, les commentaires ) * On dit aussi “réguliers” car cest “regular” en anglais.
cf.TD1
Opérations sur les langages
Soit L et M deux langages donnés.
•
•
•
•
" " " "
•
•
•
opérations ensemblistes
union, intersection, différences, complémentation, produit cartésien, ...
produit de concaténationde L et M : L.M ={w = uv / u%L, v%M}
puissancede L : 0 (B)L ={&}i i-1 (I)=pour tout i>0, L L. L
* fermeture de Kleene, notée * i L ='L i≥0
+ i on note L ='L i>0 0 même si L=(, L ={&} * lensemble des mots)est la fermeture de Kleene de lalphabet) * L : plus petit langage contenant&, L et fermé par concaténation.
Expressions régulières
formalisme simple pour décrire les langages réguliers
définition inductive :(B)(%ER &%ER a%ER, pour tout a%) (I)si*,+%ER alors (*++)%ER (*.+)%ER * *%ER
par construction, lensemble des expressions régulières est dénombrable
Exemple :sur lalphabet binaire (((0 +&) . (1.0) ) . (1 +&)) * simplifiableen (0 +&) (1 0) (1 +&) * * avec,duplusaumoinsprioritaire,lesopérations:puis.puis+ .
Correspondance entre langage rationnel(ensembles)et expression régulière(formalisme)
(B)(I)
(%ER &%ER a%ER,pour tout a%)
si*,+%ER alors (*++)%ER (*+)%ER * (*)%ER
Expression régulière
Langage (B)L(()=(L(&)={&} L(a)={a}pour tout a%) (I)L(*++)= L(*)'L(+)L(*+)= L(*).L(+)* * L(*)= L(*)
On dit quune expression régulière dénote un langage.
Théorème un langage est rationnel si et seulement si il est dénoté par une expression régulière.
Automate fini A=(), Q,,, q , F) 0
Exemple
)={0,1} Q ={q ,q}0 1 ,={(q ,0,q),(q ,1,q),(q ,",q) } 0 1 0 0 0 1 qest létat initial 0 F ={q} 1
q 0
1
0
"
A
q 1
Ici,Areconnaît le langage L(A) décrit par lexpression régulière : * 1 (0+")
Automate fini
Unautomate finiAest la donnée dun quintuplet : (), Q,,, F, q )0 tel que :
• • •
• •
!est un alphabet Qest un ensemble fini détats ,est un ensemble de règles de transition ,: Q-()'{&} )-Q qest létat initial 0Fest lensemble des états finals (un sous-ensemble de Q)
Aaccepteà un état de F étiquetéun mot m sil existe un chemin de q 0 par les lettres de m. Lensemble des mots acceptés forme le langage L(A)reconnuparA.
Automates finis déterministes
Un automate fini estdéterministe(A.F.D)ssi,est une fonctionde transition :
,: Q-).Q
! dun état donné, il part au plus une seule flèche étiquetée par une lettre donnée.
!on nautorise pas les&-transitions
Un automate finidéterministeestcompletssi,est une fonction totale sur Q-). ! de chaque état, il part exactement une flèche étiquetée par chacune des lettres de lalphabet).
Exemple dA.F.D
B=(), Q,,, F), q 0
)={0,1} Q ={q ,q} 0 1 , ={(q ,0,q),(q ,1,q),(q ,1,q)} 0 1 0 0 1 1
qest létat initial 0 F ={q} 1
q 0
1
0
B
1
q 1
Baccepte les mots du langage L(B) décrit par lexpression régulière : * * 10 1
Non-déterminisme
Dans un automate fininon-déterministe(A.F.N.) il peut y avoir lechoixentre plusieurs chemins lors de la lecture dun mot.
Pour quun mot soitaccepté, il suffit que ses lettres étiquettent un chemin dun état initial à un état final (même sil y en a dautres ne menant pas à un état final, ou bien sarrêtant en cours de route).
Notez quun A.F.D. cest aussi un A.F.N. !
A.F.D.
A.F.N.
Exemple dA.F.D complet
C=(), Q,,, F), q 0
)={0,1}
C
1
0,1
q 0 Q={q ,q ,q} 0 1 2 0 , ={(q ,0,q),(q ,1,q),(q ,0,q),(q ,1,q),(q ,0,q),(q ,1,q)} 0 1 0 0 1 2 1 1 2 2 2 2
qest létat initial 0
F ={q} 1 q 0 Caccepte les mots du langage L(C) décrit * * par 1 0 1 , cest la versioncomplétéede cet automate :
Théorème
Equivalence A.F.N. et A.F.D.
1
0
0
q 2
q 1
1
1
si un langage est reconnu par un automate fini, alors il est également reconnu par un automate fini déterministe.
! si lautomate fini du départAest déterministe, cest évident
! si lautomate de départ nest pas déterministe, on se propose de construire un automate fini déterministeBqui intègre tous les choix existant dans lautomate de départ (cf. algorithme de déterminisation)
q 1
! il resterait à prouver formellement que le nouvel automateBaccepte exactement les mots acceptés parA.
Exemple de déterminisation
soit lAFNE=(), Q,,, F), q 0 )={0,1} Q ={q ,q}0 1 ={ (q ,0,q),(q ,0,q),(q ,&,q),(q ,1,q) }, 0 0 0 1 0 1 1 1 qest létat initial 0 F ={q} 1 on construitD=(), Q, , q0, F),
q ={q q}est létat initial 0 0 1
Q={{q},{q ,q} } 0 0 1 , ={( {q ,q},0,{q ,q}), 0 1 0 1 ({q ,q},1,{q} ), 0 1 1 ({q},1,{q} )1 1 F ={{q q},{q} } 0 1 1
01
{q ,q}q ,q q0 1 0 1 1
{q}q - 1 1
Application
q 0
0
0
q q 0 1
0,&
1
E
D
q 1
q 1
1
1
En début decompilation, lors delanalyse lexicale, le flot de caractères est découpé. Chaque morceau appartient à unlexème.
Les générateurs automatiques danalyseurs lexicaux (Lex, Flex cf.TP1)utilisent un algorithme pour passer directement dune expression régulière à un automate fini déterministe complet.
1.
2.
3.
4.
•
•
•
Algorithme de déterminisation
soit un AFNA=(), Q,,, F), q 0 on construit lautomateB= (), Q,,, F), q 0 Q sera inclus dansP(Q) Clôtures par ,0(&-transitions q 0{q}'{q%Qtels que(q ,",q)%,} * 0 0 0
pour tout q%Qnon encore considéréfaire pour tout1%)faire q0{y%Q /2x%q tel que(x,1,y)%,} si q≠(alors q0q'{z%Q /2y%q tel que(y,",z)%,}* ,0,'{(q,1,q) } Q0Q'{q}
F0{q tels que q3F4(}
Dénombrabilité
unalphabet)est un ensemble fini de symboles
* lensemble desmots)sur lalphabet) # (infini)dénombrable
lensemble deslangagessur lalphabet) # non-dénombrable
( et aussi : toutes les fonctions ne sont pas calculables... )
Preuve de non-dénombrabilité
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1... 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 L 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 ... 0 L1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 ... 1L0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 ... 2L0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 ... 3L0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 ... 4L1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 ... 5
! soit L le langage tel que : 1 %Lssi1 5L i i i !iciL = {1,1,1, ... } 1 2 4 ! il ne figure pas dans notre liste donc elle est incomplète ! pour nimporte quelle liste, on peut exhiber un langage qui ny appartient pas.
6 lensemble des langages sur)nest pas dénombrable.
