12Licence Info MI BIM

Sandrine Julia

Description

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

• 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

Sujets

• Course
• Automate fini

Informations

• Publié par: profil-nechor-2012
• Nombre de lectures: 93
• Langue: Français

Extrait

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 Theory Jeffrey 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-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

TP  gr.B : J.-V. Millo

TP gr.C : E. Formenti

• • •

• • • • • • • • • •

 mercredi 8h-10h salle PV.312

 mercredi 10h15-12h15 salle PV.312

 mercredi 16h45-18h45 salle 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 dexploitation, é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 linformatique ?

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 dun 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 lesinstancesdun problème unlangagereprésentent lesinstances positivesdu problème unautomate ou autre machine de Turing repré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") : lunique mot à aucune lettre ! longueur dun mot m notée|m| représentation binaire b de n :|b |=#log (n)$+1 nn 2 nombre doccurrences du symbole a» dans m notée|m| a e i caractè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, lensemble 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 cest “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 ={&} * lensemble des mots ) est la fermeture de Kleene de lalphabet ) * 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, lensemble des expressions régulières est dénombrable

Exemple : sur lalphabet binaire  (((0 + &  ) . (1.0) ) . (1 + &  )) * simplifiableen  (0 + &  ) (1 0) (1 + &  ) * *  avec,duplusaumoinsprioritaire,lesopé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 quune 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 q est létat initial 0 F ={q} 1

q 0

1

0

"

A

q 1

Ici, A reconnaît le langage L( A ) décrit par lexpression régulière : * 1 (0  +  " )

Automate fini

Unautomate fini A est la donnée dun quintuplet : ( ) , Q,,, F, q ) 0 tel que :

• • •

• •

! est un alphabet Q est un ensemble fini détats , est un ensemble de règles de transition ,: Q-()'{&} )-Q q est létat initial 0  F est lensemble des états finals (un sous-ensemble de Q)

A accepteà un état de F étiquetéun mot m sil existe un chemin de q 0 par les lettres de m. Lensemble des mots acceptés forme le langage L( A )reconnupar A .

Automates finis déterministes

Un automate fini estdéterministe (A.F.D) ssi,est une fonctionde transition :

,: Q-).Q

! dun état donné, il part au plus une seule flèche étiquetée par une lettre donnée.

! on nautorise pas les & -transitions

Un automate finidéterministeestcompletssi,est une fonction totale sur Q-). ! de chaque état, il part exactement une flèche étiquetée par chacune des lettres de lalphabet ) .

Exemple dA.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

q est létat initial 0 F ={q} 1

q 0

1

0

B

1

q 1

B accepte les mots du langage L( B ) décrit par lexpression régulière : * * 10 1



Non-déterminisme

Dans un automate fininon-déterministe(A.F.N.) il peut y avoir lechoixentre plusieurs chemins lors de la lecture dun mot.

Pour quun mot soitaccepté, il suffit que ses lettres étiquettent un chemin dun état initial à un état final (même sil y en a dautres ne menant pas à un état final, ou bien sarrêtant en cours de route).

Notez quun A.F.D. cest aussi un A.F.N. !

A.F.D.

A.F.N.

Exemple dA.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

q est létat initial 0

F ={q} 1 q 0 C accepte les mots du langage L( C ) décrit * * par 1 0 1 , cest 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 lautomate fini du départ A est déterministe, cest évident

! si lautomate de départ nest pas déterministe, on se propose de construire un automate fini déterministe B  qui intègre tous les choix existant dans lautomate de départ (cf. algorithme de déterminisation)

q 1

! il resterait à prouver formellement que le nouvel automate B accepte exactement les mots acceptés par A .

Exemple de déterminisation

soit lAFN E =( ) , 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 q est létat initial 0 F ={q} 1 on construit  D =(), Q, , q 0 , 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

01

{q ,q}q ,q q 0 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 delanalyse lexicale, le flot de caractères est découpé. Chaque morceau appartient à unlexème.

Les générateurs automatiques danalyseurs lexicaux (Lex, Flex cf.TP1) utilisent un algorithme pour passer directement dune expression régulière à un automate fini déterministe complet.

1.

2.

3.

4.

•

•

•

Algorithme de déterminisation

soit un AFN A =(), Q,,, F), q 0 on construit lautomate B = (), Q,,, F), q 0 Q sera inclus dansP(Q) Clôtures par ,0( &-transitions q 0{q}'{q %Q tels que(q , " ,q)%,} * 0 0 0

pour tout q%Q non encore considéré faire  pour tout1%)faire  q  0{ y%Q /  2x%q tel que (x,1,y)%,}  si q  ≠(alors  q0q'{z%Q /2y%q tel que(y, " ,z)%,} * ,0,'{(q,1,q  ) }  Q0Q'{q  }

F  0  {q tels que q3F4(}

Dénombrabilité

unalphabet)est un ensemble fini de symboles

* lensemble desmots)sur lalphabet) #  (infini) dénombrable

lensemble deslangagessur lalphabet) # 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 ... 1 L0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 ... 2 L0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 ... 3 L0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 ... 4 L1 0 1 0 1 1 0 0 0 0 0 1 0 1 0 ... 5

!  soit L le langage tel que : 1 %Lssi1 5L i i i ! iciL = {1,1,1, ... } 1 2 4 ! il ne figure pas dans notre liste donc elle est incomplète ! pour nimporte quelle liste, on peut exhiber un langage qui ny  appartient pas.



6 lensemble des langages sur ) nest pas dénombrable.