C
P
C++
Alain Chillès – 祁冲 Ada
Python
Java
Théorie des langages de programmation –
Ma
g
r
o
ch
in
l
es
d
o
ParisTech Shanghai Jiao Tong 上海交大–巴黎高科卓越工程师学院
Pascal
21 octobre 2016 – 2016年10月21日 –丙申年九月廿一
Lisp
APL
Fortran
e Turing
Forth
1
Plan
C
Python Prolog
Java
Machines Automates
Forth Ada
Pascal
C++
Autres machines
Jeu
Lisp
APL
Fortran
2
AFN – Automates finis non déterministes
Python C
Java
Définition
Un automate fini non déterministe est défini par : Forth Prolog
un flux d’entrée constitué de mots appartenant à un langage L, défini sur un alphabet fini A ;
un ensemble fini d’états, noté Γ ;
un sous-ensemble I ⊂ Γ des états initiaux ; C++
une fonction T de transition, définie de
APL
Fortran
un sous-ensemble F ⊂ Γ des états d’acceptation ;
Lisp
Γ × (A ∪ {ε}) → P(Γ).
Ada
Pascal
3
AFN – Un exemple
C
Prol
Python
Java
a 0a2
og
1b3
b
a
ab
Forth
C++
Ada
A = {a,b}, Γ = {0,1,2,3}, I = {0,1}, F = {2,3} et Pascal
T:
(0, a) → {2} (0, b) → {3} Lisp (1,a)→{2} (1,b)→{3}
APL Fo
(2,a) → {2,3} (2,b) → ∅
rtran
(3, a) → ∅ (3, b) →
{2
,3}
b
4
AFD – Automates finis déterministes
Python C
Java
Définition
Un automate fini déterministe est défini par : Prolog
Forth
un flux d’entrée constitué de mots appartenant à un langage L,
défini sur un alphabet fini A ;
un ensemble fini d’états, noté Γ ;
un état initial e0 ; C++
Ada
un sous-ensemble F ⊂ Γ des états d’acceptation ; une fonction partielle T de transition, définie de
Lisp
Γ×A→{{a}, a∈A}.
APL
Fortran
Pascal
5
AFD – Un exemple
Python
Java
Forth
Ada
3
C
1
Prolog
0
1 0022
01
C++
12
2
A = {0,1,2}, Γ = {0,1,2,3}, e0 = 0, F = {1,2,3} et Pascal
T:
(1, 1) → {2} APL
(0,0) → {1} (0,1) → {2}
(0,2) → {3} (1, 2) → {3} (2,2) → {3}
(2,0) → {1} Lisp
(3,0) → {1} (3,1) → {2}
Fortran
6
Automates à pile Python
Java
C
Définition
Un automate à pile est défini par : Prolog
défini sur un alphabet fini A ;
un ensemble fini d’états, noté Γ ;
C+
un flux d’entrée constitué de mots appartenant à un langage L,
un sous-ensemble I ⊂ Γ des états initiaux ;
+
sous-ensemble F ⊂ Γ des états d’acceptation ; p
Ada
un
un alphabet de pile finit A (contenant souvent un symbole
Pascal APL ∗
particulier de fond de pile ⊥) ;
une fonction T de transition, définie de
Lisp
Γ×(A∪{ε})×Ap → P Γ×Ap Fortran
Forth
7
Automates à pile Python Empiler x : → x
a, → a Prolog
Java
b, a →
C
D ́epiler x : x →
b, a →
rth
Fo
0
Reconnaˆıtre {an.bn, n ∈ N}
1
+
C+
Pile
Ada
A={a,b},Γ={0,1},I ={0},F ={0,1},Ap ={a,⊥}et T : (0,a,ε) → {(0,a)} (0,b,ε) → {(1,a)}
Lisp APL
(1,b,a) → {(1,ε)} (x,y,z) → ∅, sinon
Pascal
Fortran
8
Plan
C
Python Prolog
Java
Machines
Automates
Forth Ada
Pascal
C++
Autres machines
Jeu
Lisp
APL
Fortran
9
Machine de Turing déterministe
Python C
Java
Forth
Définition
Une machine de Turing est définie par : Prolog
un alphabet fini A ;
un symbole blanc ⊥ ̸∈ A ;
un état initial e ∈ Γ ;
un ensemble fini d’état Γ ; Ada
C++
0
un sous-ensemble F ⊂ Γ des états d’acceptation ;
une fonction T de transition (fonction partielle), définie de
Lisp
APL
Fortran
Γ × (A ∪ {⊥}) → Γ × (A ∪ {⊥}) × {←, →}
Pascal
10
Mécanisme d’une machine de Turing
reste rempli de ⊥ ; C
Python
Java
Son mécanisme est de plus constitué de
un ruban infini, contenant un nombre fini d’éléments de A, le
un état courant (au départ e ) ; 0
Prolog
une tête de lecture, indiquant l’endroit du ruban où l’on est en
train de lire/écrire.
Forth
C++
Exemple
↓
Ada
Pascal
e0
··· ⊥ ⊥ a1 ··· a ⊥ ⊥ ···
n
Si(e,e′)∈Γ2 et(a,a′)∈(A∪{⊥})2,alorsT(e,a)=(e′,a′,←)
signifie
APL
Lisp
Si la machine est en l’état e et lit sous la tête de lecture le symbole
a, alors elle passe en l’état e′, on remplace a par a′ sous la tête de
lecture, et on se déplace d’une case vers la gauche sur le ruban.
Fortran
11
Machine de Turing – résultat du calcul
Python Prolog
Soit MT une machine de Turing, le langage L ⊂ A dit accepté par
C
Définition
Java
F
la machine de Turing est l’ensemble des mots w constitués de
C
Ada
+
+
symboles de l’alphabet A, tels qu’en partant de la configuration
la machine après lecture de w arrive en un état Pascal
APL
Fortran
init
d’acceptation e ∈ F .
iale,
Lisp
∗
orth
12
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL
Fortran
0
(5, b) → (5, b, ←)
Pascal
↓ ···⊥⊥aba⊥⊥···
13
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL
Fortran
(5, b) → (5, b, ←)
Pascal
1
↓ ···⊥⊥⊥ba⊥⊥···
13
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←) (5, b) → (5, b, ←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL ↓
Fortran
···⊥⊥⊥ba⊥⊥···
1
Pascal
13
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL
Fortran
(5, b) → (5, b, ←)
Pascal
↓ ···⊥⊥⊥ba⊥⊥···
1
13
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←) (5, b) → (5, b, ←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL ↓
Fortran
···⊥⊥⊥ba⊥⊥···
3
Pascal
13
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL
Fortran
(5, b) → (5, b, ←)
Pascal
5
↓ ···⊥⊥⊥b⊥⊥⊥···
13
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL
Fortran
5
(5, b) → (5, b, ←)
Pascal
↓ ···⊥⊥⊥b⊥⊥⊥···
13
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL
Fortran
(5, b) → (5, b, ←)
Pascal
0
↓ ···⊥⊥⊥b⊥⊥⊥···
13
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←) (5, b) → (5, b, ←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL ↓
Fortran
···⊥⊥⊥⊥⊥⊥⊥···
2
Pascal
13
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL
Fortran
(5, b) → (5, b, ←)
Pascal
4
↓ ···⊥⊥⊥⊥⊥⊥⊥···
13
Machine de Turing – un exemple (P. Senellart)
Python
A =C{a, b}, Γ = {0, . . . , 7}, e0 = 0, F = {7} et
Prolog
Java
(0,a) → (1,⊥,→) (1,a)→(1,a,→) (2,a) → (2,a,→)
(0,b) → (2,⊥,→) (1, b) → (1, b, →) (2, b) → (2, b, →)
(0,⊥)→(5,⊥,→) Forth
T: Ada (4,a) → (6,a,←) (4, b) → (5, ⊥, ←)
(1,⊥)→(3,⊥,←) (2,⊥)→(4,⊥,←) (3,⊥)→(7,⊥,←) (4,⊥)→(7,⊥,←) (5,⊥)→(0,⊥,→)
C++
(5,a) → (5,a,←)
(3,a) → (5,⊥,←) (3, b) → (6, b, ←)
Lisp
APL
Fortran
7
(5, b) → (5, b, ←)
Pascal
↓ ···⊥⊥⊥⊥⊥⊥⊥···
13
Modèles équivalents
Python C
Java
Définition
Prolog
Deux modèles de calculs seront dits équivalents s’ils permettent de
reconnaître exactement les mêmes langages.
Forth
Exemple
Ada
les grammaires hors-contexte (BNF) et les automates à pile ;
C++
Les expressions rationnelles et les automates finis ;
les grammaires contextuelles et les machines de Turing à bande
linéairement bornées (taille dépendant de la situation initiale) ; les autres grammaires et les machines de Turing.
Lisp
APL
Fortran
Pascal
14
À quoi ça sert ? Python
Java C Prolog
Définir ce que veut dire calculable ;
évaluer ce qui est possible avec une machine ;
évaluer les ressources en temps et en espace pour réaliser un
Ada
calcul algorithmique ;
C++
thèse de Church : les machines de Turing permettent se simuler tout ce qui est humainement calculable.
Lisp
APL
Fortran
Forth
Pascal
15
Un modèle simple et efficace : l’automate à deux piles
Théorème
Python
Java
C
Prolog
Les machines de Turing et les automates à deux piles sont
équivalents
Démonstration.
Forth
Il suffit de savoir simuler le ruban de la manière suivante :
C++
Ada
ei
↓
·⊥a···aa ···a⊥···
··
devient (transition (ei , ak ) → (ej , α, →)) :
1 kk+1 p
Lisp
↓
APL
ej
Pascal
··· ⊥ a1 ··· α ak+1 ··· ap ⊥ ···
Fortran
16
Automate à deux piles
C
ikjikj
Python
Java
Les transitions (e ,a ) → (e ,α,→) et (e ,a ) → (e ,α,←).
ak +1 Prolog ak +2
Ada
For
ak −1
ak −2
.
a1
ak −1
.
a1
C++
ak
ak
ak +1
. .
.
ap
th
.
ap
α
ak +1
α
ak −1
.
a1
ak +2
.
ap
ak −2
.
a1
Pascal
.
ei ak,→1 α,→2 Lisp
APL
a,→,→α
k 1 2 ej
ak +1
ak −1
ap
ej ei
Fortran
17
Exemple de reconnaissance d’un langage contextuel
Python
Java
Soit C
L = {an.bn.cn, n ∈ N∗}
a,→1 a
b,→1,→2 b Prolog
c,→2 Forth
c,→2 2 Reconnaissance = état d’acceptation+deux piles vides
0
b,→1,→2 b 1 Ada
C++
ε a,→1 a Lisp
a,→1 a
0 b,→1,→2 b
APL
L∪{ε}
b,→1,→2 b c,→2 Pascal
1 c,→2 2 Fortran
18
Plan
C
Python Prolog
Java
Machines
Automates
Forth Ada
Pascal
C++
Autres machines
Jeu
Lisp
APL
Fortran
19
Proposer un automate à deux piles pour reconnaître
Python le langage Prolog
Java
C
npq3 a .b .c , (n,p,q)∈N , 0≤n≤p