Organisation

[Link]

1,5 h de cours + 1,5 h de TD hebdo sur 12 semaines (+ soutien)

Cours : [Link] lundi 11h30-13h amphi Géologie

Automates & Langages TD g.1 : [Link] lundi 15h-16h30

(premier cours en amphi M)
salle M.3.3
TD g.2 : ??? lundi 16h45-18h salle M.3.3

Evaluation :
Sandrine Julia
( 30 * partiel + 20 * contrôle flash + 50 * exam final ) / 100
1h30 20 mn 1h30
oct. nov. déc.

L3 Info, L3 Math-MI 2017/18

Bibliographie Utilisation (plutôt pratique)

• codage de l’information
• Introduction à la calculabilité

• spécification des langages de programmation
Wolper, Dunod, 3e édit°, 2006.
à la BU ! • compilation, analyseurs lexicaux
• Logique et automates 
 • recherche de motifs
Bellot/Sakarovitch, Ellipses, 1998. ✦ dans un texte

• Langages formels, calculabilité et complexité


✦ dans une BD
Carton, Vuibert, 2008. ✦
sur le web
• systèmes d’exploitation, éditeurs
• Introduction to Automata theory, Languages, and Computation

• compression de textes
Hopcroft, Ullman, Addison-Wesley, 1979.
• électronique des ordinateurs
• A Second Course in Formal Languages and Automata Theory 
 • model-checking
Shallit, Cambridge [Link], 2009.
• images de synthèse
• Introduction to the theory of computation
 • cryptographie
Sipser, PWS publishing company, 1997.
 • biologie, génétique


• linguistique ( TALN )


Simulateurs : JFLAP, Visual Automata Simulator, AMoRE, ... • sciences cognitives
• ...
 Les solutions d’un problème 

Utilité théorique ! vues comme un langage
ING
TUR
EE
ANN
Spécification des langages de programmat° 2 : Problème du loup, de la chèvre et des choux ...
201
Modélisation C -

HLCX/ LX/HC HLX/C

Vérification (model-checking)
C - X
Complexité
L X
L

X/HLC L/HCX
Calculabilité : [Link] [Link]

1903-1995 1912-1954
C C C C

Où se situent les limites de l’informatique actuelle ?

HCX/L HLC/X

X X L
• les mots représentent toutes les instances d’un problème
• un langage regroupe les instances positives du problème C - L

• un automate (ou une autre machine) correspond à un programme. /HLCX HC/LX C/HLX

C -

Contenu du cours

✦ Automates finis déterministes

✦ Langages rationnels (ou réguliers)

✦ Expressions régulières


✦ Grammaires régulières
✦ Grammaires non-contextuelles
✦ Automates à pile
✦ Langages non-contextuels
✦ Machines de Turing 1 - Langages rationnels
✦ Automates cellulaires et automates finis déterministes 

 Matériel de base Opérations sur les langages
• symbole, lettre, chiffre, caractère Soit L et M deux langages donnés.
• alphabet : ensemble fini • opérations ensemblistes
mot : concaténation de lettres



• union, intersection, différences, complémentation, produit cartésien, …

• langage : ensemble de mots
• mot vide noté ε : l’unique mot à aucune lettre ! • produit de concaténation de L et M :

• longueur d’un mot m : |m| 
 L . M = { w = u v / u ∈ L, v ∈ M }

longueur représentation binaire de n : |bin(n)| = ⎣log2 (n)⎦+1


• quotient gauche de L par M 



longueur du mot vide : | ε |= 0 L-1 M = { w / il existe u ∈ L et v ∈ M tels que v = u w }

• nombre d’occurrences de la lettre a dans le mot m : |m|a • puissance de L :
appelée
“opération
• le ie caractère du mot m : m[i]
 (B) L0= { ε
}
étoile”
(I) pour tout entier i>0, Li = L . Li-1

• préfixe (propre)
• suffixe (propre) • fermeture de Kleene du langage L : L* = ∪i≥0 Li
• facteur (propre) ✴ on note L+ = ∪i>0 Li
• sous-mot ✴ même si L=∅, L0 = { ε }
• miroir ✴ l’ensemble des mots Σ* est la fermeture de Kleene de l’alphabet Σ
• ordres sur les mots : préfixe, lexicographique, hiérarchique ✴ L* : plus petit langage contenant ε, L et fermé par concaténation.

Exemples Ensemble des langages rationnels*

• plus petit ensemble contenant les langages finis et clos par 

• K = { 0,1,2,3,4 } union, intersection et étoile
définition inductive :
• L = { 5,6,7,8,9 } •
(B) 

• M = { 0,1 }
 ∅ ∈ R

{ε} ∈ R

• K ∪ L = { 0,1,2,3,4,5,6,7,8,9 } {a} ∈ R, pour tout a ∈ Σ
• M.L = { 05,06,07,08,09, 15,16,17,18,19 } (I) 

si L, M ∈ R alors 

• K-1 { 01,2,345,567 } = { 1,ε,45 } L ∪ M ∈ R

• M-1 K = { ε } L . M ∈ R

L* ∈ R
• L-1 K = ∅
• par construction, l’ensemble des langages rationnels est
• (K ∪ L)* \ {ε} 
 dénombrable
ensemble de toutes les représentations décimales 

Exemple : les lexèmes des langages de programmation ( les entiers, les hexadécimaux, les
( y compris celles avec des 0 inutiles en tête).
identificateurs, les commentaires ... )

* on dit aussi réguliers (regular en anglais)

 Correspondance entre langage rationnel (ensemble)
Expressions régulières (ER) et expression régulière (formalisme)
• formalisme simplifié pour décrire les langages réguliers On dit qu’une expression régulière

dénote ou décrit un langage.

• définition inductive :
(B) 

(B) 
 Unix a son propre ∅ ∈ ER
 Langage
∅ ∈ ER
 formalisme pour les exp. ε ∈ ER
 (B)
ε ∈ ER
 régulières que
a ∈ ER, pour tout a ∈ Σ
grep, find ... L(∅) = ∅ 

a ∈ ER, pour tout a ∈ Σ
utilisent (I) 
 L(ε) = {ε}

(I) 

si α, β ∈ ER alors 
 L(a) = {a} pour tout a ∈ Σ
si α, β ∈ ER alors 

(α + β) ∈ ER

( α + β ) ∈ ER
 (I)
(α .β) ∈ ER

( α . β ) ∈ ER
 α* ∈ ER L(α + β) = L(α) ∪ L(β)
α* ∈ ER L( α.β ) = L(α) . L(β)
Expression régulière
• par construction, l’ensemble des expressions régulières est
 L( α* ) = L (α) *
dénombrable

Exemple : sur l’alphabet binaire ( ( ( 0 + ε ) . ( 1 . 0 )* ) . ( 1 + ε ))

simplifiable en ( 0 + ε ) ( 1 0 )* ( 1 + ε )
Théorème un langage est rationnel si et seulement si
avec, du plus au moins prioritaire, les opérations : * puis . puis + il est dénoté par une expression régulière.

Automate fini Exemple

Un automate fini A est la donnée d’un quintuplet :

(Σ, Q, δ, q0, F)
Automate fini
1
A
tel que :
 A = (Σ, Q, δ, q0, F)
q0 ε q1
• Σ est un alphabet
Σ = {0,1}
• Q est un ensemble fini d’états 0
Q = {q0,q1}
• δ est un ensemble de règles de transition (les flèches)

δ = {(q0,0,q1),(q0,1,q0),(q0,ε,q1) }
δ : Q × ( Σ ∪ {ε} ) × Q
q0 est l’état initial
• q0 est l’état initial
F = {q1}
• F est l’ensemble des états finals (un sous-ensemble de Q)

A accepte un mot m s’il existe un chemin de q0 à un état de F

Ici, A reconnaît le langage L(A) décrit par l’expression
étiqueté par les lettres de m. régulière :
L’ensemble des mots acceptés forme le langage L(A) reconnu par A. 1* (0 + ε)
 Automates finis déterministes Exemple d’A.F.D

Un automate fini est déterministe (A.F.D) ssi δ est une

1
B 1
fonction de transition : B = (Σ, Q, δ, q0, F)

 q0
q1
δ : Q × Σ → Q Σ = {0,1}
Q = {q0,q1} 0
✦ d’un état donné, il part au plus une seule flèche étiquetée
par une lettre donnée
 δ = {(q0,0,q1),(q0,1,q0),(q1,1,q1)}

✦ on n’autorise plus les ε-transitions q0 est l’état initial

F = {q1}
Un automate fini déterministe est complet ssi δ est une
fonction définie sur l’ensemble Q × Σ tout entier. B accepte les mots du langage L(B) décrit par l’expression
régulière :
de chaque état, il part exactement une flèche étiquetée par
✦
chacune des lettres de l’alphabet Σ.
1* 0 1*

Exemple d’A.F.D complet Non-déterminisme

C = (Σ, Q, δ, q0, F) 0,1 Dans un automate fini non-déterministe (A.F.N.) il peut y avoir

 C q2
le choix entre plusieurs chemins lors de la lecture d’un mot.
1
Σ = {0,1} 0 1

Q = {q0,q1,q2}
q0 Pour qu’un mot soit accepté, il suffit que ses lettres
q1 étiquettent un chemin de l’état initial à un état final
(même s’il existe d’autres chemins non réussis).
0
δ = {(q0,0,q1),(q0,1,q0),(q1,0,q2),(q1,1,q1),(q2,0,q2),(q2,1,q2)}
Notez qu’un A.F.D.
q0 est l’état initial A.F.N.
c’est aussi un A.F.N. !
F = {q1}
1 B 1

q0 q1
C reconnaît le langage L(C) décrit par 1*0 1*. A.F.D.
C’est la version complétée l’automate B. 0
 Equivalence A.F.N. et A.F.D. Exemple de déterminisation

soit l’AFN E = (Σ, Q, δ, q0, F)

Théorème si un langage est reconnu par un automate fini, 0
E 1
Σ = { 0,1 }
alors il est également reconnu par un automate

Q = { q0,q1 }
fini déterministe. q0 q1
δ = { (q0,0,q0), (q0,0,q1),(q0,ε,q1), (q1,1,q1) }
q0 est l’état initial
0,ε
✦ si l’automate fini du départ A est déterministe, c’est

F = { q1 }
évident
on construit D = (Σ, Q’, δ’, q0’, F’)

✦ si l’automate de départ n’est pas déterministe, 
 q0’= {q0q1} est l’état initial 0 1
on se propose de construire un automate fini déterministe B 

qui intègre tous les choix existant dans l’automate de départ 0
D
Q’= { {q0,q1 } , {q1 }} {q0,q1} q0,q1 q1 1
(cf. algorithme de déterminisation)
δ’ = { ( { q0,q1 },0,{ q0,q1 }),
q 0q 1 q1
✦ il resterait à prouver formellement que le nouvel automate B ({ q0,q1 },1,{ q1 } ), {q1} - q1
accepte exactement les mots acceptés par A. ({ q1 },1,{q1 } )
1
F’ = {{ q0q1} ,{q1 } }

Algorithme de déterminisation Application n

il atio
1. soit un AFN A = (Σ, Q, δ, q0, F)
 U E Comp
cf. au S
6
on construit l’automate B = (Σ, Q’, δ’, q0’, F’) 

Q’ sera inclus dans P(Q) Clôtures par En début de compilation, lors de l’analyse lexicale,
2. δ’ ← ∅

ε-transitions le flot de caractères est découpé. Chaque morceau
q0’ ← {q0} ∪ {q ∈ Q tels que (q0,ε,q) ∈ δ* }
 appartient à un lexème i.e. un petit langage décrit
Q’ ← { q0’ }

par une expression régulière.
3. pour tout q’ ∈ Q’ non encore considéré faire

pour tout σ ∈ Σ faire

q’’← { y ∈ Q / ∃ x ∈ q’ tel que (x,σ,y) ∈ δ } 
 Les générateurs automatiques d’analyseurs lexicaux
si q’’ ≠ ∅ alors 
 (Lex, Flex …) utilisent alors un algorithme
q’’ ← q’’∪ { z ∈ Q / ∃ y ∈ q’’ tel que (y,ε,z ) ∈ δ* } 

δ’ ← δ’ ∪ {( q’,σ,q’’) } 
 pour passer directement d’une expression régulière
Q’ ← Q’ ∪ { q’’ }
à un automate fini déterministe complet.
4. F’ ← {q’ tels que q’ ∩ F ≠ ∅ } 

 Algorithme : E.R. → A.F.D. Exemple : E.R. → A.F.D.

• de gauche à droite, on indice les n lettres de Σ figurant E l’expression régulière : ( a + ε ) ( b a )* ( b + ε)

• on indice les lettres :
dans E par les entiers de 1 à n
( a 1 + ε ) ( b 2 a 3 )* ( b 4 + ε )
• on transforme E en E’ en remplaçant chaque lettre par q (q∉Σ)
• on ajoute q0 au tout début de E’ • on remplace les lettres par le symbole q (hors alphabet) et on met q0
devant :

• pour tout i de 1 à n faire
 q0 ( q1 + ε )( q2 q3 )* ( q4 + ε)
pour tout σ ∈ Σ faire

succ(qi,σ) ← {qj qui suivent qi dans E’après lecture de σ} • initialisations : Q ← {{ q0 }} δ← ∅
• Q ← {q0}, δ←∅ • q0 ,a: Q ← Q ∪ {q1} δ ← δ ∪ { (q0,a,q1) }
q0 ,b: Q ← Q ∪ {{q2,q4}} δ ← δ ∪ { (q0,b,{q2,q4}) }
• pour tout q ∈ Q non encore considéré faire
 • q1 ,a: (rien)
pour tout σ ∈ Σ faire
 q1 ,b: δ ← δ ∪ { (q1,b,{q2,q4})
q’ ← succ(q,σ) 
 • {q2,q4},a: Q ← Q ∪ {q3} δ ← δ ∪ { ({q2,q4},a,q3) }
si q’≠ ∅ alors 
 • {q2,q4},b: (rien)
δ ← (δ ∪ (q,σ, q’))
 • q3 ,a: (rien)
Q ← Q ∪ {q’} q3 ,b: δ ← δ ∪ { (q3,b,{q2,q4}) }
• F ← { états qui contiennent un symbole final de E’ } ➡ A = ( Σ, Q={q0, q1, q3,{q2,q4}}, {q0}, δ, F={q0,q1,q3,{q2,q4}})