Python
C
C++
Alain Chillès – 祁冲 Ada
Java
Théorie des langages de programmation
Autom
g
P
ate
r
s
fini
o
l
s
–
deuxième partie
o
ParisTech Shanghai Jiao Tong 上海交大–巴黎高科卓越工程师学院
23 septembre 2016 – 2016年9月23日 –丙申年八月廿三
Lisp
APL
Fortran
Forth
Pascal
1
Plan
C
Python Prolog
Java Forth
Analyse lexicale
Automates finis −→ expressions rationnelles
C++
Ada
Pascal
Automate et programmation
Jeu
Lisp
APL
Fortran
2
Automates finis −→ expressions rationnelles Python
C
Prolog
Trois méthodes :
1 réduire pas à pas le nombre d’états ;
C+
2
+
3
iser l’algorithme de Mac Naughton – Yamada.
utiliser l’algorithme de Gauss – Arden ;
util
Lisp
APL
Fortran
Ada
Java
Forth
Pascal
3
Automates généralisés
Python
Java
C
Prolog
Définition
On appelle automate généralisé un automate fini (AFN ou AFD) où
les transitions peuvent être déclenchées par une expression rationnelle.
C++ Ada
0
Lisp
[a-zA-Z0-9]+ 1
Pascal
Forth
APL
Fortran
4
Exemple de la première méthode
Soit l’automate :
C
Pro
1
Python
Java
log
01
1 Ada 0022
Pascal Fortran
C++ Lisp
2 APL1
2
0
Forth
3
5
Exemple de la première méthode
Python
Java
C
0 ε Forth
1ε Ada
00224
Pascal
ε
Fortran
Normalisation (un seul état initial, un seul état final) :
1
01
C++ Lisp
12 2 APL
Prolog
3
6
Exemple de la première méthode
Python
Suppression de l’état 3 :
C
Prolog
(0|20)
Java Forth
20 1
C++
2
Ada
(2|ε)
0
(0|20)
(1|21)
(1|21) 3
Lisp
APL
2
Fortran
(2|ε)
Pascal
21
7
Exemple de la première méthode
Python C
Java
Suppression de l’état 2 :
Forth
Prolog
20((1|21).(21)∗ .(0|20))
(0|20)((1|21).(21)∗ .(0|20)) (2|ε)((1|21).(21)∗ .(2|ε))
Ada
012
C++ Lisp
2((1|21).(21)∗ .(2|ε))
Pascal
APL
Fortran
8
Exemple de la première méthode
Python C
Suppression de l’état 1 :
F
Java Prolog
2((1|21).(21)∗ .(2|ε))(0|20)((1|21).(21)∗ .(0|20)).20((1|21).(21)∗ .(0|20))∗ .(2|
∗
01
C++
Ada
Le résultat n’est pas garanti ! Comprendre la méthode ! Les
expressions rationnelles sont trouvées en exprimant (pour la suppression de l’état e) : « je vais de l’état e à l’état e en
passant peut-être par e »…
APL
Fortran
Lisp
ε)((1|2
o
1).(21
r
) .(2
Pascal
12
t
|ε))
h
9
Exemple de la deuxième méthode
C
C++
X = A.X ∪ B X = A∗.B
Python
Java
Théorème (Arden)
P
r
o
l
o
g
Soit A et B deux lan
ε ̸∈ A, alors le seul langage X
qui vérifie est
Forth Ada
Pascal
gag
es
tels
q
ue
Démonstration.
À faire vous-même !
Lisp
APL
Fortran
10
Exemple de la deuxième méthode
SystèC
Python
Java
me d’équations obtenu de la manière suivante :
1 chaque état correspond à une variable, qui est un nom de
langage (L est le langage défing
i
Prolo
i par l’ensemble des mots
reconnus à partir de l’état e ) ; i
2 on décrit le langage Li par une équation du genre Forth
ai,j
L={a}.L i i,jj
si ei ej Ada
C++
j
ai,j
L = {a }.L∪{ε} si
ei
ej Pascal
i i,jj
j
3 on résout le système obtenu, avec un algorithme de Gauss et le théorème d’Arden ;
Lisp APL
rationnelle cherchée.
4
Fortran
le résultat obtenu pour l’état initial correspond à l’expression
11
Exemple de la deuxième méthode
C++ Lisp
123
a
Python Prolog
Java Le système obtenu est : Forth
C
L0 = {0}.L1 ∪ {1}.L2 ∪ {2}.L3
L = {1}.L ∪ {2}.L ∪ {ε}
L2={0}.L1∪ 3
L3 =
A
{2}.
{ε}
d
L∪
{0}.L1 ∪ {1}.L2 ∪ {ε}. Pascal
APL
Fortran
12
Exemple de la deuxième méthode
C
L1 =
L2 =
L3 =
C++
{0}.L2 ∪ {2}.L3 ∪ {ε}
Python
Java
En reportant la deuxième équation dans la troisième et la
quatrième, on obtient :
Prolog
L = {0}.L ∪ {1}.L ∪ {2}.L 0123
Forth
{01}.L2 ∪ {02}.L3 ∪ {0} ∪ {2}.L3 ∪ {ε}
{01}.L2 ∪ {02}.L3 ∪ {0} ∪ {1}.L2 ∪ {ε}. Ada
La troisième équation se résout avec le théorème d’Arden, on
obtient :
Pascal
Lisp
∗ APL
Fortran
L2 = {01} . ({02}.L3 ∪ {0} ∪ {2}.L3 ∪ {ε}) .
13
Exemple de la deuxième méthode
C
Python
Java
En reportant le résultat dans la quatrième, on obtient :
L = {0}.L ∪ {1}.L ∪ {2}.L 0123
Prolog
L = {0}.L ∪ {2}.L ∪ {ε} 123
L2 =
L3 =
C++
{01}∗. ({02}.L3 ∪ {0} ∪ {2}.L3 ∪ {ε}) Forth
Lisp
APL
{1, 01}.{01}∗. ({02}.L3 ∪ {0} ∪ {2}.L3 ∪ {ε}) ∪{02}.L3 ∪ {0} ∪ {ε}.
La quatrième équation se résout avec le théorème d’Arden, on
obtient :
L3 = ({1, 01}.{01} .{02} ∪ {1, 01}.{01} .{2} ∪ {02}) .
Ada
∗∗∗
∗∗
({1,01}.{01}.{0}∪{0,01}.{01} ∪{0}∪{ε}).
Pascal
Fortran
14
Exemple de la deuxième méthode
Python C Prolog
Il suffit pour conclure de
1 reporter la valeur de L3 dans L2 ;
Java Forth
reporter les valeurs de L et L obtenues dans L ; 231
2
3 reporter les valeurs de L1, L2 3 0
C++
Bon courage !
Lisp
et L
ob
A
tenues dans L . a
d
Pascal
APL
Fortran
15
Exemple de la troisième méthode
1 2
on numérote les états de 1 à n ;
Python
Java
C′2
si (q,q ) ∈ [1,n] , on note pour k ∈ [1,n]
P
o
sant par les états dans [1,k] g
r
lo
q,q Forth
Lk ′ =chemi ′
pas
;
C++
Ada
L= Lni,j (i,j)∈I×F
Lisp
a q′ Fortran
ns de
q
àq
on alors, si on note I l’ensemble des états initiaux et F l’ensemble des états finaux, le langage reconnu cherché vaut :
et, on a clairementAPL
Pascal
∀(q,q′)∈[1,n]2, L0 ′ = a∈A, q,q
q
.
16
Exemple de la troisième méthode
C
Java
F
Ada
′
C++
Cela traduit :
Python
et on utilise la relation de récurrence immédiate, pour
k∈[0,n−1]et(q,q′)∈[1,n] : Prolog Lk+1=Lk ′∪Lk .Lk
orth
2
q,q′ q,q
q,k+1 k+1,k+1
k+1,q
′
« Pour aller de l’état q à l’état q , en n’utilisant que les k + 1 premiers états, on peut, soit aller de q à q en n’utilisant que les k
premiers états, soit aller de l’état q à l’état k + 1,
′ Pascal
nt
les k premiers états, boucler sur l’état k + 1 en n’utilisant que les k
e premiers états, puis aller de l’état k + 1 à l’état q en n’utilisant
que les k premiers états. » Lisp
Fortran
APL ′
∗.Lk
en n
ilisa
’ut
qu
17
Exemple de la troisième méthode
Python C
Java
On obtient :
1
2 3
L01,2 = L03,2 = L04,2 = {0}, L01,3 = L02,3 = L04,3 = {1}, Prolog
L1,4 = L2,4 = L3,4 = {2} et les autres sont {ε}.
0 0 0 Forth
puis, on applique l’algorithme…
celui qui nous intéresse est Ada
C++ Lisp
4
L 41 , j . j=2
APL
Fortran
Pascal
18
Plan
C
Analyse lexicale
Python Prolog
Java Forth
Automates finis −→ expressions rationnelles
C++
Ada
Pascal
Automate et programmation
Jeu
Lisp
APL
Fortran
19
Passage de l’automate au code
C
exit(1);
Source C
Python
Java
C
7
8 }; 9
#include
1
2
3
4
5{
6 printf(“Le mot %s n’est pas
void error(char s[])
→ reconnu.\n”,s); ++
10 int main()
11 {
Prolog
#include
Lisp
13 char s[100]; // Chaîne lue
12 int i,etat_
Forth Ada
Pascal
n; // n est le nombre APL
acti
→ de caractères dans {0,1,2} lus
f=0,
Fortran
20
Passage de l’automate au code
Source C
C
Python
Java
14
15
printf(“Entrer une suite de 0, de 1 et de → 2 : “);Prolog
// Noter le format de la chaîne s, pour ne → pas lire de caractères interdits (le scanf
→ s’arrête dès que l’on a tapé autre chose
→ qu’un 0, un 1 ou un deux) 16 scanf(“%99[012]%n”,s,&n);
C++
17 printf(“J’ai lu %s (longueur %d)\n”,s,n);
18 for(i=0;i