THEORIE DES LANGAGES
ET AUTOMATES
1
INTRODUCTION
• Les automates ont été définis dans les années 40-50.
• Ils sont utilisés dans les beaucoup de domaines comme:
– Compilation des langages
– Reconnaissance de texte
– Conception de protocoles
– Synthèse de programmes
– Vérification de programmes
• Fin des années 50, Chomsky un linguiste a commencé
l’étude des grammaires formelles.
• Les liens entre les grammaires et les automates ont été
étudiés par la suite
2
• Alan Turing a étudié en 1930, avant que n’existe le
premier ordinateur, une question fondamentale en
Informatique:
Existe-t-il une limite à ce qu’on peut calculer?
Sa réponse:
oui, il y a des problèmes qu’on ne peut pas résoudre à
l’aide d’un ordinateur même si on suppose une mémoire
non bornée
3
• Bibliographie
– P. Dehornoy, "Mathématiques d l’Informatique",
Dunod, 2000.
– J. Hopcroft et J. Ullmann, "Introduction to automata
theory, Languages and Computations", Addison-
Wesley, 1979.
• Webographie
– [Link]
– [Link]
4
Plan
• Mots et langages
• Automates à états finis
• Langages réguliers
• Grammaires
• Langages hors contextes et automates à pile
• Machine de Turing
5
Mots et langages
6
Mots
• Un alphabet est un ensemble fini non vide de
lettres (ou symboles)
• Un mot est une suite finie de symboles de
l’alphabet
Exemple: 001110 est un mot sur = {0, 1}
• Un mot w constitué de m symboles est dit de
longueur m. On note |w| = m.
Exemple: |001110|=6
||=0
7
• On note * l’ensemble des mots sur
• i est l’ensemble des mots de longueur i .
On a : *= n n
• NB : On note + l’ensemble * \ {}
8
Opérations
• Concaténation
Soit x * et y * tels que |x| = m et |y| = n.
La concaténation de x et y notée xy est le mot de
longueur m + n dont les m premiers symboles sont ceux
de x et les n derniers ceux de y
• Propriétés de la concaténation
– associativité
– non commutativité
– neutre pour la concaténation
9
• Portions de mots:
Soient w, x, y, z quatre mots tels que : w = xyz
– x est un préfixe de w
– y est une sous-chaîne de w
– z est un suffixe de w
• Exemple
Si le mot considéré est w = 00110
– préfixes : , 0, 00, 001, 0011 et w
– suffixes : , 0, 10, 110, 0110 et w
– sous-chaînes : , 0, 1, 00, 01, 10, 11, 001, 011, 110, 0011,0110 et
w
10
• L'opération miroir est définie de la manière suivante :
– si |w| = 0, alors w = et wR =
– Sinon |w| > 0, w = au (a et u *), wR = uRa.
Si w est tel que wR = w alors w est un palindrome.
11
Langages
• Langage
Un langage (formel) L sur un alphabet est un
sous-ensemble quelconque de * tel que L *
• Exemple
Le langage des nombres est défini sur un alphabet
= {0, 1, . . . , 9}. 02, 00310, 3200 sont alors des
mots sur . On définira le langage des nombres
comme les mots sur qui ne commencent pas par
0. Ainsi, 1233 et 3200 seront des mots du
langages mais pas 00310.
12
• Concaténation de langages
Soient L1 et L2 deux langages, leur concaténation est le
langage
L1L2 = {xy|x L1, y L2}
• Propriétés de la concaténation
– associative
– non commutative
– {} neutre
– absorbant
13
• Clôture de Kleene
– L2 = LL la concaténation de L avec lui-même
– L0 = {}
– clôture de Kleene
L* = i=0 → Li
14
• Autres opérations sur les langages:
– A + B (ou A B) = {w X*| w A ou w B}
– A B = {w X*| w A et w B}
– A - B (ou A \ B) = {w X*| w A et w B}
– LR={uR|uL} (image miroir d’un langage)
15
• Propriétés:
– A = A =
– A {} = {} A = A
– A B AC BC
– A* = i=0 → Ai
– A+ = i=1 → Ai
• Remarque:
On n’ a pas la distributivité de la concaténation par
rapport à l’intersection
16
Théorème d’Arden
A, B langages sur .
Si A alors l’équation L=AL+B admet une
unique solution L= A*B
17
Automates à Etats finis
(AEF)
18
Automates à états finis
• Un Automate à Etats Finis (AEF) est défini par la donnée
de:
– un ensemble fini non vide de symboles
– un ensemble fini d’états Q
– un élément distingué de Q, appelé état initial
– un sous-ensemble F de Q, appelé ensemble des
états finaux
– une fonction partielle : Q→Q, appelée fonction
de transition.
19
20
• représentation concrète:
un ruban, illimité à droite, divisé en cases
une tête de lecture positionnée sur une
seule case à la fois
21
chaque case du ruban contient au plus un symbole, c’est alors
nécessairement un symbole de
celles qui ne contiennent pas de symbole: cases vides, ou occupées
par des blancs (« _ »)
a a c b b
= {a, b, c}
22
Au départ: tête de lecture sur première case non vide à partir
de la gauche
si ruban vide: sur n’importe quelle case
a a c b b
= {a, b, c}
23
Au départ: tête de lecture sur première case non vide à partir
de la gauche dans l’état initial q0
si ruban vide: sur n’importe quelle case
a a c b b
q0
= {a, b, c}
Q = {q0, q1, q2}
q0 initial 24
La tête de lecture se déplace uniquement vers la droite,
d’une seule case à chaque instant du calcul
son mouvement est déterminé par la fonction
a a c b b
q0
= {a, b, c}
Q = {q0, q1, q2}
q0 initial 25
Si (q0, a) = q1 alors la tête de lecture passe à l’état q1 puis
se déplace d ’une case vers la droite
a a c b b
q1
= {a, b, c}
Q = {q0, q1, q2}
q0 initial 26
But: mot accepté si et seulement si
1- mot entièrement « lu »
2- arrêt dans un état final
a a c b b
q2
= {a, b, c}
Q = {q0, q1, q2}
q0 initial q2 final 27
Exemple d’automate
= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Q = {q0, q1, q2}
Qf = {q0}
: 0, 3, 6, 9 1, 4, 7 2, 5, 8
q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1
28
soit à reconnaître le mot 25170462
2 5 1 7 0 4 6 2
q0
: 0, 3, 6, 9 1, 4, 7 2, 5, 8
q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1
29
soit à reconnaître le mot 25170462
2 5 1 7 0 4 6 2
q2
: 0, 3, 6, 9 1, 4, 7 2, 5, 8
q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1
30
soit à reconnaître le mot 25170462
2 5 1 7 0 4 6 2
q1
: 0, 3, 6, 9 1, 4, 7 2, 5, 8
q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1
31
soit à reconnaître le mot 25170462
2 5 1 7 0 4 6 2
q2
: 0, 3, 6, 9 1, 4, 7 2, 5, 8
q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1
32
soit à reconnaître le mot 25170462
2 5 1 7 0 4 6 2
q0
: 0, 3, 6, 9 1, 4, 7 2, 5, 8
q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1
33
soit à reconnaître le mot 25170462
2 5 1 7 0 4 6 2
q0
: 0, 3, 6, 9 1, 4, 7 2, 5, 8
q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1
34
soit à reconnaître le mot 25170462
2 5 1 7 0 4 6 2
q1
: 0, 3, 6, 9 1, 4, 7 2, 5, 8
q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1
35
soit à reconnaître le mot 25170462
2 5 1 7 0 4 6 2
q1
: 0, 3, 6, 9 1, 4, 7 2, 5, 8
q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1
36
soit à reconnaître le mot 25170462
2 5 1 7 0 4 6 2
q0
: 0, 3, 6, 9 1, 4, 7 2, 5, 8
q0 q0 q1 q2
q1 q1 q2 q0
q2 q2 q0 q1
37
soit à reconnaître le mot 25170462
2 5 1 7 0 4 6 2
q0
• L ’automate s’arrête dans un état final,
• il ne reste plus rien à lire
• le mot est donc accepté
38
Représentation par diagramme
• états = sommets
• transitions = arcs étiquetés (par les lettres)
• état initial = sommet de départ
• état final = sommet d’arrivée
• mot = chemin
• mot accepté = chemin allant de l’état initial
à un état final
39
9|6|3|0 7|4|1 9|6|3|0
1
0
8|5|2
8|5|2 8|5|2
7|4|1
7|4|1
9|6|3|0
reconnaître 25170462 40
9|6|3|0 7|4|1 9|6|3|0
1
0
8|5|2
8|5|2 8|5|2
7|4|1
7|4|1
9|6|3|0
reconnaître 25170462 41
9|6|3|0 7|4|1 9|6|3|0
1
0
8|5|2
8|5|2 8|5|2
7|4|1
7|4|1
9|6|3|0
reconnaître 25170462 42
9|6|3|0 7|4|1 9|6|3|0
1
0
8|5|2
8|5|2 8|5|2
7|4|1
7|4|1
9|6|3|0
reconnaître 25170462 43
9|6|3|0 7|4|1 9|6|3|0
1
0
8|5|2
8|5|2 8|5|2
7|4|1
7|4|1
9|6|3|0
reconnaître 25170462 44
9|6|3|0 7|4|1 9|6|3|0
1
0
8|5|2
8|5|2 8|5|2
7|4|1
7|4|1
9|6|3|0
reconnaître 25170462 45
9|6|3|0 7|4|1 9|6|3|0
1
0
8|5|2
8|5|2 8|5|2
7|4|1
7|4|1
9|6|3|0
reconnaître 25170462 46
9|6|3|0 7|4|1 9|6|3|0
1
0
8|5|2
8|5|2 8|5|2
7|4|1
7|4|1
9|6|3|0
reconnaître 25170462 47
9|6|3|0 7|4|1 9|6|3|0
1
0
8|5|2
8|5|2 8|5|2
7|4|1
7|4|1
9|6|3|0
reconnaître 25170462 48
9|6|3|0 7|4|1 9|6|3|0
1
0
8|5|2
8|5|2 8|5|2
7|4|1
7|4|1
9|6|3|0
reconnaître 25170462 49
• Configuration : couple (q, w) avec qQ et w*
(q représente l’état courant et w le mot qui reste à lire
sur le ruban)
• Succession immédiate
(q’,w’) suit immédiatement (q,w):
(q, w) ➔(q’, w’)
si et seulement si
– w = xw’ avec x
– (q, x) = q’
50
w
x w’
a a aa aaaa
q
w’
a a aa aaaa
q’
51
• Succession :
(q,w) ➔* (q’, w’)
si et seulement si
il existe un entier n0 et une suite (q0,w0), (q1,w1),…, (qn,
wn)
telle que:
– (q0, w0) = (q, w)
– (qn, wn) = (q’, w’)
– (q0, w0) ➔ (q1, w1) ➔ … ➔ (qn, wn)
• le cas particulier n = 0, la suite se réduit alors à (q0,w0)
(réflexivité)
52
• Mot accepté par A = <, Q, q0, F, >
w * est accepté par A
si et seulement si
(q0, w) ➔* (q, ) avec qF
• Langage accepté par A : L(A) défini par
L(A) = {w *; w accepté par A}
• ➔ * : fermeture réflexive transitive
• ➔ + fermeture transitive non réflexive
53
• Un automate fini sur un alphabet est complet si pour
chaque symbole x, et chaque état q, il existe au
moins une transition étiquetée x qui quitte q.
• Un automate fini sur un alphabet est non ambigüe si
pour chaque symbole x, et chaque état q, il existe au
plus une transition étiquetée x qui quitte q.
• Un automate est dit déterministe ssi il est complet et
non ambigüe.
54
55
Automates finis non déterministes
• Un AFN (Automate Fini Non déterministe) est un
quintuplet A = (Q,,,q0, F) tel que
– E est l’ensemble fini d’états
– est un vocabulaire (d’entrée) fini
– : Q × → P(Q) est une fonction dite de transition
– q0 Q est l’état initial
– F Q est l’ensemble des états terminaux (ou
d’acceptation)
56
Exemple:
A = ({e0, e1, e2}, {0, 1}, , e0, {e2})
57
• Le prolongement de noté * à Q × * est défini de la
façon suivante :
– qQ, *(q, ) = {q}
– qQ, x , w*,
*(q,wx ) = e*(q,w) (e,x)
• Un mot est accepté par l’automate lorsqu’au moins un
des états de sortie est terminal
58
• Exemple – chaîne d’entrée 00101
– * (e0, ) = {e0}
– * (e0, 0) = (e0,0) = {e0, e1}
– * (e0, 00) = (e0, 0) (e1, 0) = {e0, e1} = {e0, e1}
– * (e0, 001) = (e0, 1) (e1, 1) = {e0} {e2} = {e0, e2}
– * (e0, 0010) = (e0, 0) (e2, 0) = {e0, e1} = {e0, e1}
– * (e0, 00101) = (e0, 1) (e1, 1) = {e0} {e2} = {e0, e2}
59
• Langage reconnu par un automate fini non déterministe:
L(A) = {x V* | *(q0, x) F }
Exemple
L(A) = {w | y V*,w = y01}
60
• Déterminisation d’un AFN:
Soit un AFN N = (QN,, N, e0, FN). On construit un AFD
D = (QD,, D, e0, FD) comme suit:
– QD = P(QN)
– FD = {G QN|G FN }
– G QN (G P(QN)), x , D(G, x) = e G N(e,x)
• Théorème (Equivalence AFN – AFD)
Soit N = (QN,, N, e0, FN) et D = (QD,, D, e0, FD)
construit comme précédemment à partir de N. On a alors
L(D) = L(N)
61
Principe de déterminisation:
considérer des ensembles d’états plutôt que des états
1. Partir de l’état initial
2. Rajouter dans la table de transition tous les nouveaux
états produits avec leurs transitions
3. Recommencer 2 jusqu’à ce qu’il n’y ait plus de nouvel
état
4. Tous les états contenant au moins un terminal
deviennent terminaux
62
63
Exemple
0 1
{e0} {e0,e1} {e0}
{e1} {e2}
{e2}
{e0,e1} {e0,e1} {e0,e2}
0
0
{e0,e2} {e0,e1} {e0}
1 {e0,e1}
{e1,e2} {e2}
e0
{e0,e1,e2} {e0,e1} {e0,e2} 0 1
1 {e0,e2}
64
Minimisation d’AEF
• Principe:
On définit des classes d’équivalence d’états par
raffinements successifs. Chaque classe obtenue forme
une seul même état du nouvel automate
• Hypothèse de l’algorithme:
AFD complet dont tous les états sont accessibles.
65
Minimisation d’AEF
1. Faire deux classes: l’une contenant les états terminaux
et l’autre les états non terminaux
2. S’il existe un symbole a et deux états e1 et e2 d’une
même classe tels que (e1,a) et (e2,a)
n’appartiennent pas à la même classe, alors créer une
nouvelle classe et séparer e1 et e2
3. Recommencer 2 jusqu’à ce qu’il n’y ait plus de classes
à séparer
4. Chaque classe restante forme un état du nouvel
automate
66
Minimisation d’AEF: Exemple
a
a a
1 2 3
b b
4 a 5 a 6
b b a
b
7
a,b
0 0,1 0,1,2 0,1,2,3
1 2 2 2 a
2,3
1
2 3 3 3 a
3 1 1 1 b
5 5 5 5 a
6 6 6 6 4 5,6 a
4 4 4 4 b
b
7 7 7 7 7 67
a,b
68
Automates finis avec -transitions
• Un -AFN est un quintuplet A = (Q,,,q0, F) où:
– Q est l’ensemble fini d’états
– est un vocabulaire (d’entrée) fini
– : Q × {} → P(Q) est une fonction dite de
transition
– q0 Q est l’état initial
– F Q est l’ensemble des états terminaux (ou
d’acceptation)
69
Automates finis avec -transitions
• Exemple
a b c
0 1 2
70
• Configuration : couple (q, w) avec qQ et w* (q
représente l’état courant et w le mot qui reste à lire sur le
ruban)(sans changement)
• Succession immédiate : (modifiée)
(q’,w’) peut suivre immédiatement (q,w):
(q, w) ➔ (q’, w’)
si et seulement si
– w = vw’ avec v {} (si v= alors w = w’)
– (q, v, q’) R
71
Elimination des -transitions
a b c
0 1 2
a,b b,c
a,b,c
72
Elimination des -transitions
• Soit A=(Q,,,q0, F) un -AFND. On construit un automate
-el(A)=(Q,, -el(),q0, -el( F)) qui reconnaît L(A).
• On définit inductivement la relation :
– q q et
– Si q q’ et q’’ (q’, ) alors q q’’
• On définit -el() par:
q’ (q, a) ssi il existe q1 q2 Q tels que q2 (q1, a) et q2 q’
• L’ensemble des états accepteurs -el( F) est défini par:
– -el(F)=F{q0} si q0 q’ F
– -el(F)= F sinon.
73
Déterminisation des -AFN
• -fermeture:
On appelle -fermeture de l’ensemble d’états T= {e1,e2, ….,en},
l’ensemble des états accessibles depuis un état ei de T par des -
transitions
• Principe de déterminisation:
1. Partir de l’ -fermeture de l’état initial
2. Rajouter dans la table de transition toutes les -fermetures des
nouveaux états produits avec leurs transitions
3. Recommencer 2 jusqu’à ce qu’il n’y ait plus de nouveaux états
4. Tous les états contenant au moins un état terminal deviennent
terminaux
74
a b c
0 1 2
75
