Le langage
Pour comprendre les notions liées à la théorie de la supervision, il est nécessaire de présenter celles liées à la théorie des langages. La théorie des langages est fondée sur la théorie des ensembles. Il s’agit donc d’une théorie éprouvée pour la modélisation et la manipulation des SED. Un langage est composé de deux ensembles, un alphabet noté S et un ensemble de mots noté L. L’alphabet est constitué de l'ensemble des événements ou des actions réalisables par le SED. La concaténation des éléments de l’alphabet forme des mots ou traces qui sont des modèles de séquences d’événements ou séquences d’actions. La théorie des langages définit e qui représente à la fois la chaîne vide et l’événement vide.Exemple:
Soit S={a,b,c,d}
et L={ab,bc}, le langage de L définit sur S compte les 2 mots ab et bc.
Opérations sur les langages
Fermeture de kleene
La fermeture de Kleene d'un langage consiste en la
réalisation d'un langage noté S* modélisant toutes les combinaisons d'événements
possibles à partir de S incluant la chaîne vide e.
Exemple:
Si S={a,b};
L={ab,bc} alors S*=(a|b)*
(le symbole * sur un événement signifie que ce dernier peut apparaître de 0 à n
fois. Le langage constitué de L'=a* équivaut à L'={e,a,aa,aaa,aaaa,aaaaaa,…})
Fermeture préfixée
La fermeture préfixée est l'augmentation du langage à
l'aide de tous les préfixes des mots contenus dans le langage incluant e.
Le préfixe d’un mot est une partie antécédente du mot qui n’est pas e.
Exemple:
Si S={a,b,c};
L={ab,bc} alors Lpréf={e,a,b,ab,bc}
Union
L'union est l’opération permettant de mettre dans un seul
langage l’ensemble des mots des différents langages.
Exemple:
Si S1={a,b,c};
L1={ab,bc} et S2={a,b,y,z};
L2={ab,yz} alors, L1 U L2 = L3 tel que : S3={a,b,c,d,y,z}; L3={ab,bc,yz}
L'intersection
L'intersection est une opération permettant de créer un
langage à partir des mots se trouvant dans les deux langages.
Exemple:
Le complement
Le complément d'un langage L1 correspond au langage L2 = L1comp contenant tous les mots
réalisables avec l'alphabet de L1 moins les traces de L1. Mathématiquement,
cela correspond à réaliser L2=S1*-L1.
Exemple:
Si S1={a};
L1={aa} alors L1comp=L2={a|aaa(a)* }
La projection
L'opération de projection d'un langage s'effectue par
rapport à un alphabet de projection, ce dernier étant inclus ou égal à
l’alphabet du langage. Cette opération est assimilable à un filtrage sur les
événements contenus dans les mots du langage. Les événements restant dans les
mots étant les événements présents dans l’alphabet de projection.
Exemple:
Si S1={a,b,c};
L1={ab,bc} et Sp={b,c}
l'alphabet sur lequel L1 est projeté alors P(L1,Sp)={b,bc}.
La projection inverse
L'opération de projection inverse permet de compléter un
langage avec des événements non contenus dans son alphabet. Ces événements vont
être insérés entre chaque événement de chaque mot du langage de façon à
construire un langage de taille maximale. La projection inverse permet pour le
langage de considérer les nouveaux événements ajoutés comme étant possibles à
chaque instant. La projection inverse sera notée IP tels que si A est la
projection inverse de B suivant un alphabet S alors A=IP(B,S).
Il est nécessaire de préciser que les opérations de projection et de projection
inverse ne sont pas des réciproques.
Exemple:
Si S1={a,b,c};
L1={ab,bc} et Sp={b,d}
l'alphabet sur lequel la projection inverse est réalisée alors IP(L1,Sp)={d*ad*bd*,d*bd*cd*}
References:
C. G. Cassandras, and S. Lafortune. Introduction to discrete event systems, Kluwer Academic Publishers, 1999, ISBN: 0-7923-8609-4.
Aucun commentaire:
Enregistrer un commentaire