Python
C
Java
Théorie des langages de programmation
P
lo
r
A
o
g
u
tom
ate
Alain Chillès – 祁冲 Ada
C++
20 septembre 2016 – 2016年9月20日 –丙申P年八a月二s十cal
Lisp
APL
Fortran
ParisTech Shanghai Jiao Tong 上海交大–巴黎高科卓越工程师学院
s finis
Forth
1
Plan
C
Python Prolog
Java
Analyse lexicale
Automates finis
Automate et programmation
Forth Ada
Pascal
C++
Jeu
Lisp
APL
Fortran
2
De la difficulté d’écrire les expressions rationnelles
Définition
Python
Java
Étant donné un alphabet Σ sur lequel on à construit un langage L, C
Prolog
Un état initial, noté :
Des états d’acceptation, notés :
on appelle automate reconnaissant les mots du langage A, un ensemble constitué d’états et de transitions comportant
Forth
C++
da
A
Des états intermédiaires, not
Un mot du langage est consommé caractère par caractère et permet à travers les transitions de changer d’état. Au départ,
état d’acceptation, le mot est reconnu, sinon le mot n’est pas dans
Lisp
APL
Fortran
le langage. Une transition déclenchée par le caractère c est notée
és :
l’automate est dans l’état initial. À la fin, si l’automate est dans un
Pascal
3
De la difficulté d’écrire les expressions rationnelles
Python C
Java
Fluxd’entrée: a→b→b→a→b Prolog
C++
Forth Ada
[a,b,b,a,b]
Reconnaît le même langage que l’expression rationnelle (a|b)*ab
Lisp
APL
Fortran
Pascal
4
De la difficulté d’écrire les expressions rationnelles
Python C
Java
Fluxd’entrée: a→b→b→a→b Prolog
C++
Forth Ada
[b,b,a,b]
Reconnaît le même langage que l’expression rationnelle (a|b)*ab
Lisp
APL
Fortran
Pascal
4
De la difficulté d’écrire les expressions rationnelles
Python C
Java
Fluxd’entrée: a→b→b→a→b Prolog
C++
Forth Ada
[b,a,b]
Reconnaît le même langage que l’expression rationnelle (a|b)*ab
Lisp
APL
Fortran
Pascal
4
De la difficulté d’écrire les expressions rationnelles
Python C
Java
Fluxd’entrée: a→b→b→a→b Prolog
C++
Forth Ada
[a,b]
Reconnaît le même langage que l’expression rationnelle (a|b)*ab
Lisp
APL
Fortran
Pascal
4
De la difficulté d’écrire les expressions rationnelles
Python C
Java
Fluxd’entrée: a→b→b→a→b Prolog
C++
Forth Ada
[b]
Reconnaît le même langage que l’expression rationnelle (a|b)*ab
Lisp
APL
Fortran
Pascal
4
De la difficulté d’écrire les expressions rationnelles
Python C
Java
Fluxd’entrée: a→b→b→a→b Prolog
C++
Forth Ada
[]
Reconnaît le même langage que l’expression rationnelle (a|b)*ab
Lisp
APL
Fortran
Pascal
4
Automates Finis Non déterministes (AFN) ou Déterministes
(AFD)
Python
Java
C
Définition
Prolog
On appelle ε-transition une transition qui se déclenche sans
consommation d’un caractère du flux d’entrée. (Elle se déclenche
tout le temps). Elle est notée :
C++
Définition
possédant au moins un état d’acceptation et peut-être des
ε-transitions.
Forth Ada
On appelle automate fini non déterministe (AFN) tout automate Pascal
Lisp
APL
On appelle automate fini déterministe (AFD) tout AFN ne
po
pas d’ε-transition et tel qu’au plus une transition puisse Fortran
sséd
an
t
être déclenchée pour un caractère donné.
5
AFN ⇐⇒ AFD Python
Java
C
Théorème
Tout AFN peut-être transformé en un AFD équivalent (qui
reconnaît le même langage).
Forth Ada
Pascal
Prolog
C++ Lisp
APL
Fortran
6
Automates finis et langages rationnels
Python C
Java
Un langage est reconnu par un automate fini (AFN ou AFD) si, et
Thé
orème
Prolog
seulement si il est rationnel.
Démonstration.
Forth
C++
Ada
Pascal
Chaque élément de l’alphabet x ∈ Σ du langage est reconnu
par un automate.
Il suffit de savoir faire les opérations sur les langages
APL
Fortran
Lisp
7
On peut se limiter à un état d’acceptation
Python C Prolog
. . ..
Java Forth
C++ Lisp
Ada
Pascal
APL
Fortran
8
Représentation des automates dans la démonstration
C
Python Prolog
Java
C++ Lisp
Forth Ada
Pascal
APL
Fortran
9
Réunion de deux langages
Python C
Prolog
C++ Lisp
Java Forth
Ada
Pascal
APL
Fortran
10
Concaténation de deux langages
C
Python Prolog
Java
C++ Lisp
Forth Ada
Pascal
APL
Fortran
11
Fermeture de Kleene d’un langage
C
Python Prolog
Java
C++ Lisp
Forth Ada
Pascal
APL
Fortran
12
Fermeture positive d’un langage
C
Python Prolog
Java
C++ Lisp
Forth Ada
Pascal
APL
Fortran
13
Plan
C
Python Prolog
Java
Analyse lexicale
Automates finis
Forth Ada
Pascal
C++
Automate et programmation
Jeu
Lisp
APL
Fortran
14
Lien avec la programmation
Python C Prolog
Java Forth
Trois manières d’utiliser les automates :
1 Écrire une expression rationnelle et donc un analyseur lexical.
Réagir aux événements (on fait une action à chaque transition)
2
3 Gérer les changements d’état
a
C++
s (on
fai
état)
Lisp
APL
Fortran
A
Pascal
d
t une action dans chaque
15
Plan
C
Python Prolog
Java
Analyse lexicale
Automates finis
Forth Ada
Pascal
C++
Automate et programmation
Jeu
Lisp
APL
Fortran
16
Production d’automates
C
Python Prolog
Java
Appliquer les algorithmes donnés pour trouver un AFD qui reconnaît
le même langage que les expressions rationnelles suivantes :
a*ba*ba*ba*
([-+]?[0-9]+\.?[0-9]*|[-+]?\.[0-9]+)
C++ Lisp
APL
Fortran
Forth
Ada
Pascal
17
Production d’expression rationnelle
Python
J
Donner une description du langage reconnu par cet aut
a
C
l’aide d’une expression rationnelle.
om
a
ate
à
v
Prolog
C++ Lisp
Forth Ada
Pascal
APL
Fortran
18