Théorie des Langages et
Compilation
Leila Jemni Ben Ayed
Leila Jemni Ben Ayed
Maître de Conférences
Ecole Nationale des Sciences de l’Informatique
Janvier 2013
Théorie des langages
Objectif. Ce cours présente la théorie des langages en traitant trois aspects :
Objectif. Ce cours présente la théorie des langages en traitant trois aspects :
L’aspect reconnaissance par les automates finis, les automates à pile et les
machines de turing, L’aspect génération par les grammaires régulières, non
contextuelles et contextuelles, et L’aspect représentation par propriétés
contextuelles et contextuelles, et L’aspect représentation par propriétés
mesurables, définitions récursives et expressions régulières. L’objectif est
d’introduire des connaissances en théorie des langages et des automates afin
de pouvoir les étendre à la description des langages de programmation et leur
analyse syntaxique en vue de leur compilation.
Références. A. Aho, R. Sethi et J. Ullman, Compilateurs Principes,
Techniques et Outils, InterEditions, Paris, 1991.
- P. Walper, Introduction à la Calculabilité, Dunod, Paris, 2001.
-G. Dowek et J. Lévy, Introduction à la théorie des langages de programmation,
Éditions de l'École polytechnique, Paris, 2006.
Théorie des langages
I. Mots et langages
II.
Les automates finis et les langages
réguliers
réguliers
III. Les grammaires
IV. Les grammaires non contextuelles
V.
VI. Les machines de Turing
Les automates à piles
I. Mots et langages
Plan
Langage
Langage
I.1. Vocabulaire et Mot
I.2.
I.2.
I.3. Opérations sur les langages
I.4. Propriétés des langages
I.5. Définition des langages
Le lemme d’Arden
I.6.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
4
I.1. Vocabulaire et mot Exercices
Définition 1. Alphabet: Un alphabet (ou vocabulaire) est
un ensemble fini, non vide de symboles. On le note
généralement X.
Définition 2. Fermeture: Soit X, un alphabet. On note par
Définition 2. Fermeture: Soit X, un alphabet. On note par
X*, l’ensemble de toutes les séquences finies de symboles
de X.
Rq le symbole * est une fonction qui, appliquée à un
ensemble non vide X, donne un autre symbole infini X*. On
dit que X* est la fermeture de X.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
5
I.1. Vocabulaire et mot
Définition 3. Chaine vide: Une chaine vide est une chaine
qui ne contient aucun symbole du vocabulaire ( appelée
aussi mot vide). Une chaine vide est un élément de X*. On
la note : e
la note : e
Définition 4. Longueur d’une chaine: La longueur d’une
chaine finie w est le nombre de symboles qu’elle contient.
On la note |w |.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
6
e
e
e
e
e
e
I.1. Vocabulaire et mot
Définition 5. Mot : Un mot w est une application d’un
segment initial de longueur n vers le vocabulaire:
: [n] fi
X
i est l’image de i dans X; i est le rang de w
i est l’image de i dans X; i est le rang de w
i = a et a ˛ X alors w
i dans X;
i dans X;
i est une occurrence de a dans le
Où w
Où w
si w
mot w
.
Exercice :
Donner les w
1) abba sur le vocabulaire {a, b}
2)
i associés aux mots sivants :
(x1(x2+x1)) sur le vocabulaire {x1, x2, +, , (, )}
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
7
w
w
˛
w
I.1. Vocabulaire et mot
Corrigé:
1) Si le vocabulaire X = {a, b} alors dans le mot abba,
1 = a
2 = b
3 = b
3 = b
4 = a
2) Si le vocabulaire est X = {x1, x2, +, , (, )} alors dans le mot (x1(x2+x1))
1 = (
4 = (
7 = x1
2 = x1
5 = x2
8 = )
3 = *
6 = +
9 = )
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
8
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
I.1. Vocabulaire et mot
Longueur d’un mot : La longueur d’un mot w est le
nombre de symboles qu’il contient , on le note
w |.
|w
Exercice :
Exercice :
Quelle est la longueur des mots abba et e
Vocabulaire {a,b}
Corrigé:
Le mot abba est de longueur 4, |abba| = 4
Le mot e est de longueur 0, | e | = 0
sur le
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
9
w
w
I.1. Vocabulaire et mot
w |x.
w | .
. On le note |w
. On le note |w
w |x
˛ X |w
x˛
Nombre d’occurrences d’un symbole dans un mot :
Le nombre d’occurrences d’un symbole x dans un mot
w est le nombre de fois où ce symbole apparaît dans
ce mot w
ce mot w
|w
w | = S
Exercice :
Quel est le nombre d’occurrences de b dans les mots
abba et e
Corrigé :
|abba|b=2
| e |b=0
Théorie des Langages et Compilation-2013
Leila Jemni Ben Ayed
10
w
w
w
w
w
w
S
S
S
˛
˛
w
w
I.2. Langage
Définition 6. Langage :
On définit un langage sur un alphabet X comme un sous
ensemble de X*
Exemple:
Exemple:
• Si le vocabulaire est X = {0, 1, 2, 3, …9}
L = { représentations décimales des nombres entiers
naturels}
L = |N
• Si le vocabulaire est X = {x1, x2, +, *, (, )}
L = {expressions arithmétiques parenthésées}
manipulant x1, x2, + et *
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
11
I.2. Langage
• Si X est la vocabulaire du langage de programmation C
X = {main, (, ), #, Include, <, >, ., ;, id, nb, …….}
L= {programmes C corrects syntaxiquement}
• Si X est le vocabulaire de la logique des propositions
X ={p, (, ), fi
L = {formules bien formées de la logique des
} où p désigne une proposition
, (cid:216)
, (cid:217)
propositions}
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
12
fi
fi
fi
(cid:217)
(cid:217)
(cid:217)
(cid:216)
(cid:216)
(cid:216)
I.3. Opérations sur les langages
Concaténation de deux mots:
Si u et v deux mots / |u| = n et |v| = m alors:
u.v = w
/
i ˛
i = ui
= v "
n+j = vj
[n] et
[m]
[m]
j ˛
j ˛
Le mot vide e est un élément neutre de la
concaténation
u. e = e .u = u
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
13
w
"
w
w
"
I.3. Opérations sur les langages
Soient A et B deux langages alors on a les opérations suivantes:
Intersection
Union
Complémentation
Concaténation
A˙ B = {w / w
A+B = {w / w
A-B = {w / w
A et w
A ou w
A et w
B}
B}
B}
A.B = {w / $
A.B = {w / $
$ u ˛ A et $
$ u ˛ A et $
$ v ˛ B et w = u.v}
$ v ˛ B et w = u.v}
Propriétés
Soient A, B, C des langages, on a
A.(B+C) = A.B + A.C
(A+B).C = A.C+B.C
A ˝ B ⇒
AC ˝ BC
CA ˝
CB
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
14
˛
˛
˛
˛
˛
ˇ
$
Advertisement
$
$
$
$
$
$
$
I.3. Opérations sur les langages
Notation:
ak = aaaaaaaaa……
<----------------->
k fois
k fois
a2 = aa
a0 = e
a* = {ai / i ‡ 0} = {a0, a1, a2, ….ai, …}
a+ = {ai / i >0} = {a1, a2, …., ai, …}
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
15
I.3. Opérations sur les langages
L’opération *
A* = ¨ Ai avec A0 = {e }
i‡ 0
A1 = A
Ai = A.Ai-1 "
Ai = A.Ai-1 "
i‡ 1
i‡ 1
L’opération +
A+ = ¨ Ai
i‡ 1
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
16
I.3. Opérations sur les langages
Exercice :
Calculer A* pour chacun des ensembles A suivants:
1) A = {a}
2)
Corrigé :
1) Si A = {a} alors A = {a} = a*
X* / |w | = 2k+1 / k ‡ 0}
A = {w
Car A* = A0 + A1 + A2 +… Ai +…
Car A* = A0 + A1 + A2 +… Ai +…
A0 = {e } = {a0}
A1 = AA0 = {a} {e } = {a} = {a1}
A2 = AA1 = {a}{a} = {aa} = {a2}
Ai = {ai}
Ai+1 = A Ai = {a}{ai} = {ai+1}
….
A = {e , a, aa, aaa, …} = {a0, a1, a2, a3, …} = a
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
17
˛
I.3. Opérations sur les langages
X* / |w | = 2k+1 / k ‡ 0}
2) Si A = {w
A = X
Car A* = A0 + A1 + A2 +… Ai +…
A0 = {e }
A1 = AA0 = A{e } = {w
A2 = AA1
A2 = AA1
‡ 0}
X* / |w |= 2k+1/ k ‡ 0}
X* / |w |= 2k+1/ k ‡ 0}
w | = 2k+1 / k ‡
X* / |w
X* / |w | = 2k+1/ k‡ 0} {w
X* / |w | = 2k+1/ k‡ 0} {w
X* / |w | = 2k+2/ k‡ 0}
X* / |w | = 2k / k>0}
X* / |w | = 2k / k>0} = {w
X* / |w
w | = 2k/
= {w
= {w
= {w
= {w
A0 + A2 = {e } + {w
‡ 0}
k‡
A0 + A1 + A2 = X*
Donc A = X
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
18
˛
˛
w
w
‡
‡
˛
˛
˛
˛
˛
˛
˛
˛
w
w
‡
‡
I.4. Propriétés des langages
Exercice :
Calculer A.f et A.{e }
Montrer qu’on n’a pas A.(B+C) = A.B + A.C
Corrigé:
1- A.f = f
1- A.f = f
2- A.{e } = {e }.A= A
5- On n’a pas A.(B˙ C) = A.B ˙ A.C
.A = f
.A = f
Contre exemple : A = {e , x}, B = {xyzt}, C = {yzt}
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
19
I.4. Propriétés des langages
Contre exemple : A = {e , x}, B = {xy}, C = {y}
Car A.(B˙ C) „ A.B ˙ A.C
En effet (B˙ C) = f donc A. (B˙ C) = f
Par contre A.B = {xy, xxy} et A.C = {y, xy} donc A.B ˙ A.C = {xy}
6- On n’a pas A+ = A* - {e
6- On n’a pas A+ = A* - {e
Pour A = {e , a}
A+ = A1 + A2 + … = {e
A* = A0 + A1 + A2 + … = {ai / i ‡ 0}
A* - {e } = {ai / i > 0} „ A+ car A ˚
A+ = A* - {e
e } est vraie lorsque A ne contient pas e
e } par contre on A* =A+ + {e }
e } par contre on A* =A+ + {e }
e , a} + {e , a, aa} + …
{e }
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
20
e
e
e
e
e
e
e
e
I.5. Définition de langages (propriété
mesurable ou définition récursive)
• Définition par propriété mesurable
– L est l’ensemble des mots sur {a, b} de longueur paire
w | = 2k, K ‡ 0}
{a, b}*/ |w
L = { w
– L est l’ensemble des mots sur {a, b} ayant un nombre
– L est l’ensemble des mots sur {a, b} ayant un nombre
impaire de b
L = { w
{a, b}*/ |w
w |b = 2k+1, K ‡ 0}
– L est l’ensemble des mots sur {a, b} où tous les a précèdent
les b et sont de même nombre
L = { anbn, n ‡ 0}
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
21
˛
w
w
˛
w
w
I.5. Définition de langages (propriétés
mesurables ou récursive)
• Définition récursive
– L est l’ensemble des mots sur {a, b} où tous les a précèdent
les b et sont de même nombre
La définition par propriété mesurable est la suivante :
La définition par propriété mesurable est la suivante :
L = { anbn, n ‡ 0}
La définition récursive du même langage est :
L = { w
{a, b}*/ w
w = e
e ou w
w = aw
1b et w
1
L}
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
22
‡
w
w
w
˛
˛
˛
˛
w
w
e
e
w
w
w
w
w
w
w
w
˛
˛
˛
˛
I.5. Définition de langages (propriétés
mesurables ou récursive)
• Définition récursive
– L est l’ensemble des mots palindromes sur le
vocabulaire {a, b}, de longueur paire.
L = { w
w = bw
{a, b}*/ w
1b et w
1
w = aa ou w
L}
w = bb ou w
w = aw
1a ou
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
23
w
w
w
˛
˛
˛
˛
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
˛
˛
˛
˛
I.5. Définition de langages (propriétés
mesurables ou récursive)
• Définition récursive
– L est l’ensemble des mots palindromes sur le
vocabulaire {a, b}, de longueur impaire.
L = { w
w = bw
{a, b}*/ w
1b et w
1
w = a ou w
L}
w = b ou w
w = aw
1a ou
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
24
w
w
w
˛
˛
˛
˛
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
˛
˛
˛
˛
I.5. Définition de langages (propriétés
mesurables ou récursive)
• Définition récursive
– L est l’ensemble des mots palindromes sur le
vocabulaire {a, b}.
L = { w
ou w
{a, b}*/ w
1a ou w
w = a ou w
w = bw
w = b ou w
1b et w
1
w = aa ou w
L}
w = aw
Advertisement
w = bb
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
25
w
w
w
˛
˛
˛
˛
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
w
˛
˛
˛
˛
I.6. Le lemme d’Arden
Pour deux langages A et B d’un vocabulaire X*,
Les équations L= AL+B et L = LA+B admettent
Les équations L= AL+B et L = LA+B admettent
respectivement comme solution minimale A*B
et BA*. Cette solution est unique si e
ˇ A.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
26
II. Les automates finis et les
langages réguliers
Plan
II.1. Les automates finis déterministes
II.1. Les automates finis déterministes
II.2. Langage accepté par un automate fini
II.3. Rendre déterministe un automate fini non
déterministe
II.4. Les langages réguliers LR
II.5. Minimisation d’un automate fini déterministe
II.6. Expressions régulières et automates finis
II.7. Limites des automates finis
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
27
II.1. Les automates finis déterministes
Définition7. Automate fini
Un automate fini consiste en un quintuple de la
forme (Q, X, d , q0, F) avec
Q est un ensemble fini d’états
Q est un ensemble fini d’états
X est un alphabet
d est une fonction de transition
d : Q x X fi
q0 est l’état initial
F est l’ensemble des états finaux F ˝ Q
(Q) (l’ensemble de tous les sous ensembles de Q)
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
28
d
d
d
d
d
d
R
II.1. Les automates finis déterministes
Exemple d’un automate fini
OFF
Presser
Presser
Q = {OFF, ON}
X = {presser}
q0 = OFF
F = {ON}
d (OFF, presser) = {ON}
d (ON, presser) = {OFF}
ON
Cet automate reconnaît les
séquences de presser qui
nous mènent toujours à
l’état final souhaité ON
(lampe allumée)
(lampe allumée)
En partant d’un état où la
lampe est éteinte (OFF)
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
29
d
d
d
d
d
d
II.1. Les automates finis déterministes
Exemple d’un automate fini
OFF
Presser
Presser
Presser
ON
La séquence:
presser presser presser est acceptée
Par ce que
•en partant de l’état off, avec un presser on passe à l’état ON
•En lisant le deuxième presser à partir de l’état ON, on revient à l’état OFF
•Le dernier presser lu nous mène de l’état OFF à l’état ON
Donc à la fin de la lecture des trois presser, trois transitions sont effectuées et la
dernière nous mène à l’état ON donc la séquence est acceptée.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
30
II.1. Les automates finis déterministes
Exemple d’un automate fini
OFF
OFF
OFF
presser
presser
Presser
Presser
Presser
presser
presser
presser presser presser
presser
presser
presser
ONON
ONON
ON
Le mot est lu et l’état est final
donc le mot est accepté
donc le mot est accepté
La séquence:
presser presser presser est acceptée
Par ce que
•en partant de l’état off, avec un presser on passe à l’état ON
•En lisant le deuxième presser à partir de l’état ON, on revient à l’état OFF
•Le dernier presser lu nous mène de l’état OFF à l’état ON
Donc à la fin de la lecture des trois presser, trois transitions sont effectuées et la
dernière nous mène à l’état ON donc la séquence est acceptée.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
31
II.1. Les automates finis déterministes
Exemple d’un automate fini
OFF
Presser
Presser
ON
La séquence:
presser presser n’est pas acceptée par l’automate
Par ce que
•en partant de l’état off, avec un presser on passe à l’état ON
•En lisant le deuxième presser à partir de l’état ON, on revient à l’état OFF
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
32
II.1. Les automates finis déterministes
Exemple d’un automate fini
A
OFF
Presser
Presser
ON
Le langage accepté par cet automate est l’ensemble des séquences de presser qui,
partant de l’état initial OFF, après la lecture de tous les symboles de la séquence,
on se trouve à l’état ON.
Ce langage (le langage accepté par l’automate A, L(A)) est l’ensemble des
séquences de presser de longueur impaire.
‡ 0}
L(A) = {w
w | = 2k + 1, k ‡
{presser}*/ | w
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
33
w
w
w
˛
˛
˛
˛
w
w
‡
‡
II.1. Les automates finis déterministes
Exemple d’un automate fini qui accepte
{w
w | = 2k, k ‡
{a}*/ |w
‡ 0}
A
P
P
a
a
(aa)*
I
I
L’état initial devient un état final puisque le mot e est accepté (pour k = 0).
En étant à l’état initial de l’automate, on peut ne rien lire (c-a-d lire 0 symboles
donc lire e ) et on est déjà à un état final.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
34
w
w
w
˛
˛
˛
˛
w
w
‡
‡
II.1. Les automates finis déterministes
Exercices :
1) Construire un automate fini qui accepte le langage suivant:
{w
w | = 2k, k > 0}
{a}*/ |w
A
q0
a
q1
aa(aa)*
q2
a
a
Le plus petit mot accepté est aa (On atteint l’état final après la lecture de aa).
Après il faudra continuer à avoir un nombre paire de a. Donc quand on se trouve à
l’état d’acceptation ou l’état final, il faudra continuer à lire des séquences de 2a
pour revenir à l’état final.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
35
w
w
w
˛
˛
˛
˛
w
w
II.1. Les automates finis déterministes
{w
A
{a}*/ |w
w | = 2k, k > 0} (autre solution)
q0
a
q1
a
q2
a
a
a
q3
Le plus petit mot accepté est aa (On atteint l’état final après la lecture de aa).
Après il faudra continuer à avoir un nombre paire de a. Donc quand on se trouve à
l’état d’acceptation ou l’état final, il faudra continuer à lire des séquences de 2a
pour revenir à l’état final.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
36
w
w
w
˛
˛
˛
˛
w
w
II.1. Les automates finis déterministes
2) Construire un automate fini qui accepte le langage suivant:
{a,b}*/ |w
w |a = 3k+2, k ‡
‡ 0}
A
b
q0
q0
a
b
a
q2
q2
q1
q1
a
b
babab(ababab)*
Le plus petit mot accepté est aa (On atteint l’état final après la lecture de aa).
Après il faudra continuer à avoir un nombre paire de a. Donc quand on se trouve à
l’état d’acceptation ou l’état final, il faudra continuer à lire des séquences de 2a
pour revenir à l’état final. Les b on peut les lire à n’importe quel état et on reste
au même état puisqu’ils n’engendrent pas une transitions contrairement à un a lu
qui nous fait passer de q0 à q1 ou de q1 à q2 ou de q2 à q0 par ce qu’il faut les
comptabiliser.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
37
w
w
‡
‡
Advertisement
II.1. Les automates finis déterministes
3) Construire un automate fini qui accepte le langage suivant:
{w
w | = 3k+1, k ‡
{a}*/ |w
‡ 0}
a(aaa)*
A
q0
a
q1
a
q2
q3
a
a
a
Le plus petit mot accepté est a (On atteint l’état final après la lecture de a). Après il
faudra continuer à avoir un nombre multiple de 3a. Donc quand on se trouve à
l’état d’acceptation ou l’état final, il faudra continuer à lire des séquences de 3a
pour revenir à l’état final.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
38
w
w
w
˛
˛
˛
˛
w
w
‡
‡
II.1. Les automates finis déterministes
{w
A
{a}*/ |w
w | = 3k+1, k ‡
‡ 0} (autre solution)
a(aaa)*
q0
a
a
a
q1
a
q2
Le plus petit mot accepté est a (On atteint l’état final après la lecture de a). Après il
faudra continuer à avoir un nombre multiple de 3a. Donc quand on se trouve à
l’état d’acceptation ou l’état final, il faudra continuer à lire des séquences de 3a
pour revenir à l’état final.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
39
w
w
w
˛
˛
˛
˛
w
w
‡
‡
II.1. Les automates finis déterministes
4) Construire un automate fini qui accepte le langage suivant:
{w
{a, b, c}*/ |w
‡ 0}
w |a = 3k+1, k ‡
A
b, c
q0
a
a
a
b, c
a
q1
q2
b, c
(b+c)a(b+c)(a(b+c)a(b+c)a(b+c))
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
40
w
w
w
˛
˛
˛
˛
w
w
‡
‡
II.1. Les automates finis déterministes
5) Construire un automate fini qui accepte l’ensemble des mots
sur {a, b, c} ayant aba comme facteur (ou sous chaine)
b
q2
a
q3
a, b, c
b, c
q0
a
c
a
q1
b, c
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
41
II.1. Les automates finis déterministes
6) Construire un automate fini qui accepte l’ensemble des
représentations décimales des nombres entiers ayant le chiffre 1
dans les dizaines (Exemple: 12316, 13, 210)
0,1,2,3,4,5,6,7,8,9
1
q0
0,1,2,3,4,5,6,7,8,9
q1
q2
c*1c
(0+1+2+…+9)*1(0+1+2+…9)
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
42
II.1. Les automates finis déterministes
7) Construire un automate fini qui accepte l’ensemble des
représentations décimales des nombres entiers différents de
Zéro
0,1,2,3,4,5,6,7,8,9
0
q0
1,2,3,4,5,6,7,8,9
q1
0(1+2+…9)(0+1+2+…+9)
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
43
II.1. Les automates finis déterministes
Définition 8. Automate fini complet
Définition 8. Automate fini complet
Un automate fini est dit complet sur un vocabulaire X ssi
pour chaque état q et chaque symbole s, il existe au moins
une transition qui quitte q avec le symbole s.
Définition 9. Automate fini non ambigu
Un automate fini est dit non ambigu sur un vocabulaire X
Un automate fini est dit non ambigu sur un vocabulaire X
ssi pour chaque état q et chaque symbole s, il existe au plus
une transition qui quitte q avec le symbole s.
Définition 10. Automate fini déterministe
Un automate fini est dit déterministe sur un vocabulaire X
ssi il est complet et non ambigu (pour chaque état q et
chaque symbole s, il existe une et une seule transition qui
quitte q avec le symbole s).
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
44
II.1. Les automates finis déterministes
a
q0
a,b
q1
Non complet sur {a, b} car
d (q0, b) = f
d (q0, b) = f
L(A) = a(a+b)*
a,b
q0
a
b
a
q1
Ambigu sur {a, b} car
Ambigu sur {a, b} car
d (q0, a) = {q0, q1}
L(A) = ((a+b)a+)
b
q0
a
b
a
q1
L(A) = (ba+)
Automate fini déterministe sur {a, b} car il est complet et non ambigu:
d (q0, a) = {q1} d (q0, b) = {q0} d (q1, a) = {q1} d (q1, b) = {q0}
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
45
II.2. Langage accepté par un automate
fini
Définition 11. Configuration
Une configuration est un couple
(q, w
)
où q est l’état courant et w est le reste du mot à lire.
Pour l’automate suivant, des configurations possibles sont:
Pour l’automate suivant, des configurations possibles sont:
A
b
q0
q0
a
b
a
b
q2
q2
q1
q1
a
(q0, aa) (q1, a) (q2, e )
(q0, bba) (q0, ba) (q0, a) (q1, e )
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
46
II.2. Langage accepté par un automate
fini
Définition 12. Configuration successeur
Une configuration (p, y) est successeur d’une
configuration (q, x) qu’on note:
(q, x) |-- (p, y)
(q, x) |-- (p, y)
ssi
$ a / x = a y et d (q, a) = p
p
q
a
a
y
x
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
47
II.2. Langage accepté par un automate
fini
Pour l’automate suivant, des configurations possibles
sont:
A
A
b
q0
q0
a
q1
q1
a
b
a
b
q2
q2
(q0, aa) |-- (q1, a) |-- (q2, e )
(q0, bba) |-- (q0, ba) |-- (q0, a) |-- (q1, e )
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
48
II.2. Langage accepté par un automate
fini
Définition 13. Configuration kème successeur
Une configuration (p, y) est kème successeur d’une
configuration (q, x) qu’on note:
k
(q, x) |-- (p, y) ssi (q, x) |-- (q1, x1) |-- (q2, x2) |--…(qk, xk) = (p, y)
(q, x) |-- (p, y) ssi (q, x) |-- (q1, x1) |-- (q2, x2) |--…(qk, xk) = (p, y)
*
k
(q, x) |-- (p, y) ssi $ k ‡ 0 / (q, x) |-- (p, y)
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
49
II.2. Langage accepté par un automate
fini
Pour l’automate suivant, nous avons :
b
A
q0
q0
a
q1
q1
a
a
b
a
b
q2
q2
*
k
(q0, aa) |-- (q2, e ) puisque: $ k ‡ 0 / (q0, aa) |-- (q2, e )
(q0, aa) |-- (q1, a) |-- (q2, e ) (k = 2)
3
(q0, bba) |-- (q1, e )
En effet, (q0, bba) |-- (q0, ba) |-- (q0, a) |-- (q1, e )
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
50
II.2. Langage accepté par un automate
fini
Définition 14. Langage reconnu par un
automate fini
Soit A = (Q, X, d , q0, F) un automate fini.
Le langage accepté (ou reconnu par A)
Le langage accepté (ou reconnu par A)
est noté L(A) /
est noté L(A) /
L(A) = {w / (q0, w
*
) |-- (qf, e ) , qf ˛
F}
w est accepté par A ssi w
L(A)
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
51
˛
II.2. Langage accepté par un automate
fini
Exercice : Soit l’automate fini A suivant :
b
A
q0
q0
a
Advertisement
q1
q1
a
a
b
a
b
q2
q2
Montrer que aa ˛
L(A) et que bba ˇ
L(A)
Corrigé:
aa ˛
L(A) par ce que : (q0, aa) |-- (q2, e ) puisque:
*
(q0, aa) |-- (q1, a) |-- (q2, e ) (k = 2)
bba ˇ
L(A) par ce que : (cid:216)
k / (q0, bba) |-- (q2, e )
k
En effet, (q0, bba) |-- (q0, ba) |-- (q0, a) |-- (q1, e )
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
52
$
II.2. Langage accepté par un automate
fini
Exercice: Considérons l’automate A suivant :
Quel est le langage reconnu par A
1)
b
A
q0
q0
a
q1
q1
a
a
b
a
b
q2
q2
Est-ce que le mot e est accepté par A Pour l’automate suivant, nous avons :
2)
Corrigé:
1) L(A) = {w
2) e
{a, b}*/ |w
w | = 3k+2, k ‡
F
L(A) par ce que : q0 ˛
‡ 0} + {e
e }
(q0, e ) est une configuration initiale et finale.
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
53
w
w
w
˛
˛
˛
˛
w
w
‡
‡
e
e
˛
II.2. Langage accepté par un automate
fini (Lemme d’Arden)
Soit A un automate fini sur un vocabulaire X
Avec x ˛
˛ X
A
qi
x
qj
On dénote par Li, le langage reconnu par l’automate A en considérant que qi
j
Lj (cid:219)
est l’état initial. Ainsi, L0 est le langage reconnu par A
i = x w
j en conséquence Li = xLj
Li / w
Si qi est un état final alors Li = x Lj + {e
et final alors le langage Li contient le mot e
i
e } par ce que si qi est un état initial
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
54
˛
˛
w
˛
˛
˛
˛
(cid:219)
(cid:219)
(cid:219)
$
$
$
$
w
˛
˛
˛
˛
e
e
e
e
e
II.2. Langage accepté par un automate
fini (Lemme d’arden)
Exercice : Soit A un automate fini sur un vocabulaire X= {a,b}, Chercher le
langage L0 reconnu par l’automate A
A
a
q0
a
q2
q1
a
Corrigé :
L0 = {a} L1(1)
L2 = {a} L0 + {e }
(1)
(4) + (3) ⇒ L0 = {aa} L2 = {aa}({a}L0 + {e }) ⇒ L0 = {aaa}L0 + {aa}
+ (2) ⇒ L0 = {a}{a}L2 = {aa}L2
L1 = {a} L2(2)
(3)
(4)
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
55
⇒ L0 = {aaa}{aa} = (aaa)aa
D’après le lemme d’Arden
II.2. Langage accepté par un automate
fini (Lemme d’arden)
Exercice :
1) Construire un automate qui accepte le langage ab
2) Vérifier que l’automate construit reconnaît le langage ab
Corrigé :
1)
b
a
A
q0
b
b
q1
2) Calculons L0
L0 = {a} L0 + {b}L1 + {e }
L1 = {b} L1 + [e ]
(2) ⇒ L1 = {b}{e } d’après le lemme d’Arden ⇒ L1 = b
(1)
⇒ L0 = {a}L0 + {b} b* + {e }
(1)
(2)
+ (3)
(3)
⇒ L0 = {a}L0 + b+ + {e }
⇒ L0 = {a}L0 + b car b++{e } = b
⇒ L0 = {a}b = abd’après le lemme d’Arden
L(A) = L0 = ab donc l’automate A reconnaît le langage ab
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
56
II.2. Langage accepté par un automate
fini (Lemme d’arden)
Exercice :
1)
2)
Construire une automate qui accepte le langage (a+b)*
Vérifier que l’automate construit reconnaît le langage (a+b)* (L0 est le langage
accepté par l’automate puisque c’est le langage où q0 est l’état initial)
Corrigé:
1)
A
A
a,b
q0
2)
L0 = {a} L0 + {b}L0 + {e }
(1) ⇒ L0 = {a,b} L0 + {e }
(1)
⇒ L0 = {a,b}*{e } d’après le lemme d’Arden
⇒ L0 = {a,b} = (a+b)
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
57
II.3. Rendre déterministe un automate
fini non déterministe
II.3.1. Automate fini non complet
Si l’automate fini est non déterministe par ce qu’il est non complet, alors
pour le rendre déterministe, il suffit d’ajouter un état puit et ajouter
toutes les transitions manquantes vers cet état.
a,b
a,b
a
a
q0
q1
Non complet sur {a, b} car
d (q0, b) = f
L(A) = a(a+b)*
q0
b
a
a
p
q1
a,b
Complet sur {a, b}
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
58
II.3. Rendre déterministe un automate
fini non déterministe
II.3.2. Automate fini ambigu
Si l’automate fini est non déterministe par ce qu’il est
ambigu alors on doit construire un automate en groupant
les états visités par un même symbole à partir d’un état,
ces états groupés forment les nouveaux états de l’automate
déterministe. La construction de l’automate déterministe
déterministe. La construction de l’automate déterministe
suit les étapes suivantes:
Etape 1. Définir les nouveaux groupes d’états
Etape 2. Renommer les nouveaux groupes et définir les états
finaux. Un nouvel état (Groupe d’état) est un état final ssi il
contient un ancien état final
Etape 3. Construire l’automate déterministe
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
59
II.3. Rendre déterministe un automate
fini non déterministe
Exemple1
Etape 1. Définir les nouveaux groupes d’états
a
q0
a,b
a,b
a,b
q1
L(A) = a*(a+b)+
a
a
{q0}
{q0, q1}
{q0, q1}
{q0, q1}
{q1}
{q1}
b
b
{q1}
{q1}
{q1}
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
60
II.3. Rendre déterministe un automate
fini non déterministe
Exemple1
Etape 2. Renommer les états et définir les états finaux
a
q0
a,b
a,b
a,b
q1
a
a
b
b
{q0} A
{q0, q1} B
{q1} C
{q0, q1} B
{q0, q1} B
{q1} C
{q1} C
{q1} C
{q1} C
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
61
II.3. Rendre déterministe un automate
fini non déterministe
Exemple1
Etape 3. Construire l’automate déterministe
A
a
B
b
a
a
b
a,b
C
a
a
b
b
{q0} A
{q0, q1} B
{q1} C
{q0, q1} B
{q0, q1} B
{q1} C
{q1} C
{q1} C
{q1} C
Leila Jemni Ben Ayed
Théorie des Langages et Compilation-2013
62
II.3. Rendre déterministe un automate
fini non déterministe<...