L ANGAGE ET AUTOMATE
Plan
1 L ANGAGE ET AUTOMATE
Le concept de langage
Le concept d’automate
Automate fini déterministe
Automate fini non déterministe
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 2
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
On veut concevoir un simple système qui
présente l’état de la voiture au démarrage.
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 3
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
On veut concevoir un simple système qui
présente l’état de la voiture au démarrage.
q Voiture ON
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 3
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
On veut concevoir un simple système qui
présente l’état de la voiture au démarrage.
q Voiture ON
q Tout va bien
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 3
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
On veut concevoir un simple système qui
présente l’état de la voiture au démarrage.
q Voiture ON
q Tout va bien
q Vérifier l’huile
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 3
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
On veut concevoir un simple système qui
présente l’état de la voiture au démarrage.
q Voiture ON
q Tout va bien
q Vérifier l’huile
q J’ai besoin d’essence
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 3
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
On veut concevoir un simple système qui
présente l’état de la voiture au démarrage.
q Voiture ON
q Tout va bien
q Vérifier l’huile
q J’ai besoin d’essence
q Rapport terminé
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 3
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
q Un Alphabet est l’ensemble d’événements :
E={Voiture ON, Tout va bien, Vérifier l’huile, J’ai besoin d’essence,
Rapport terminé}
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 4
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
q Un Alphabet est l’ensemble d’événements :
E={Voiture ON, Tout va bien, Vérifier l’huile, J’ai besoin d’essence,
Rapport terminé}
q Une chaîne est une séquence d’événements
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 4
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
q Un Alphabet est l’ensemble d’événements :
E={Voiture ON, Tout va bien, Vérifier l’huile, J’ai besoin d’essence,
Rapport terminé}
q Une chaîne est une séquence d’événements
Exemples
q Voiture ON-Tout va bien-Rapport terminé
q Voiture ON-J’ai besoin d’essence
q Voiture ON
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 4
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
q Un Alphabet est l’ensemble d’événements :
E={Voiture ON, Tout va bien, Vérifier l’huile, J’ai besoin d’essence,
Rapport terminé}
q Une chaîne est une séquence d’événements
Exemples
q Voiture ON-Tout va bien-Rapport terminé
q Voiture ON-J’ai besoin d’essence
q Voiture ON
q Un langage est un ensemble de chaînes
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 4
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
q Un Alphabet est l’ensemble d’événements :
E={Voiture ON, Tout va bien, Vérifier l’huile, J’ai besoin d’essence,
Rapport terminé}
q Une chaîne est une séquence d’événements
Exemples
q Voiture ON-Tout va bien-Rapport terminé
q Voiture ON-J’ai besoin d’essence
q Voiture ON
q Un langage est un ensemble de chaînes
Exemples
q Voiture ON-Tout va bien-Rapport terminé → État normal
q Voiture ON-Vérifier l’huile-Rapport terminé → État anormal
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 4
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
Remarques
q Une chaîne composée d’aucun événement est appelée la
chaîne vide et est noté ε
q La longueur d’une chaîne est le nombre d’événements
qu’elle contient noté |s|
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 5
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
Définition (langage)
Un langage défini sur un ensemble d’événements E est
un ensemble de chaînes de longueur finie formées à partir
d’événements dans E.
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 6
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
Définition (langage)
Un langage défini sur un ensemble d’événements E est
un ensemble de chaînes de longueur finie formées à partir
d’événements dans E.
A titre d’exemple, soit E = {a, b, g} l’ensemble des événements. On
peut alors définir le langage :
q L1 = {ε, a, abb}
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 6
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
Définition (langage)
Un langage défini sur un ensemble d’événements E est
un ensemble de chaînes de longueur finie formées à partir
d’événements dans E.
A titre d’exemple, soit E = {a, b, g} l’ensemble des événements. On
peut alors définir le langage :
q L1 = {ε, a, abb}
q L2 = {toutes les chaînes possibles de longueur 3 commençant par l’événement a}
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 6
L ANGAGE ET AUTOMATE
Le concept de langage
Modèles de langage des systèmes d’événements
discrets
Définition (langage)
Un langage défini sur un ensemble d’événements E est
un ensemble de chaînes de longueur finie formées à partir
d’événements dans E.
A titre d’exemple, soit E = {a, b, g} l’ensemble des événements. On
peut alors définir le langage :
q L1 = {ε, a, abb}
q L2 = {toutes les chaînes possibles de longueur 3 commençant par l’événement a}
q L3 = {toutes les chaînes possibles commençant par l’événement a}
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 6
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Définition (Automate)
Un automate est un modèle capable de représenter un langage
selon des règles bien définies.
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 7
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Définition (Automate)
Un automate est un modèle capable de représenter un langage
selon des règles bien définies.
La manière la plus simple de présenter la notion d’automate est de
considérer son diagramme état-transition. Nous utilisons les
exemples suivants à cette fin
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 7
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : L’interrupteur
Etat OFF Etat ON
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : L’interrupteur
Etat OFF Etat ON
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : L’interrupteur
Etat OFF Etat ON
q Diagramme d’état-transition
Appuyer sur l’interrupteur
Etat initial Etat
OFF ON
Transition
Appuyer sur l’interrupteur Evènement
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 8
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : Feu de circulation
q Diagramme d’état-transition
Etat initial t=0 Etat
t=1
Rouge
t=0
t=1
Vert
Jaune Transition
t=1
Evènement
t=0
t=temps, si un temps défini découle
(Ex 30s) donc t=1 sinon t=0
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 9
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : L’ascenseur
1
Up
Down
0
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : L’ascenseur
2
q Diagramme d’état-transition
Down Up Up Up
1 0 1 2
Up
Down Down
Down
0
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 10
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : Un simple automate
a b
x a
y
g a,g
b
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : Un simple automate
q Ensemble d’états :
X = {x, y , z}
a b
x a
y
g a,g
b
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : Un simple automate
q Ensemble d’états :
X = {x, y , z}
q Ensemble d’événements :
a b
E = {a, b, g}
x a
y
g a,g
b
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : Un simple automate
q Ensemble d’états :
X = {x, y , z}
q Ensemble d’événements :
a b
E = {a, b, g}
x a
y q La fonction de transition f : X × E → X
f (x, a) = x f (x, g) = z
g a,g f (y , a) = x fy , b) = y
f (z, b) = z f (z, a) = f (z, g) = y
z
b
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : Un simple automate
q Ensemble d’états :
X = {x, y , z}
q Ensemble d’événements :
a b
E = {a, b, g}
x a
y q La fonction de transition f : X × E → X
f (x, a) = x f (x, g) = z
g a,g f (y , a) = x fy , b) = y
f (z, b) = z f (z, a) = f (z, g) = y
z
q L’état initial : x0 = x
b
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : Un simple automate
q Ensemble d’états :
X = {x, y , z}
q Ensemble d’événements :
a b
E = {a, b, g}
x a
y q La fonction de transition f : X × E → X
f (x, a) = x f (x, g) = z
g a,g f (y , a) = x fy , b) = y
f (z, b) = z f (z, a) = f (z, g) = y
z
q L’état initial : x0 = x
b
q L’ensemble d’états finaux (marqués) :
Xm = {x, z}
L ANGAGE ET AUTOMATE
Le concept d’automate
Le concept d’automate
Exemple : Un simple automate
q Ensemble d’états :
X = {x, y , z}
q Ensemble d’événements :
a b
E = {a, b, g}
x a
y q La fonction de transition f : X × E → X
f (x, a) = x f (x, g) = z
g a,g f (y , a) = x fy , b) = y
f (z, b) = z f (z, a) = f (z, g) = y
z
q L’état initial : x0 = x
b
q L’ensemble d’états finaux (marqués) :
Xm = {x, z}
q Puisque X et fini, on parle d’automates
à états finis
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 11
L ANGAGE ET AUTOMATE
Le concept d’automate
Types d’automate
Automates
Automates avec Automates sans
sor!e sor!e
Moore Mealy
Automates Automates non e - Automates non
déterministes déterministe déterministe
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 12
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Définition (Automate déterministe)
Un automate fini déterministe, noté AFD, est un cinq-uplet :
AFD = {X , E, f , x0 , Xm }
Avec :
X : l’ensemble de tous les états
E : l’ensemble d’événements
f : la fonction de transition notée f : X × E → X
x0 : l’état initial
Xm : l’ensemble d’états marqués (finaux)
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 13
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 1
b
b E2
E0
a b
a
E1
a
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 1
q X {E0, E1, E2}
b
b E2
E0
a b
a
E1
a
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 1
q X {E0, E1, E2}
q E {a, b}
b
b E2
E0
a b
a
E1
a
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 1
q X {E0, E1, E2}
q E {a, b}
b
b
q x0 = E0
E0 E2
a b
a
E1
a
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 1
q X {E0, E1, E2}
q E {a, b}
b
b
q x0 = E0
E0 E2
q Xm = {E2}
a b
a
E1
a
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 1
q X {E0, E1, E2}
q E {a, b}
b
b
q x0 = E0
E0 E2
q Xm = {E2}
a b
a q la fonction de transition f :
E1
a b
a E0 E1 E0
E1 E1 E2
E2 E1 E0
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 14
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
Considérant l’ensemble d’événements E = {0, 1}
Soit le langage : L1 = { définir toutes les chaines commençant par 0 }
L1 = { 0, 01, 001, 011, 0110, ... }
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
Considérant l’ensemble d’événements E = {0, 1}
Soit le langage : L1 = { définir toutes les chaines commençant par 0 }
L1 = { 0, 01, 001, 011, 0110, ... }
0,1
0
E0 E2
1
E1
0,1 Blocage
(Etat mort)
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
Considérant l’ensemble d’événements E = {0, 1}
Soit le langage : L1 = { définir toutes les chaines commençant par 0 }
L1 = { 0, 01, 001, 011, 0110, ... }
q X {E0, E1, E2}
0,1
0
E0 E2
1
E1
0,1 Blocage
(Etat mort)
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
Considérant l’ensemble d’événements E = {0, 1}
Soit le langage : L1 = { définir toutes les chaines commençant par 0 }
L1 = { 0, 01, 001, 011, 0110, ... }
q X {E0, E1, E2}
0,1 q E {0, 1}
0
E0 E2
1
E1
0,1 Blocage
(Etat mort)
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
Considérant l’ensemble d’événements E = {0, 1}
Soit le langage : L1 = { définir toutes les chaines commençant par 0 }
L1 = { 0, 01, 001, 011, 0110, ... }
q X {E0, E1, E2}
0,1 q E {0, 1}
0 q x0 = E0
E0 E2
1
E1
0,1 Blocage
(Etat mort)
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
Considérant l’ensemble d’événements E = {0, 1}
Soit le langage : L1 = { définir toutes les chaines commençant par 0 }
L1 = { 0, 01, 001, 011, 0110, ... }
q X {E0, E1, E2}
0,1 q E {0, 1}
0 q x0 = E0
E0 E2
1
q Xm = {E2}
E1
0,1 Blocage
(Etat mort)
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
Considérant l’ensemble d’événements E = {0, 1}
Soit le langage : L1 = { définir toutes les chaines commençant par 0 }
L1 = { 0, 01, 001, 011, 0110, ... }
q X {E0, E1, E2}
0,1 q E {0, 1}
0 q x0 = E0
E0 E2
1
q Xm = {E2}
E1 q la fonction de transition f :
0,1 Blocage 0 1
(Etat mort) E0 E2 E1
E1 E1 E1
E2 E2 E2
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
Considérant l’ensemble d’événements E = {0, 1}
Soit le langage : L1 = { définir toutes les chaines commençant par 0 }
L1 = { 0, 01, 001, 011, 0110, ... }
q X {E0, E1, E2}
0,1 q E {0, 1}
0 q x0 = E0
E0 E2
1
q Xm = {E2}
E1 q la fonction de transition f :
0,1 Blocage 0 1
(Etat mort) E0 E2 E1
E1 E1 E1
E2 E2 E2
0 0 1
Ex : 001 E0 E2 E2 E2 Etat final
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
Considérant l’ensemble d’événements E = {0, 1}
Soit le langage : L1 = { définir toutes les chaines commençant par 0 }
L1 = { 0, 01, 001, 011, 0110, ... }
q X {E0, E1, E2}
0,1 q E {0, 1}
0 q x0 = E0
E0 E2
1
q Xm = {E2}
E1 q la fonction de transition f :
0,1 Blocage 0 1
(Etat mort) E0 E2 E1
E1 E1 E1
E2 E2 E2
0 0 1
Ex : 001 E0 E2 E2 E2 Etat final
0 0 1
Ex : 101 E0 E1 E1 E1 Etat non final
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 15
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
On veut programmer le code PIN d’un télé-
phone portable.
L’ensemble d’événements est :
E = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
le code PIN correcte c’est 1234
Soit le langage : L1 = {1234}
L ANGAGE ET AUTOMATE
Automate fini déterministe
Automate fini déterministe
Exemple 2
On veut programmer le code PIN d’un télé-
phone portable.
L’ensemble d’événements est :
E = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
le code PIN correcte c’est 1234
Soit le langage : L1 = {1234}
Le diagramme d’état-transition :
0,1,2,3,5, 0,1,2,3,4,
6,7,8,9 5,6,7,8,9
0,2,3,4,5,
6,7,8,9
1 2 3 4
E0 E1 E2 E3 E4
0,1,3,4,5,
6,7,8,9
0,1,2,4,5,
6,7,8,9
Penser à d’autres améliorations !
Pr. Marouane EL AZZAOUI • Systèmes à événements discrets (SED) 16