Notes du cours

Automates et commande supervisée

Alessandro Giua

GII, Polytech’Marseille

Aix-Marseille Université, Marseille, France

Email: alessandro.giua@univ-amu.fr

vérsion: 13 avril 2017

Table des matières

1 Classification des systèmes dynamiques 1

1.1 Systèmes à avancement temporel . . . . . . . . . . . . . . . . . . . . .. 1

1.2 Systèmes à évènements discrets . . . . . . . . . . . . . . . . . . . . .. 3

1.3 Systèmes hybrides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.4 Classes des systèmes dynamiques . . . . . . . . . . . . . . . . . . . .. 6

2 Langages Formels 7

2.1 Les alphabets et les mots . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2 Les opérations sur les mots . . . . . . . . . . . . . . . . . . . . . . . . .8

2.3 Langages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.4 Les opérations sur les langages . . . . . . . . . . . . . . . . . . . . .. . 10

3 Automates finis déterministes (AFD) 13

3.1 Définition d’un automate fini déterministe . . . . . . . . . . . .. . . . . 13

3.2 Comportement d’un automate fini déterministe . . . . . . . . .. . . . . 15

3.3 Langages d’un automate fini déterministe . . . . . . . . . . . . .. . . . 16

3.4 Propriété d’un automate fini déterministe . . . . . . . . . . . .. . . . . . 18

3.5 Automates comme reconnaisseurs des séquences . . . . . . . .. . . . . 21

4 Automates finis non-déterministes (AFN) 23

4.1 Définition d’un automate fini non-déterministe . . . . . . . .. . . . . . . 23

4.2 Comportement d’un automate fini non-déterministe . . . . .. . . . . . . 24

4.3 Langages d’un automates fini non-déterministe . . . . . . . .. . . . . . 26

iii

4.4 Propriété d’un automate fini non-déterministe . . . . . . . .. . . . . . . 27

4.5 Equivalence entre AFD et AFN . . . . . . . . . . . . . . . . . . . . . . . 28

5 Automates avec entrées et sorties 32

5.1 L’automate de Moore . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.2 L’automate de Mealy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6 Diagnostic et diagnosticabilité des systèmes à évènements discrets à l’aided’automates 35

6.1 Le modèle des procédés . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

6.2 Diagnostic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6.3 Diagnosticabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7 Synthèse modulaire par produit synchrone 48

8 La commande supervisée 53

8.1 Procédé, superviseur et système supervisé . . . . . . . . . . .. . . . . . 54

8.1.1 Procédé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

8.1.2 Évènements contrôlables et incontrôlables . . . . . . . .. . . . . 54

8.1.3 Superviseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

8.1.4 Entrées de commande . . . . . . . . . . . . . . . . . . . . . . . 56

8.2 Superviseurs AFD et système supervisé . . . . . . . . . . . . . . .. . . 57

8.3 Spécifications de contrôle . . . . . . . . . . . . . . . . . . . . . . . . .60

8.4 Conception d’un superviseur pour les spécifications d’états . . . . . . . . 61

8.4.1 États faiblement interdits . . . . . . . . . . . . . . . . . . . . . .62

8.4.2 Conception d’un superviseur . . . . . . . . . . . . . . . . . . . . 63

8.5 Conception d’un superviseur pour les spécifications de langage . . . . . . 65

8.5.1 Mots faiblement interdits . . . . . . . . . . . . . . . . . . . . . . 66

8.5.2 Automate composé et contrôlabilité . . . . . . . . . . . . . . .. 66

8.5.3 Conception d’un superviseur . . . . . . . . . . . . . . . . . . . . 71

iv

A Fonctions et relations 74

A.1 Définitions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

A.2 Relations binaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

A.3 Relations d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . .. 78

B Eléments de la théorie de graphes 80

B.1 Définitions de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

B.2 Chemins et cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

B.3 Sous-graphes et composantes . . . . . . . . . . . . . . . . . . . . . . .82

C Bibliographie 86

v

Chapitre 1

Classification des systèmes dynamiques

L’objectif de la théorie des systèmesest de développer un formalisme général pour mod-éliser, analyser et commander des systèmes dynamiques dansdifférents domaines de lascience et de l’ingénierie. Unsystèmeest un objet physique, tandis qu’unmodèleest unedescription mathématique de son comportement, captant sescaractéristiques qui lui sontpropres. Nous allons décrire brièvement les classes principales de systèmes dynamiquespar la suite.

1.1 Systèmes à avancement temporel

Un système à avancement temporel(SAT) est un système dynamique dont l’évolution estdécrite par des variables numériques qui changent au cours du temps (signaux).

Lorsque la variable indépendant temps prend ses valeurs dans les nombres réels, c.à.d.t ∈ R, on parle desystème à avancement temporel à temps continu, dont le comportementpeut être décrit par uneéquation différentiellede la forme :

x(t) = f(x(t), u(t))

où x(t) ∈ Rn et u(t) ∈ Rm sont, respectivement, le vecteur des états et le vecteur desentrées du système au tempst. Dans le cas linéaire, les descriptions sont souvent utiliséessous la forme :

x(t) = Ax(t) +Bu(t)

oùA ∈ Rn×n etB ∈ Rn×m sont des matrices réelles.

Exemple 1.1 (SAT à temps continu)Un exemple de ce système est schématisé dans lafigure 1.1. Il s’agit d’un réservoir dont le comportement estdécrit par l’équation différen-tielle ci-dessous (nous supposons que le réservoir n’est pas plein) :

d

dtV (t) = q1(t)− q2(t). (1.1)

1

t

q1(t)

q2(t)

V(0)

V(t)

t

q2(t)q1(t)

h(tV(t)

hmax

hmin

FIGURE 1.1 – Un réservoir.

Dans le cas étudié, la variable indépendante est le temps continu t ∈ R. Le signalV (t),volume d’eau en[m3], est l’état du système. Les signauxq1(t) et q2(t), débits d’eau en[m3/s], peuvent être contrôlés par deux pompes : ils correspondentaux entrées de com-mande. ⋄

Lorsque la variable indépendante temps prend des valeurs dans l’ensemble des nombresentiers, c.à.d.k ∈ Z = {0,±1,±2, . . .}, nous parlons ainsi dessystèmes à avancementtemporel à temps discret, dont le comportement peut être décrit par uneéquation auxdifférencesde la forme :

x(k + 1) = f(x(k), u(k))

où x(k) ∈ Rn et u(k) ∈ Rm sont, respectivement, le vecteur des états et le vecteur desentrées du système au tempsk. Le cas linéaire est par conséquent de la forme :

x(k + 1) = Ax(k) +Bu(k)

oùA ∈ Rn×n etB ∈ Rn×m sont des matrices réelles.

Exemple 1.2 (SAT à temps discret)Supposons que dans le réservoir illustré dans la fig-ure 1.1 les mesures du volume et de débit sont seulement valables toutes les unitésT detemps (intervalle d’échantillonnage). Dans un tel cas, nous pouvons décrire le comporte-ment du système uniquement pendant les instants de temps :

0, T, 2T, 3T, . . . , kT, . . .

Ainsi on définit les signaux en temps discretV (k) = V (kT ), q1(k) = q1(kT ) et q2(k) =q2(kT ) dont la variable indépendante estk = 0, 1, . . .

Si∆t = T , alors nous pouvons rapprocher la dérivée par rapport au temps des signaux entemps continu par leurs rapports différentiels :

d

dtV (t) ≈ ∆V

∆t=

V (k + 1)− V (k)

T

2

et par la multiplication des deux côtés parT , l’équation (1.1) nous donne :

V (k + 1)− V (k) = Tq1(k)− Tq2(k). (1.2)

L’équation aux differences ci-dessus représente le lien dynamique entre les signaux entemps discretV (k), q1(k) et q2(k). ⋄

1.2 Systèmes à évènements discrets

Un système à évènements discrets[1, 7] est un système dynamique avec un espace d’étatdiscret et avec des trajectoires d’état par morceaux constants qui évolue conformément àl’occurrence, à intervalles irréguliers généralement inconnus, des évènements physiquesqui déterminent une transition d’état.

L’état d’un tel système peut avoir des valeurs logiques ou symboliques, plutôt que desvaleurs numériques, qui changent en réponse aux évènementsqui peuvent également êtredécrits en termes non numériques. Les automates ou les réseaux de Petri sont deux entreles modèles les plus communs de systèmes à évènements discrets.

Exemple 1.3 (Système à évènements discrets)On considère un robot qui charge des piè-ces mécaniques sur un convoyeur, dont le comportement est décrit par l’automate dans lafigure 1.2. Le robot peut être “inactif”, en train d’effectuer le “chargement” d’une pièceou dans un état de “panne” lorsqu’une pièce est mal positionnée. Les évènements quirégissent son évolution sont :a (saisir une pièce),b (pièce correctement positionnée),c(pièce mal positionnée) etd (pièce repositionnée). ⋄

chargement

b

ainactif

panne

c d

t

t1

inactif

panne

a

état

b a

c

t2 t3 t4

chargement

FIGURE 1.2 – Une machine avec pannes.

Dans un système à évènements discretslogique, le modèle ne précise pas les dates d’oc-currences des évènements qui restent inconnues. Donc, une hypothèse simplificatrice estde ne considérer que l’ordre dans lequel les évènements se produisent, par exemple

w = abac . . .

3

à

moité

plein

a

videba

b

FIGURE 1.3 – Modèle à évènements discrets du réservoir.

Cette simplification est justifiée lorsque le modèle est utilisé pour étudier les propriétésdes évènements dynamiques qui sont indépendant des dates. Par exemple on peut identi-fier les séquences admissibles d’opérations (chaqueb doit être immédiatement précédéepar unea), vérifier l’absence de blocage, etc.

Dans un système à évènements discretstemporisé le modèle précise aussi la structure dutemps. Ces modèles peuvent être ainsi qualifiés de :

a) déterministe :si les dates des évènements sont connus à l’avance ;

b) stochastique :si les dates ne sont pas connues à l’avance à cause des occurrencesaléatoires des évènements.

Dans les deux cas, on considér l’ordre et les dates d’occurrences des évènements, parexemple

wtemp = (a, t1)(b, t2)(a, t3)(c, t4) . . .

Cette description plus détaillé est nécessaire pour étudier les propriétés qui dépendent dutemps. Par exemple on peut déterminer combien de fois dans une heure l’évènementb seproduit (dans l’exemple, ce ci répresent le taux de chargement du robot) ou la fraction dutemps dans laquelle on reste dans un état (dans l’exemple, sile robot est dans l’état depanne il ne peut pas être utilisé).

Alors que l’on peut penser que les systèmes à évènements discrets sont intrinsèque-ment différents des systèmes à avancement temporel, il est souvent le cas d’un systèmephysique qui, en admetant un modèle à avancement temporel, va être décrit par un modèleà évènements discrets où la dynamique à avancement temporelest ignorée. Cette procé-dure, qu’on appelleabstractionpermet de dériver un modèle plus simple qui préserve toutde même les propriétés analysées tout en masquant les détails qui sont sans intérêt.

Exemple 1.4 (Modèle à évènements discrets du réservoir)On considère que le réservoirdécrit dans les exemples 1.1 et 1.2 doit être contrôlé de sorte à garder le niveau de fluidedans un intervalle[hmin, hmax]. Pour cela, on peut utiliser un superviseur qui, en contrôlantles pompes, bloque le débit en entréeq1 lorsque le niveauhmax est atteint et bloque ledébit en sortieq2 lorsque le niveauhmin est atteint. Le comportement de ce superviseurpeut être facilement décrit par le modèle à évènements discrets présent sur la figure 1.3.L’automate de la figure comprend trois états (“haut”, “milieu” et “bas”) et les évènements,qui indiquent le niveau de franchissement des seuilshmin ethmax peuvent être générés parun simple capteur de niveau. ⋄

4

x= q - k [x - Te ] x = - k [ x - Te ]

ON OFF

x 20?

x 22?

FIGURE 1.4 – Modèle graphique du thermostat.

1.3 Systèmes hybrides

Un système hybrideest un système dont le comportement regroupe les dynamiquesdessystèmes à avancement temporelet dessystèmes à évènements discrets.

Certains états prennent des valeurs dens un ensemble continu (par exemple : l’ensembledes nombres réelsR), alors que d’autres prennent des valeurs dans un ensemble discret etfini (par exemple :{ON,OFF}). L’évolution de ces systèmes est décrite par un mélangedes signaux continus et évènementiels.

Exemple 1.5 (Système hybride)Un thermostat doit garder la températurex(t) d’une piècecomprise entreTON = 20 ◦C etTOFF = 22 ◦C, mettent en marche ou en arrêt une pompeà chaleur. La pièce échange de la chaleur avec l’environnement externe à la températureTe < TON .

Quand la pompe à chaleur est en arrêt, le flux thermique est−k[x(t) − Te] [J/s] oùk estun coefficient et le signe négatif montre que six > Te alors il y a une perte de chaleur dela pièce vers l’environnement externe. Le changement de la température durant l’unité detemps, c.à.d.x(t), est égal au rapport entre le flux de chaleur et la capacité thermique dela pièce. Dans un but de simplicité, nous supposons la capacité thermique être unitaire, etnous pouvons aussi dire dans ce cas là que la température diminue selon :

x(t) = −k[x(t)− Te].

Quand la pompe à chaleur est en marche, elle produit un flux thermique égal àq [J/s]qu’on suppose plus grand que la perte de chaleur, ainsi la température augmente selon :

x(t) = q − k[x(t)− Te].

Le thermostat active la pompe (en état de marche) quand la température est inférieure ouégale àTON , et l’arrête quand la température est supérieure ou égale àTOFF .

Le comportement de ce système peut être décrit par le modèle graphique montré dans lafigure 1.4. Si nous ignorons les dynamiques dans les cases, nous pouvons reconnaître un

5

Systèmes hybrides

Systèmes à avancement

temporel (SAT)

Systèmes à évènements

discrets (SED)

SAT à temps

continu

SAT à temps

discret

SED

logiques

SED

temporisés

déterministes stochastiques

FIGURE 1.5 – Classification des systèmes.

simple modèle à évènements discrets qui sur l’occurrence dequelques évènements (tem-pérature traversant une seuil) décrit l’opération du thermostat. Si nous nous concentronssur les dynamiques dans les deux cases du modèle graphique, nous pouvons reconnaîtreun système à avancement temporel à temps continu qui est associé au profil de la tem-pérature.

L’état de ce système au tempst est décrit par la coupley(t) = (ℓ(t), x(t)) dont on recon-nait deux composantes :– l’état discretℓ(t) ∈ {ON,OFF} dont l’évolution est régie par l’occurrence des évène-

ments ;– l’état continux(t) ∈ R dont l’évolution est régie par une équation différentielle.On remarquera que l’évolution évènementielle et celle continue sont liées entre eux. Lechangement d’état discret modifie la dynamique continue (l’éq. différentielle), tandis quela dynamique continue déclenche l’occurrence des évènements (x ≥ TOFF etx ≤ TON ).

⋄

1.4 Classes des systèmes dynamiques

Un résumé des différentes classes que nous avons décrites jusqu’à présent est schématisédans la figure 1.5. Nous pouvons voir que du haut vers le bas nous passons d’une classegénérale à une sous-classe. Notons que dans la figure, nous désignons ces classes commeétant des systèmes à avancement temporel, des systèmes à évènements discrets ainsi quedes systèmes hybrides. Cependant, il faut garder à l’espritque cette taxonomie concerneles modèles parce que les termes “à avancement temporel”, “àévènements discrets” ou“hybride” devraient être utilisés pour classifier la description mathématique plutôt quel’objet physique. Souvent le même système (c.à.d l’objet physique) peut être décrit parplusieurs modèles.

6

Chapitre 2

Langages Formels

Cette section va introduire les notions élémentaires de la théorie des langages formels, àsavoir les concepts d’alphabet, demotet delangageainsi que les principales opérationssur les mots et les langages. Pour en savoir plus, nous nous référons à [4, 3].

2.1 Les alphabets et les mots

Définition 2.1 Un alphabetE est un ensemble fini non vide desymboles(ou lettres). Lenombre de symboles qu’il contient est appelé sacardinalitéet dénoté par|E|. N

Exemple 2.1On considère les alphabets

E1 = {0, 1}, E2 = {a, b, c, . . . x, y, z} and E3 = {♣,♦,♥,♠}. (2.1)

Le premier alphabetE1 a cardinalité|E1| = 2, . Il est composé des symboles0 et1, qu’onutilise pour écrire les nombres binaire.

Le deuxième alphabetE2 a cardinalité|E2| = 26. Il est composé des lettres minusculeslatines. Le troisième alphabetE3 a cardinalité|E3| = 4. Il est composé des enseignes (oucouleurs) du jeu de cartes. ⋄

Définition 2.2 Un motw défini sur un alphabetE est une suite de symboles deE. Lenombre de symboles qui compose la suite est appelélongueurdu motw et dénoté par|w|.On dénote par|w|e le nombre de fois que le symbolee est présent dansw. N

Exemple 2.2On considère les trois alphabets définis dans l’exemple (2.1). Le motw1 =00110 défini surE1 a longueur|w1| = 5. Le motw2 = mucem défini surE2 a longeur|w2| = 5. Dans ce mot :|w2|m = 2, parce que le symbolem y apparaît deux fois ;|w2|c =1, parce que le symbolec y apparaît une fois.

Le motw3 = ♣♣♣ défini surE3 a longueur|w3| = 3. ⋄

7

Définition 2.3 Le mot vide, de longueur0, est notéε et est défini sur n’importe quelalphabet.

Définition 2.4 On dénoteE∗ l’ensemble de tous les motsdéfinis sur un alphabetE. N

On remarquera que, bien queE aie cardinalité finie, l’ensembleE∗ a toujours a cardinalitéinfinie.

Exemple 2.3On considère l’alphabetE = {a, b, c}. Pour déterminer l’ensembleE∗ onpeut énumèrer tous les mots surE, inclus le mot vide, dans un ordre croissant :– ε : mot de longueur zéro ;– a, b, c : mots de longueur1 (à noter : un symbole est aussi un mot) ;– aa, ab, ac, ba, bb, bc, ca, cb, cc : les mots de longueur2 ;– aaa, aab, . . ., ccb, ccc : les mots de longueur de3 ;– etc.,. . .

⋄

2.2 Les opérations sur les mots

La première opération qu’on considéré sur les mots est une loi de composition binaire1

qu’on appelleconcaténation.

Définition 2.5 La concaténationde deux motsw1 ∈ E∗ et w2 ∈ E∗ est un nouveaumotw = w1 · w2 ∈ E∗ composé par la suite des symboles dew1 suivie par la suite dessymboles dew2. N

Exemple 2.4La concaténation du motw1 = a avec le motw2 = bba donneraw =w1 · w2 = abba. ⋄

Le symbole· utilisé pour dénoter la concaténation est souvent omis, et on écritw1w2 aulieu de ofw1 · w2. La longueur du mot obtenue par concaténation est égale à la sommedes longueurs des deux mots qui la composent, c.à.d.,|w1w2| = |w1|+ |w2|.La concaténation est une opérationassociative2, c.à.d.,(w1w2)w3 = w1(w2w3) = w1w2w3.Par exemple, siw1 = he,w2 = ll etw3 = 0, leur concaténation estw = w1w2w3 = hello.

A l’opposé, la concaténation n’est pas une opérationcommutative, c.à.d., généralementw1w2 6= w2w1. Par exemple, siw1 = ab etw2 = cd, clairementabcd 6= cdab.

L’ élément neutrede cette opération est le mot videε, c.à.d. : pour toutw ∈ E∗ on awε = εw = w.

1. Une opération binaire est une opération à deux arguments ou opérandes, telle que l’addition desnombres réelsf(a, b) = a+ b.

2. En tant que telle, elle peut être appliquée à plus de deux mots.

8

On utilise la même notation de l’arithmétique classique, à savoir l’exponentielle puissancek, pour dénoter la concaténation d’un symbole pourk fois. Par exemple, le motaabbb peutaussi s’écrirea2b3. Pour tout symbolee ∈ E on dénotee0 = ε, car on aeke0 = ek+0 = ek

(donce0 est l’élément neutre pour la concaténation).

La deuxième opération sur les mots qu’on va considérer, est une loi de composition un-aire3 : la projection.

Définition 2.6 Soit le motw ∈ E∗ et un alphabetE ⊆ E. La projectiondew sur E,notéew ↑ E, est la suite obtenue dew en guardant les symboles qui appartiennent àE eteffaçant les autres symboles. N

Exemple 2.5Soit E = {a, b, c} et E = {a, b}. On considère le motw = cabccb, :sa projection surE est obtenue en guardant lesa et b et en effaçant tous lesc et doncw ↑ E = abb. ⋄

On termine la section par la dèfinition suivante.

Définition 2.7 Si le motw ∈ E∗ peut s’écrirew = uvz ou u, v, z ∈ E∗, alors le motuest appelépréfixedew, le motv est appelésous-chainedew et le motz est appelésuffixedew. Si u est un préfixe dew on écritu � w. N

Exemple 2.6Soit le motw = abcd. Ses préfixes sontε, a, ab, abc et abcd. Ses suffixessontε, d, cd, bcd etabcd. Ses sous-chaines sont : tous ses préfixes, tous ses suffixes et leschainesb, c et bc. ⋄

2.3 Langages

Un langage est un ensemble de mots.

Définition 2.8 Un langageL défini sur un alphabetE est un ensemble de mots sur cetalphabet. Sacardinalité, à savoir le nombre de mots qu’il contient, est notée|L|. N

Exemple 2.7Soit l’alphabetE = {a, b}, on considère les langages suivants :

L1 = {aab, aa, bbba}, L2 = {a, b} = E, L3 = {ε, a}, L4 = {ε},L5 = {w ∈ E∗ | |w| = 5}, L6 = {w ∈ E∗ | |w| > 3}, L7 = ∅, L8 = E∗.

Le langageL1 se compose de trois mots, donc sa cardinalité est|L1| = 3. Le langageL2 se compose de deux mots, de longueur 1 et coïncide avec l’alphabet. Le langageL3

3. Une opération unaire est une opération à un seul argument,telle que l’élévation au carré des nombresréelsf(a) = a2.

9

se compose de deux mots, y compris le mot vide. Le langageL4 ne se compose que dumot vide. Le langageL5 se compose de tous les mots de longueur cinq. Le langageL6 secompose de tous les mots de longueur supérieure à 3. Le langageL7 est l’ensemble videet ne contient pas de mots. Le langageL8 se compose de tous les mots définis surE. ⋄

Notons que un langage peut être vide (autrement dit, sa cardinalité est égale à zéro, commele langageL7 définit dans l’exemple) ou il peut avoir une cardinalité finie(comme leslangagesL1, L2, L3, L4 etL5 dans l’exemple) ou même avoir cardinalité infinie (commele langageL6 etL8dans l’exemple). Un langage peut être décrit explicitementénuméranttous les mots (les quatre premiers langages dans l’exemple)ou en utilisant une notationensembliste (les quatre derniers langages dans l’exemple). Notons aussi que l’alphabetpeut aussi être considéré comme un langage particulier composé de mots de longueur1(ce qui est le cas du langageL2 dans l’exemple).

Etant donné que les langages sont des ensembles de mots, il est possible de comparerdeux langages à travers les relations d’inclusion⊆ et inclusion stricte(.

Exemple 2.8Le langageL1 = {a} est strictement inclus dans le langageL2 = {a, aa}.Aucun de ces deux langages est inclus dans le langageL3 = {aaa}. ⋄

Si L est un langage sur l’alphabetE cela implique∅ ⊆ L ⊆ E∗.

2.4 Les opérations sur les langages

Les opérations binaires usuelles, telles que l’union et de l’intersection, peuvent être ap-pliquées aux langages.

Définition 2.9 Soit L1 ⊆ E∗1 et L2 ⊆ E∗

2 deux langages. On admet queE = E1 ∩ E2

et E = E1 ∪ E2 sont l’intersection et l’union de leurs alphabets respectivement. Nousdéfinissons les langages suivantes :– l’ intersectiondeL1 etL2 notéeL1 ∩ L2 = {w ∈ E∗ | w ∈ L1, w ∈ L2} ;– l’uniondeL1 etL2 notéeL1 ∪ L2 = {w ∈ E∗ | w ∈ L1 ∨ w ∈ L2} 4. N

Exemple 2.9Si L1 = {ε, a} et L2 = {a, b, ab}, doncL1 ∩ L2 = {a} et L1 ∪ L2 ={ε, a, b, ab}. ⋄

Les deux opérations sont associatives et commutatives. L’élément neutre de l’opérationd’intersection est le langageE∗, donc on peut dire que pour toutL ⊆ E∗ on aL∩E∗ = L.L’élément neutre de l’opération d’union est le langage∅, donc on peut dire que pour toutL ⊆ E∗ on aL ∪ ∅ = L.

4. Ici ∨ représente le OU logique.

10

L’opération deconcaténation, définie sur les mots, peut être redéfinie en tant qu’opérationsur les langages.

Définition 2.10 Étant donnés deux langagesL1, L2 ⊆ E∗ nous définissons laconcaténa-tion deL1 etL2 comme le langage

L1L2 = {w = w1w2 ∈ E∗ | w1 ∈ L1, w2 ∈ L2},

composé de tous les mots qui sont la concaténation d’un mot enL1 avec un mot enL2. N

Exemple 2.10Si L1 = {ε, a} et L2 = {a, b, ab} doncL1L2 = {ε · a} ∪ {ε · b} ∪ {ε ·ab}∪ {a · a}∪ {a · b}∪ {a · ab} = {a, b, aa, ab, aab}. Le motab peut être obtenu de deuxmanières différentes : soit concaténationε avecab ou concaténationa avecb. ⋄

L’opération de concaténation sur les langages est associative et non commutative. Sonélément neutre est le langage qui se compose du mot vide{ε}, à savoir, pour toutL ⊆ E∗

on aL{ε} = {ε}L = L.

Il est également usuel de désigner pour tout langageL ⊆ E∗ : L0 = {ε}, L1 = L,L2 = LL, etc.

Enfin, nous notons que l’opération de concaténation est distributive par rapport à l’union.Autrement dit,(L1 ∪ L2)L3 = L1L3 ∪ L2L3 et aussiL1(L2 ∪ L3) = L1L2 ∪ L1L3.

Une opération unaire sur les langages est l’étoile de Kleene.

Définition 2.11 Étant donné un langageL ⊆ E∗, sonétoile de Kleene(parfois appeléefermeture de Kleeneou encorefermeture itérative) est le langage

L∗ = {ε} ∪ L ∪ LL ∪ LLL ∪ · · · =∞⋃

k=0

Lk,

constitué de tous les mots obtenus par la concaténation de mots àL un nombre quelconquede fois, y compris zéro. N

Exemple 2.11Soit L = {bb} un langage surE = {b}. Son étoile de Kleene estL∗ ={ε} ∪ {bb} ∪ {bbbb} ∪ · · · = {(bb)n | n ≥ 0}. ⋄

Notez que l’étoile de Kleene d’un alphabet (vu comme un langage) génère l’ensemble detous les mots possibles sur cet alphabet, ce qui justifie la notationE∗ utilisé pour désignercet ensemble.

D’autres opérations unaires sur les langages sont laclôture préfixeet lecomplément.

Définition 2.12 Étant donné un langageL ⊆ E∗, saclôture préfixe(ou fermeture préfixe)est le langage

L = {u ∈ E∗ | il existew ∈ L : u � w}

11

composé de tous les préfixes de mots dansL.

NormalementL ⊆ L. Un langageL est appeléclos par préfixesiL = L. N

Exemple 2.12Soit L1 = {ε, a, aa} et L2 = {a, b, ab}. On aL1 = L1 et doncL1 estclos par préfixe. Au contraire, on aL2 ( L2 = {ε, a, b, ab} et doncL2 n’est pas clos parpréfixe. ⋄

Définition 2.13 Étant donné un langageL ⊆ E∗, soncomplémentest le langage

∁L = {w ∈ E∗ | w 6∈ L}composé de tous les mots qui ne font pas partie deL. Nous pouvons également écrire∁L = E∗ \ L. N

Exemple 2.13Considérons le langageL1 = {ε, a, aa} surE = {a} : son complémentest∁L1 = {an | n ≥ 3}. ⋄

La dernière opération que nous considérons, appeléeproduit synchrone, joue, commenous le verrons, un rôle important lors de la description du comportement d’un systèmecomposé de plusieurs sous-systèmes.

Définition 2.14 Étant donnés deux langagesL1 ⊆ E∗1 et L2 ⊆ E∗

2 soit E = E1 ∪ E2

l’union de leurs alphabets. Leproduit synchronedeL1 etL2 est le langage

L1 ‖ L2 = {w ∈ E∗ | w ↑ E1 ∈ L1, w ↑ E2 ∈ L2},composé de tous les mots surE dont la projection surE1 est un mot deL1 et dont laprojection surE2 est un mot deL2. N

Exemple 2.14ConsidéronsE1 = {a, b}, E2 = {b, c}, L1 = {abn | n ≥ 0} et L2 ={cbcnb | n ≥ 0}. Le produit synchrone deL1 etL2 estL = {acbcnb | n ≥ 0} ∪ {cabcnb |n ≥ 0}. A noter que la projection deL surE1 est le langage{abb} ( L1, tandis que laprojection deL surE2 est le langage{cbcnb | n ≥ 0} = L2. ⋄

Comme un cas particulier, si les alphabets des deux langagescomposées sont les mêmes,l’opération de produit synchrone est équivalente à l’intersection. En fait, siE1 = E2 = Epour chaquew ∈ E∗ on aw ↑ E1 = w ↑ E2 = w et donc

L1 ‖ L2 = {w ∈ E∗ | w ↑ E1 ∈ L1, w ↑ E2 ∈ L2}= {w ∈ E∗ | w ∈ L1, w ∈ L2} = L1 ∩ L2.

L’opération de produit synchrone est associative et commutative.

Nous concluons en observant que tous les opérations binaires que nous avons définis dansle présent paragraphe sont associatives ; par conséquent, elles peuvent naturellement êtreétendues à plus de deux langages. DoncL1 ‖ L2 ‖ L3 = (L1 ‖ L2) ‖ L3 = L1 ‖ (L2 ‖L3).

12

Chapitre 3

Automates finis déterministes (AFD)

Dans la section précédente, nous avons donné quelques exemples de langages formelsdéfinis ou en décrivant leurs mots ou en utilisant la notationdes ensembles. Cependant, ilest également possible de définir un langage à travers un générateur, à savoir, une structureà laquelle un langage peut être associé. Un telgénérateurest unmodèle à évènementsdiscrets. Dans cette section, un modèle particulier, appeléautomate fini déterministe, estprésenté. Ce modèle est basé sur deux éléments : lesétatset lestransitions. Il décrit defaçon naturelle le comportement d’un système dynamique quiévolue d’un état à l’autrelors de l’occurrence d’évènements discrets. Pour en savoirplus, nous nous référons à[4, 1].

3.1 Définition d’un automate fini déterministe

Définition 3.1 Un automate fini déterministe(AFD) est un quintuplet

G = (X,E, δ, x0, Xm)

où :– X est un ensemble fini d’états;– E est un alphabet ;– δ : X × E → X est unefonction de transition1 ;– x0 ∈ X est unétat initial ;– Xm ⊆ X est un ensemble d’états finaux(ou états marqués). N

Nous utilisons les AFD pour décrire les systèmes à évènements discrets. L’alphabet représentel’ensemble des évènements tandis que la fonction de transition spécifie la dynamique del’automate : six = δ(x, e) alors l’occurrence de l’évènemente lorsque l’état actuel del’automate estx, conduit à l’étatx.

1. Nous considérons icifonctions partielles, c’est à dire, il peut y avoir des couples(x, e) ∈ X × E detelle sorte queδ(x, e) ne soit pas défini.

13

x0 x1 x2

a b c

d

d

FIGURE 3.1 – Exemple d’automate fini déterministe

Un automate peut être décrit par un graphe dans lequel chaqueétat correspond à un noeudet est représenté par un cercle : en particulier, l’état initial est représenté par un cercleavec une flèche d’entrée, et un état final par un double cercle.Si x = δ(x, e) il y aura uneflèche dirigé à partir du noeudx au noeudx marqués avec le symbolee pour représenterla transition dex à x, et cette flèche est appelée unee-transition.

Exemple 3.1La figure 3.1 montre la structure graphique d’un automate avec ensembled’étatsX = {x0, x1, x2}, alphabetE = {a, b, c, d}, état initialx0 et un ensemble d’étatsfinauxXm = {x0}. La fonction de transition est donnée par le tableau suivant:

δ a b c d

x0 x1

x1 x2 x0

x2 x2 x0

⋄

Dans ce tableau, par exemple, la valeurx1 à l’intersection entre la lignex0 et la colonnea indique queδ(x0, a) = x1. Une case vide, comme celle à l’intersection entre la lignex0

et la colonneb, indique que la transition correspondante n’est pas définie. La c-transitiondu noeudx2 vers lui-même est appelé uneboucle. �

L’automate dans la figure 3.1 décrit le comportement d’un utilisateur d’une base de don-nées en ligne. Quand l’utilisateur n’est pas connecté à la base de donnée (étatx0) il peutse connecter (évènementa). Une fois la communication établie (étatx1) il doit s’identi-fier avec ID et mot de passe (évènementb). Quand il a bien été identifié (étatx2) il peutà plusieurs reprises interroger la base de donnée pour obtenir des informations (évène-mentc). A chaque moment l’utilisateur peut interrompre la communication (évènementd). Il y a un seul état finalx0, pour montrer que l’utilisateur ne dois pas être connecté àla fin d’une période de travail. L’interprétation de chaque état et transition de l’AFD enfigure 3.1 est aussi montrée dans la Table 3.1.

Dans un AFD chaque transition est associée à un évènement. Ainsi, les étiquettes destransitions sortantes d’un état donnéx spécifient quels évènements peuvent se produire

14

Etats

x0 non connecté

x1 communication établie

x2 identifié

Evènements

a connection

b identification

c interrogation

d déconnection

TABLE 3.1 – Interprétation de l’automate en figure 3.1

dans cet état.

Définition 3.2 Soit un AFDG = (X,E, δ, x0, Xm), l’ensemble des évènementsactifsdans l’étatx ∈ X est

A(x) = {e ∈ E | δ(x, e) est défini}.

Pour indiquer quee ∈ A(x) on écrit aussiδ(x, e)!, ce qui signifie que la fonctionδ estdéfinie pour le couple(x, e). N

Nous avons mentionné que dans un AFD la fonction de transition δ est une fonction par-tielle, à savoir, pour certainsx ∈ X et certainse ∈ E il peut ne pas exister un évènemente en sortie de l’étatx (ou de manière équivalenteA(x) ( E). Notez, cependant, que l’onne peut pas avoir deux ou plusieurs transitions avec la même étiquette en sortie d’un étatx.

3.2 Comportement d’un automate fini déterministe

Le comportement d’un automate est donné par toutes ses évolutions possibles, caractérisépar sescalculs.

Définition 3.3 Soit un AFDG = (X,E, δ, x0, Xm), on définitcalcul de longueurk unséquences d’états et de transitions

xj0

e1−→ xj1

e2−→ · · ·xjk−1

ek−→ xjk

où pour touti = 0, . . . , k on axji ∈ X et pout touti = 1, . . . , k on axji = δ(xji−1, ei), à

savoir, l’occurrence de l’évènementei à partir de l’étatxji−1amène a l’étatxji.

Un tel calcul départ de l’étatxj0, produit un motw = e1e2 · · · ek et conduit l’étatxjk . N

Exemple 3.2Un calcul possible pour l’automate dans la figure 3.1 est le suivant :

x0a−→ x1

b−→ x2c−→ x2

c−→ x2.

15

Ce calcul, qui départ de l’étatx0, produit un motw = abcc et conduit à l’étatx2. Il décritune évolution dans laquelle l’utilisateur établie une connexion avec la base de donnée (a)et, après être identifié (b), interroge la base de donnée pour obtenir deux records (cc). ⋄

Notez qu’un calcul peut départir de tout état, et pas nécessairement de l’état initial.

Exemple 3.3Un autre calcul pour l’automate dans la figure 3.1 est le suivant :

x2c−→ x2

c−→ x2d−→ x0

a−→ x1.

⋄

Commeδ est une fonction, il ne peut y avoir deux calculs différentesqui partent du mêmeétat et génèrent le même mot. Pour décrire les calculs d’un AFD dans une manière pluscompacte, nous introduisons la notation suivante.

Définition 3.4 Soit un automate fini déterministe AFDG = (X,E, δ, x0, Xm), la ferme-ture transitive et réflexivede la fonction de transitionδ est la fonctionδ∗ : X × E∗ → Xtel queδ∗(x, w) = x si il existe un calcul

xe1−→ xj1

e2−→ · · ·xjk−1

ek−→ x

qui départ dex, produit un motw = e1e2 · · · ek et conduit à l’étatx. Pour indiquer qu’il ya un calcul qui produitw à partir dex on utilise également la notationδ∗(x, w)! signifiant“δ∗(x, w) est dé finie”.

Par convention,δ∗(x, ε) = x pour toutx ∈ X, à savoir, à partir d’un état, produisant lemot vide l’automate reste dans le même état. N

Exemple 3.4Pour l’automate dans la figure 3.1 on aδ∗(x0, abcc) = x2. ⋄

3.3 Langages d’un automate fini déterministe

A chaque calcul d’un automate est associé un mot de l’alphabet E. Par conséquent, sil’on considère l’ensemble des calculs qui départent de l’état initial, l’ensemble des motscorrespondant définit un langageL ⊆ E∗.

Définition 3.5 SoitG = (X,E, δ, x0, Xm) un AFD. On dit qu’un motw ∈ E∗ est :– généréparG si δ∗(x0, w) est defini, à savoir, il existe un calcul qui produitw à partir

de l’état initial ;– acceptéparG si δ∗(x0, w) = x ∈ Xm, à savoir, il existe un calcul qui produitw à partir

de l’état initial et conduit à un état final. N

16

Exemple 3.5On considere l’automate dans la figure 3.1. Le motabcc est généré parcequeδ∗(x0, abcc) = x2, mais il n’est pas accepté parce que l’étatx2 n’est pas un état final.Le motad est accepté (et donc aussi généré) parce queδ∗(x0, ad) = x0 et quex0 est unétat final. Enfin, le motac n’est pas généré (et donc pas acceptée) parce queδ∗(x0, ac)n’est pas définit : à partir de l’état initial l’occurrence del’évènementa conduit à l’étatx1, dans lequel l’évènementc n’est pas actif. ⋄

Dans la précédente définition,w peut être le mot videε. Le mot vide peut toujours êtregénéré, et il est accepté t seulement siδ∗(x0, ε) = x0 ∈ Xm, à savoir, si l’état initial estaussi l’état final.

Par inspection de la représentation graphique d’un AFD, nous pouvons dire quew estgénéré s’il y a un chemin direct dans le graphe qui départ de l’état initial et de telle sorteque les étiquettes le long de ses arcs formentw. Si le noeud terminal d’un tel chemin estun état final,w est également accepté.

Définition 3.6 SoitG = (X,E, δ, x0, Xm) un AFD. On associe à lui deux langages :– le langage généré, à savoir, l’ensemble de tous les mots générés :

L(G) = {w ∈ E∗ | δ∗(x0, w)! } ⊆ E∗;

– le langage accepté, à savoir, l’ensemble de tous les mots acceptés :

Lm(G) = {w ∈ E∗ | δ∗(x0, w) ∈ Xm} ⊆ L(G).

N

Le langage généré décrit toutes les évolutions possibles d’un système. Le langage acceptédécrit ces évolutions qui correspondent au complétement decertaines tâches. Par exemple,pour l’automate de la figure 3.1 qui décrit une machine, le langage accepté décrit desévolutions qui conduisent à l’étatx0, à savoir, l’état dans lequel l’utilisateur n’est pasconnecté.

A noter que le langage généré par un AFD est toujours clos par préfixe, à savoirL(G) =L(G) : en fait, si un mot peut être généré alors tous ses préfixes peuvent également êtregénérés.

A l’inverse, le langage accepté par un AFD n’est pas nécessairement clos par préfixe,car les préfixes d’un mot accepté ne doivent pas forcement être acceptés. Donc on a :Lm(G) ⊆ Lm(G). On peut facilement prouver queLm(G) = Lm(G) si et seulement siXm = X, à savoir, tous les états deG sont finaux.

Exemple 3.6Considérons l’AFD dans la figure 3.1. Le motad est accepté, mais sonpréfixea ne l’est pas. ⋄

En outre, si un mot peut être accepté, alors ce mot et tous ses préfixes peuvent aussi êtregénérés : cela implique queLm(G) ⊆ L(G) est toujours vraie.

17

Par combinaison de toutes les expressions précédentes, on peut écrire pour tout AFDG :

Lm(G) ⊆ Lm(G) ⊆ L(G) = L(G).

Nous concluons cette section définissant la classe des langages acceptées par les AFD.

Définition 3.7 Laclasse des langages acceptéspar des AFD sur un alphabetE est l’ensem-ble

LAFD = {L ⊆ E∗ | (il existe un AFDG) : L = Lm(G)},qui se compose de tous les langages qui peuvent être acceptéspar un quelque AFD. N

La définition ci-dessus ne prend en compte que la classe deslangages acceptéspar desAFD, et non la classe deslangages généréspar des AFD, que nous noteronsL′

AFD. Onpeut facilement montrer, toutefois, qu’on aL′

AFD ( LAFD, à savoir, la classe des langagesacceptés par un AFD contient strictement la classe des langages générés par des AFD.

Pour prouver l’inclusionL′AFD ⊆ LAFD il faut observer d’abord que si un langage appar-

tient à la classeL′AFD alors il appartient aussi à la classeLAFD. En effet, si un langage

est généré par un AFDG, il existe aussi un AFDG′ qui l’accepte :G′ est obtenu à partirdeG en redéfinissant tous les états comme finaux de sorte que tout mot généré parG estégalement accepté parG′.

Pour prouver que l’inclusion est stricte, il suffit de montrer qu’il existe des langages dansLAFD et non dansL′

AFD. Tel est le cas, parce que un langage accepté par un AFDG oùtous les états ne sont pas finaux, à savoir,Xm ( X, n’est pas clos par préfixe, et donc, celangage n’appartient pas àL′

AFD étant donné que tous les langages générées par des AFDsont clos par préfixe.

3.4 Propriété d’un automate fini déterministe

Dans cette partie on définit les propriétés principales d’unautomate, qui sont intéressantesvis-à-vis du système décrit per ce modèle.

Définition 3.8 SoitG = (X,E, δ, x0, Xm) un AFD. Un étatx ∈ X est dit :– accessible depuis un étatx ∈ X si il existe un motw ∈ E∗ tel queδ∗(x, w) = x.

Un étatx accessible depuis l’état initialx0 est appelé tout simplementaccessible(ouréalisable) ;

– co-accessible vers un étatx ∈ X si il existe un motw ∈ E∗ tel queδ∗(x, w) = x.Un étatx co-accessible vers un état finalx ∈ Xm, x est tout simplement appeléco-accessible(ou co-réalisable) ;

– bloquantsi il est accessible mais pas co-accessible ;– mort si A(x) = ∅, c’est à dire il n’existe aucune transition possible à partir de l’étatx.

N

18

Il faut noter que les étatsbloquantsetmortsont différentes propriétés à ne pas confondre.Un état mort peut ne pas être bloquant, si il est final2. Un état bloquant peut ne pas êtremort, c’est le cas de l’étatx2 pour l’AFD dans la figure 3.2(a).

En regardant le graphe d’un automate on peut dire (cf. AnnexeB) qu’un étatx est :– accessible depuis un étatx : si il existe un chemin direct dex versx .– co-accessible vers un étatx si il existe un chemin direct dex versx.– mort si il n’y a aucune transition qui sort depuis celui-ci.On définit les propriétés suivantes pour un automate.

Définition 3.9 Un AFD G est dit :– accessible(ou réalisable) si tous ses états sont accessibles ;– co-accessible(ou co-réalisable) si tous ses états sont co-accessibles ;– non-bloquantsi tous ses états sont non bloquants ;– émondés’il est accessible et co-accessible ;– réversiblesi tout état accessible est aussi co-accessible ver l’état initial. N

En observant le graphe d’un automate on peut dire que l’automate est ’bloquant’ si etseulement si il existe une composante ergodique (=absorbant) accessible, qui ne contientpas des états marqués (une fois qu’on atteint cette composante on ne peut plus atteindrel’état final).

Enfin, on peut montrer que l’automate est réversible si et seulement si l’état initial appar-tient à une composante ergodique.

Exemple 3.7Dans l’AFD dans la figure 3.2(a) tous les états sont accessibles, seuls lesétatsx0 etx1 sont co-accessibles etx3 est mort. C’est pourquoi cet automate et accessible,non co-accessible et bloquant. Dans l’AFD dans la figure 3.2(b) tous les états sont co-accessibles mais justex0 etx1 sont accessibles ; donc cet automate est non-accessible, co-accessible et non-bloquant. Dans l’AFD dans la figure 3.2(c) tous les états sont accessibleset co-accessibles. Cet automate est donc émondé. Aucun des AFD de la figure 3.2 n’estréversible. Un exemple de AFD réversible est donné dans la figure 3.1. ⋄

L’accessibilité nous permet d’étudier quels sont les possibles états dans lesquels un sys-tème peut se trouver après une évolution qui part de l’état initial. Un état bloquant représenteune (souvent indésirable) condition depuis laquelle le système ne peut pas évoluer versun état final, et donc on ne pas finaliser une tâche. Un état mortreprésente une condi-tion à partir de laquelle aucun évènement ne peut survenir. La réversibilité caractérise dessystèmes qui peuvent toujours être ramenés vers leur état initial.

D’après la Definition 3.6, on peut constater que pour tout AFDG on aLm(G) ⊆ L(G).On déduit le résultat suivant.

Proposition 3.1 Un AFDG est non-bloquant siLm(G) = L(G).

2. Un état finalx ∈ Xm est co-accessible par définition, parce queδ∗(x, ε) = x ∈ Xm.

19

x0

x1

x2

b

a

(a)

a

x0

x1

x2

b

a

(b)

a

x0

x1

b

a

(c)

a

x3

FIGURE 3.2 – (a) Un automate accessible, non co-accessible et bloquant ; (b) un automatenon-accessible, co-accessible et non-bloquant ; (c) un automate émondé.

Preuve.

(Si) SiLm(G) = L(G) alors tout motu ∈ L(G) est aussi préfix d’un mot accepté, c’est àdire, pour tout motu il existe un motv tel queuv ∈ Lm(G) est accepté. Ainsi pour toutétat accessiblex = δ∗(x0, u), il existe un motv tel queδ∗(x, v) soit un état final, et celaprouve que tout état final est co-accessible.

(Seulement si) SiLm(G) ( L(G) alors il existe un motu ∈ L(G) qui n’est pas préfixed’un mot accepté, c’est à dire, il existe aucun motv tel queuv ∈ Lm(G) soit accepté.Ainsi si x = δ(x0, u) est un état auquel on arrive en générantu, alors pour cet état là iln’existe pas un motv tel queδ∗(x, v) soit un état final. Par conséquentx est accessiblemais pas co-accessible : il est donc bloquant. �

Exemple 3.8Dans l’AFD bloquant de la figure 3.2(a) on peut vérifier queLm(G) ={ban | n ≥ 0} etLm(G) ( {ε, a, aa} ∪ {ban | n ≥ 0} = L(G).

Au contraire les AFD des figure 3.2(b) et figure 3.2(c) sont non-bloquants car on aLm(G) = {ban | n ≥ 0} etLm(G) = {ε} ∪ {ban | n ≥ 0} = L(G). ⋄

Un automateG qui n’est pas accessible ou pas co-accessible, peut toujours être émondé sion enlève tous les états qui ne sont pas accessibles ou pas co-accessibles et les transitionsqui mènent vers eux ou sortent d’eux.

Définition 3.10 Soit un AFDG = (X,E, δ′, x0, Xm) tel queLm(G) 6= ∅ qui est à la foisnon-accessible et non co-accessible. Sacomposante émondéeest l’AFD

G′ = émondé(G) = (X ′, E, δ′, x0, X′m),

avec– X ′ = {x ∈ X | x est accessible et co-accessible dansG } ;– δ′(x, e) = δ(x, e) si x ∈ X ′ et δ(x, e) ∈ X ′ sinon il n’est pas défini ;– X ′

m = Xm ∩X ′.Cet automate accepteLm(G

′) = Lm(G), et généreL(G′) = Lm(G′) = Lm(G). N

20

Exemple 3.9En émondant l’AFD en figure 3.2(a) ou celui en figure 3.2(b) on obtientl’AFD dans la figure 3.2(c). ⋄

Il faut constater que le fait d’émonder un AFD ne change pas lelangage accepté. De plus,l’émondement d’un AFD non-bloquant ne change même pas le langage généré, mais justesupprime les états non-accessibles. Cependant, l’émondement d’un AFD bloquant changenécessairement le langage généré.

3.5 Automates comme reconnaisseurs des séquences

La théorie des langages formels ne prend généralement en considération qu’un seul typede langage AFD : le langage accepté. Ceci est parce que cette théorie ne considère pas unautomate comme unsystème dynamiquequi génère spontanément des évènements, maisplutôt comme un dispositif pourreconnaitre séquencebien formées. Dans cette perspec-tive, un AFD est guidé par des symboles lus à partir d’une bande d’entrée : dépendant deson état actuel et du symbole lu à partir de la bande, l’automate exécute une transitionvers un nouvel état, et accepte tout mot qui amène à un état final.

Si l’on voit un AFD comme un dispositif guidé par des symbolesd’entrée, il est nécessaired’admettre que tout symbole peut être lu indépendamment de l’état actuel de l’automate.Ceci est formalisé avec la notion d’automate complet.

Définition 3.11 L’AFD G = (X,E, δ, x0, Xm) est appelécompletsi la fonction de tran-sition δ(x, e) est défini pour tout étatx ∈ X et tous les symbolese ∈ E ou, de façonéquivalente, si pour toutx ∈ X on aA(x) = E. N

Exemple 3.10L’AFD a la figure 3.1 n’est pas complet parce que, par exemple,δ(x0, b)n’est pas défini : en effetA(x0) = {a} ( E. ⋄

On notera que siG est un automate complet alorsL(G) = E∗.

Il est toujours possible decompléterun AFD avec l’algorithme suivant :

Algorithme 3.1 Réalisation d’un AFD completEntrée :Un AFD non completG = (X,E, δ, x0, Xm).Sortie :Un AFD completG′ = (X ′, E ′, δ′, x′

0, X′m) avecLm(G

′) = Lm(G) etL(G′) =E∗.

1. SoitX ′ = X ∪{xc}, à savoir, l’ensemble des états deG′ inclut l’ensemble des étatsdeG avec l’ajout d’un nouvel étatxc 6∈ X .

2. SoitE ′ = E, x′0 = x0 etX ′

m = Xm, à savoir, l’alphabet, l’état initial et l’ensembledes états finaux deG etG′ sont identiques.

21

x0 x1x2

a b c

d

d

a,b,c,dxc

b,c,da,c

a,b

FIGURE 3.3 – L’automate obtenu en complétant l’AFD de la figure 3.1.

3. Pour tout x ∈ X ′ et pour toute ∈ E, soit

δ′(x, e) =

δ(x, e) si δ(x, e) est défini ;

xc autrement.

�

Exemple 3.11En complétant l’automate en figure 3.1 on obtient l’automatedans la fig-ure 3.3. Notons que par souci de simplicité, nous représentons une seule transition marquépare1, e2, . . . , ek du noeudx au noeudx pour indiquerk transitions parallèles (chacuneavec l’étiquetteei) dex à x. ⋄

Notez finalement, que l’automate completG′ accepte le même langage queG, mais il negénère pas le même langage : par constructionL(G′) = E∗. En plus, les propriétés desdeux automates sont différents : en particulier,G′ est certainement bloquant, vu que lenouvel étatxc n’est pas co-accessible.

22

Chapitre 4

Automates finis non-déterministes(AFN)

Dans ce chapitre on présente un deuxième modèle à évènementsdiscrets, appeléauto-mate fini non-déterministe, qui peut être vu comme une généralisation des automates finidéterministes. Pour plus d’information nous renvoyons le lecteur à [4, 1].

4.1 Définition d’un automate fini non-déterministe

Définition 4.1 Un automate fini non-déterministe(AFN) est un quintuplet

G = (X,E,∆, x0, Xm),

où :– X est l’ensemble fini des états ;– E est un alphabet ;– ∆ ⊆ X ×Eε ×X est larelation de transition, avecEε = E ∪ {ε} ;– x0 ∈ X est unétat initial ;– Xm ⊆ X est l’ensemble desétats finaux(ou états marqués). N

La relation de transition (cf. Annexe A pour la définition formelle derelation) spécifiela dynamique de l’automate : si(x, e′, x) ∈ ∆, alors de l’étatx l’occurrence d’unee′-transition conduit à l’étatx. On remarque que icie′ peut être un symbole de l’alphabetEou le mot videε.

Une représentation graphique d’un AFN peut aussi être donnée en utilisant le même for-malisme vu précédemment pour l’AFD.

Exemple 4.1La figure 4.1 montre un AFN avec ensemble des étatsX = {x0, x1, x2, x3, x4},alphabetE = {a, b}, état initialx0 et ensemble des états finauxXm = {x4}. La relation

23

x0 x1 x2

x3 x4

a

b

a

ε

b

aa

b

ba

FIGURE 4.1 – Un automate fini non-déterministe.

de transition∆ est donnée par :

∆ = { (x0, ε, x1), (x0, a, x0), (x0, b, x3)(x1, b, x0), (x1, b, x2),

(x2, a, x2), (x2, b, x4), (x3, a, x2), (x3, a, x4), (x4, a, x4) }.⋄

Un AFN peut être vu comme une généralisation d’un AFD. En fait, la relation de transition∆ est une généralisation de la relation de transition∆ (voir appendice A) introduisantdeux primitives de non-déterminisme comme montré dans la figure 4.2.

1. Transitions étiquetées avec le mot videε (appelées aussiε-transitions). Cette tran-sition décrit un évènementnon observableou silencieuxqui se produit sans êtreobservé.

2. Deux ou plus transitions qui partent du même état et qui ontla même étiquette. Cettestructure caractérise des évènementsméconnaissables, c’est-à-dire, on peut détecterque un évènement c’est produit, mais on ne peut pas déterminer exactement laquelleparmi les deux (ou plus) transitions associées au même évènement a été franchie.

4.2 Comportement d’un automate fini non-déterministe

Comme dans le cas d’un AFD, le comportement d’un AFN est donnépar toutes les évo-lutions possibles caractérisées par ses calculs.

Définition 4.2 Soit l’AFN G = (X,E,∆, x0, Xm), on définitcalcul de longueurk laséquence d’états et de transitions

xj0

e′1−→ xj1

e′2−→ · · ·xjk−1

e′k−→ xjk

où : pour touti = 0, . . . , k on axji ∈ X et pour touti = 1, . . . , k on a(xji−1, e′i, xji) ∈ ∆.

Ici e′i ∈ Eε peut être un évènement dansE ou le mot videε.

Un tel calcul départ de l’étatxj0, produit le motw = e′1e′2 · · · e′k et conduit à l’étatxjk . N

24

x x’a

a

x”

x x’

évènement

méconnaissableévènement

non observable

FIGURE 4.2 – Deux primitives de non-determinisme.

Exemple 4.2Un calcul possible de l’automate de la figure 4.1 est le suivant

x0a−→ x0

ε−→ x1b−→ x0

a−→ x0a−→ x0

Ce calcul départ de l’étatx0, produit le motw = abaa et conduit à l’étatx0. À noter quedans ce cas la longueur du mot généré est plus petite que la longueur du calcul : en fait,|w| = 4, alors que le calcul contient5 transitions. ⋄

De plus, puisque∆ est une relation de transition (et non une fonction), il peuty avoirdeux, ou plus, calculs qui départ du même état et produisent le même mot. Par exemple lecalcul suivant

x0a−→ x0

b−→ x3a−→ x4

a−→ x4

est aussi un calcul qui départ de l’étatx0 et produit le motw = abaa, mais il conduit àl’état x4.

Cette caractéristique, c’est-à-dire, le fait qu’un mot généré commençant par un état donnépeut correspondre à plus d’un calcul, rend un tel automate non-déterministe. Cette no-tion de non-déterminisme peut sembler différente de la notion commune utilisée dans lathéorie des systèmes, selon laquelle un système est déterministe si, à partir d’une con-dition initiale donnée et d’un signal d’entrée donné, il n’ya qu’une évolution possible.Cependant les deux notions coïncides si on considère un mot comme une entrée d’unsystème et le calcul comme son évolution.

Pour décrire le calcul d’un AFN de façon plus compacte on introduit la notion suivante.

Définition 4.3 Soit l’AFN G = (X,E,∆, x0, Xm), la fermeture transitive et réflexivedela relation de transition∆ est la relation∆∗ ⊆ X × E∗ ×X tel que(x, w, x) ∈ ∆∗ si ilexiste un calcul

xe′1−→ xj1

e′2−→ · · ·xjk−1

e′k−→ x

qui départ dex, produit le motw = e′1e′2 · · · e′k et conduit à l’étatx.

25

Par convention(x, ε, x) ∈ ∆∗, c’est-à-dire, si on départ d’un étatx et on produit le motvide l’automate pourrait être toujours enx (c’est le cas si aucuneε-transition s’est pro-duite). N

Exemple 4.3Pour l’automate dans la figure 4.1, on a

(x0, abaa, x0) ∈ ∆∗ and (x0, abaa, x4) ∈ ∆∗.

⋄

4.3 Langages d’un automates fini non-déterministe

A cause du non-déterminisme d’un système, la notion de mot accepté par un AFN doitêtre traitée avec particulièrement d’attention.

Définition 4.4 SoitG = (X,E,∆, x0, Xm) un AFN. On dit qu’un motw ∈ E∗ est :– généréparG : s’il existe un étatx ∈ X tel que(x0, w, x) ∈ ∆∗, c’est-à-dire qu’il existe

un calcul produisantw à partir de l’état initial ;– acceptéparG : s’il existe un étatx ∈ Xm tel que(x0, w, x) ∈ ∆∗, c’est-à-dire qu’il

existe un calcul produisantw à partir de l’état initial et qui conduit à un état finalx.N

On a vu qu’à cause du non-déterminisme, ils peuvent exister plusieurs calculs produisantw à partir de l’état initial. Le motw est accepté si au moins un de ces calculs conduit à unétat final.

Exemple 4.4Regardons la figure 4.1. Le motw = abaa peut être généré par plusieurscalculs, comme les deux suivants :

x0a−→ x0

ε−→ x1b−→ x0

a−→ x0a−→ x0

x0a−→ x0

b−→ x3a−→ x4

a−→ x4

Le premier calcul ne conduit pas à un état final. Cependant, ledeuxième conduit à l’étatfinal x4. Le motabaa est alors accepté. ⋄

Définition 4.5 SoitG = (X,E,∆, x0, Xm) un AFN. On associe à lui deux langages :– Le langage généré, c.à.d., l’ensemble des mots générés :

L(G) = {w ∈ E∗ | tel qu’il existex ∈ X : (x0, w, x) ∈ ∆∗} ⊆ E∗;

– Le langage accepté, c.à.d., l’ensemble des mots acceptés :

Lm(G) = {w ∈ E∗ | tel qu’il existex ∈ Xm : (x0, w, x) ∈ ∆∗} ⊆ L(G).

26

x0

x1b

a

b

x2

FIGURE 4.3 – Un AFNG bloquant oùLm(G) = L(G).

N

Ces langages et leurs préfixes satisfont les mêmes relationsque celles qu’on a vues pourles AFD :

Lm(G) ⊆ Lm(G) ⊆ L(G) = L(G).

On conclue cette partie en définissant les classes de langages acceptées par un AFN.

Définition 4.6 La la classe de langages sur un alphabetE accepté par un AFNest l’e-semble

LAFN = {L ⊆ E∗ | (il existe un AFNG) : L = Lm(G)},qui contient tous les langages puissants être acceptés par quelques AFN. N

4.4 Propriété d’un automate fini non-déterministe

Les principales propriétés d’un AFD ont été abordées dans laSection 4.4. Toutes cespropriétés qui dépendent de la structure graphique d’un AFDsont aussi valable pour unAFN : cela inclue les propriétés de la Définition 3.8 and Définition 3.9. Cependant, lespropriétés qui dépendent du langage peuvent changer, ceci étant du au non-déterminisme.

Par exemple, vu à la Définition 3.6 et 4.5, pour tout automateG (déterministes ou non-déterministes) on aLm(G) ⊆ L(G).

Pac contre, dans la Proposition 3.1 on a observé qu’un AFDG est non-bloquant si etseulement siLm(G) = L(G). Ce résultat ne tient pas pour un AFN, car le même mot peutêtre généré par deux chemins ou plus, un qui emmène à un état bloquant et l’autre non.Un AFN peut toutefois être bloquant siLm(G) = L(G).

Exemple 4.5Considérons l’AFN de la figure 4.3, dans lequel l’étatx2 est bloquant. On aalorsLm(G) = {ban | n ≥ 0} etLm(G) = {ε} ∪ {ban | n ≥ 0} = L(G). ⋄

Une propriété plus faible, toujours vraie pour un AFN, est lasuivante.

27

Proposition 4.1 Un AFNG est bloquant siLm(G) ( L(G). �

4.5 Equivalence entre AFD et AFN

Dans les précédentes parties, deux classes de langages ont été définis :

– LAFD : la classe des langages acceptés par les AFD ;– LAFN : la classe des langages acceptés par les AFN.

Puisqu’un AFD peut être vu comme un AFN particulier, tout langage accepté par un AFDest aussi accepté par un AFN et donc nous avons l’inclusion suivante :LAFD ⊆ LAFN .Dans cette partie, nous démontrerons que l’inclusion inverseLAFN ⊆ LAFD est aussivraie. Cela nous mène à la conclusion queLAFN = LAFD et donc que les deux modèles,AFD et AFN, décrivent la même classe de langages.

Pour prouver que la classe des langages acceptés par les AFD contient la classe des lan-gages acceptés par les AFN, nous décrirons une procédure qui, étant donné un AFNG,détermine un AFDG′ qui lui estéquivalent, i.e.,G′ accepte le même langage accepté parG et génère le même langage généré parG. Pour des soucis de simplicités, il n’y aura pasde preuve formelle de la justesse de l’algorithme donné.

L’idée de base est la suivante. Supposons que dans un AFNG, un motw peut être généré àpartir de l’état initial par différentes calculs qui atteint différents états, par exemple,x1, x2

andx3. Alors l’AFD G′ aura un seul état appelé{x1, x2, x3} et le seul calcul qui produitw à partir de l’état initial conduit à cet état.

Algorithme 4.1 AFD équivalent à un AFN.Entrée :Un AFN G = (X,E, δ, x0, Xm).Sortie :Un AFD G′ = (X ′, E ′, δ′, x′

0, X′m) avecLm(G

′) = Lm(G) etL(G′) = L(G).

1. Pour tout étatx ∈ X deG calculer l’ensemble

Dε(x) = {x ∈ X | (x, ε, x) ∈ ∆∗}

contenant les états accessibles à partir dex par l’occurrence dezéro ou plus ε-transitions. On notera que par définitionx ∈ Dε(x).

2. Pour tout étatx ∈ X deG et pour tout symbolee ∈ E calculer l’ensemble

De(x) = {x ∈ X | (x, e, x) ∈ ∆}

contenant tous les états accessibles à partir dex par l’occurrence deexactementune e-transition .

3. Soitx′0 = Dε(x0), c.à.d. l’état initial deG′ est l’ensemble des états accessibles dans

G à partir de l’état initialx0 exécutant zéro ou plusε-transitions.

28

ex’

e

e

(x’,e)(x’,e)

x

FIGURE 4.4 – Représentation des ensemblesα(x′, e) et β(x′, e) définis dans l’Algo-rithme 4.1.

4. Soit X ′ = ∅ etX ′new = {x′

0}. (A la fin de l’algorithmeX ′ ⊆ 2X contiendra tousles états deG′, tandis que l’ensembleX ′

new contient à chaque étapes les états deG′

encore à explorer.)

5. Sélectionner un étatx′ ∈ X ′new.

(a) Pour tout e ∈ E :

i. Définir les ensembles :

α(x′, e) =⋃

x∈x′

De(x) and β(x′, e) =⋃

x∈α(x′,e)

Dε(x).

Le premier ensemble contient les états accessibles dansG à partir d’unétatx ∈ x′ par l’occurrence de exactement unee-transition. Le deux-ième ensemble contient les états accessibles dansG à partir d’un étatx ∈ α(x′, e) par l’occurrence de zéro ou plusε-transitions (voir fig-ure 4.4).

ii. Soit x′ = β(x′, s) et définirδ′(x′, e) = x′. c.à.d. l’occurrence de l’évène-mente à partir de l’étatx′ deG′ rendx′.

iii. Si x′ 6∈ X ′ ∪X ′new alorsX ′

new = X ′new ∪ {x′}.

(b) SoitX ′ = X ′ ∪ {x′} etX ′new = X ′

new \ {x′}.

6. Si X ′new 6= ∅ alors goto5.

7. Soit X ′m = {x′ ∈ X ′ | x′ ∩Xm 6= ∅}, c.à.d. un étatx′ deG′ est final si il contient

au moins un état final deG. �

Nous considérons maintenant un exemple d’application de cet algorithme.

Exemple 4.6On considère l’AFNG dans la figure 4.5(a) et on souhaite déterminer unAFD G′ à lui équivalent.

29

x0

x1

x2x3 x4

x5

a

b

a

a

b

b

a

b

x0’={x0, x2, x3}

x1’={x4, x5}

x2’={x1, x4}

b

a

a

b

a

a

(a) (b)

FIGURE 4.5 – (a) Un AFN ; (b) son AFD équivalent.

Premièrement calculons les ensemblesDε etDe comme indiqué dans le tableau ci-dessous :

x Dε(x) Da(x) Db(x)

x0 {x0, x2, x3} ∅ ∅x1 {x1} {x1} {x0, x3}x2 {x2, x3} ∅ ∅x3 {x3} {x4, x5} ∅x4 {x4} {x1, x4} ∅x5 {x5} ∅ {x4, x5}

Nous considérons comme état initial deG′ l’état x′0 = {x0, x2, x3}.

À l’étape 5 de l’Algorithme :– Choisir dansX ′

new l’état x′0 = {x0, x2, x3}.

Pour l’évènementa on obtientα(x′0, a) = Da(x0) ∪ Da(x2) ∪ Da(x3) = {x4, x5} et

β(x′0, a) = Dε(x4) ∪Dε(x5) = {x4, x5}, par conséquentδ′(x′

0, a) = x′1 = {x4, x5}.

Pour l’évènementb on obtientα(x′0, b) = ∅ et β(x′

0, b) = ∅, par conséquentδ′(x′0, b)

n’est pas défini.– Choisir dansX ′

new l’état x′1 = {x4, x5}.

Pour l’évènementa on obtientα(x′1, a) = Da(x4) ∪ Da(x5) = {x1, x4} et β(x′

1, a) =Dε(x1) ∪Dε(x4) = {x1, x4}, par conséquentδ′(x′

0, a) = x′2 = {x1, x4}.

Pour l’évènementb on obtientα(x′1, b) = Db(x4) ∪ Db(x5) = {x4, x5} et β(x′

1, b) =Dε(x4) ∪Dε(x5) = {x4, x5}, par conséquentδ′(x′

1, b) = x′1 = {x4, x5}.

– Choisir dansX ′new l’état x′

2 = {x1, x4}.Pour l’évènementa on obtientα(x′

2, a) = Da(x1) ∪ Da(x4) = {x1, x4} et β(x′2, a) =

Dε(x1) ∪Dε(x4) = {x1, x4}, par conséquentδ′(x′0, a) = x′

2 = {x1, x4}.Pour l’évènementb on obtientα(x′

2, b) = Db(x1) ∪ Db(x4) = {x0, x3} et β(x′2, b) =

Dε(x0) ∪Dε(x3) = {x0, x2, x3}, par conséquentδ′(x′1, b) = x′

0 = {x0, x2, x3}.

30

x′ α(x′, a) β(x′, a) α(x′, b) β(x′, b)

x′0 = {x0, x2, x3} {x4, x5} {x4, x5} ∅ ∅x′1 = {x4, x5} {x1, x4} {x1, x4} {x4, x5} {x4, x5}

x′2 = {x1, x4} {x1, x4} {x1, x4} {x0, x3} {x0, x2, x3}

TABLE 4.1 – Tableau résumant les étapes de l’exemple 4.6.

À l’étape 7 de l’algorithme on obtientX ′ = {x0,′ x′

1, x′2} et puisque seul l’étatx′

0 contientx2 (l’unique état marqué deG) on obtientX ′

m = {x′0}.

Les différentes étapes ont été résumées dans le Tableau 4.1.

La représentation graphique de l’AFDG′ est donnée dans la figure 4.5(b). ⋄

Dans l’exemple précédent l’ensemble des étatsX de l’AFN G a une cardinalité|X| = 7,tandis que l’ensemble des étatsX ′ de l’AFD G′ équivalent à une cardinalité|X ′| = 3états. En général, on ne peut pas dire a priori lequel des deuxautomates a le plus grandnombres d’états. Le seul résultat général est le suivant.

Proposition 4.2 SoitG un AFN avec ensemble d’étatsX. Un AFDG′ équivalent àG aensemble d’étatsX ′ de cardinalité

|X ′| ≤ 2|X| − 1.

Preuve.Chaque état dansX ′ est un sous-ensemble non vide d’états dansX. Le nombrede sous-ensembles possibles deX, y compris l’ensemble vide qui ne peut pas être un état

deG′, est2|X|. �

Il faut noter que dans le pire des cas, la cardinalité de l’ensemble d’état de l’AFD équiva-

lent peut être égal à2|X| − 1, c.à.d. il peut croître de façon exponentielle en fonction dunombre d’états de l’AFN.

31

Chapitre 5

Automates avec entrées et sorties

Dans ce chapitre nous allons considérer deux modèles particuliers, nommésautomate deMooreet automate de Mealy, dont l’évolution est guidée par une séquence d’évènementsen entrée, qui produiront des séquences d’évènements en sortie.

5.1 L’automate de Moore

C’est un modèle AFD qui produit un évènement en sortie dépendant de l’état courant.

Définition 5.1 Uneautomate de Mooreest un sextuplet défini parGmo = (X,E,Θ, δ, λ, x0)où :– X, E, δ et x0 sont définis de la même façon que pour un AFD (à l’exception qu’à

présentE se nommealphabet d’entrée) ;– Θ est nomméalphabet de sortie;– λ : X → Θ est lafonction de sortie, c’est-à-dire, l’évènementλ(x) ∈ Θ est la sortie

produite quand l’automate est à l’étatx. N

Supposons qu’à la séquence d’entréew = e1e2 · · · ek ∈ E∗ corresponde le calcul1

xj0

e1−→ xj1

e2−→ · · ·xjk−1

ek−→ xjk

Alors sur cette entrée l’automate va produire cette séquence de sortie

v = λ(xj0)λ(xj1) · · ·λ(xjk) ∈ Θ∗.

Lorsque l’automate est initialisé (c’est-à-dire quand la séquence d’entrée estε), une sortieλ(x0) est produite : par conséquent, la longueur de la séquence de sortie est toujours d’uneunité plus grande que la longueur de la séquence d’entrée. Lareprésentation graphique del’automate de Moore est similaire à un AFD à la différence quechaque étatx ∈ X à uneétiquetteλ(x).

1. Un tel calcul est unique car l’automate est déterministe.

32

a a bY

bA B

a

bb

Y Ya b

x0 x4x3x2 x1

FIGURE 5.1 – Automate de Moore en Example 5.1.

Exemple 5.1L’automate de Moore en figure 5.1 représente le comportementd’un sys-tème de surveillance guidé par deux types d’évènements,a et b.Si les deux derniersévènements étudiés sont tous les deuxa, alors le système produira une sortieA ; si lesdeux derniers évènements étudiés sont tous les deuxb, alors le système produira unesortieB ; sinon il produiraY . L’alphabet d’entrée estE = {a, b} et celui de sortie estΘ = {A,B, Y }. ⋄

L’ensemble des états finaux d’un automate de Moore n’est pas défini. Cependant, il estimportant de savoir que l’ensemble des états finaux d’une AFDpeut être vu comme unerelation qui partitionne les états en deux classes : lesétats marquéset lesétats non mar-qués.

Toutefois, la fonction de sortie d’un Automate de Moore autorise une partition de l’ensem-ble d’états en autant de classes qu’il a de symboles de sortie. Par conséquent, un AFD peutêtre considérée comme un automate de Moore avec un alphabet de sortieΘ = {m, m}, oùλ(x) = m si x est marqué etλ(x) = m si x est non marqué. Ainsi, dans ce raisonnement,un automate de Moore est une généralisation d’un AFD.

5.2 L’automate de Mealy

Ce modèle est un AFD qui produit un évènement de sortie à chaque fois qu’une transitionse déclenche.

Définition 5.2 Unautomate de Mealyest un sextuplet défini parGme = (X,E,Θ, δ, λ, x0)où :– X, E, δ et x0 sont définis de la même façon que pour un AFD (à l’exception qu’à

présentE se nommealphabet d’entrée) ;– Θ est nomméalphabet de sortie;– λ : X × E → Θ est lafonction de sortie, c’est-à-dire, l’évènementλ(x, e) désigne

l’évènement de sortie produit lorsque la transitionδ(x, s) se déchenche. N

Supposons qu’à la séquence d’entréew = e1e2 · · · ek ∈ E∗ corresponde le calcul :

xj0

e1−→ xj1

e2−→ · · ·xjk−1

ek−→ xjk

33

a / Y b / Y

x0

a / Y

b / Y

a / A b / Bx2x1

FIGURE 5.2 – Un automate de Mealy équivalent à l’automate de Moore dela figure 5.1.

Alors sur cette entrée, l’automate produira en sortie cetteséquence :

v = λ(xj0, e1)λ(xj1, e2) · · ·λ(xjk−1, ek) ∈ Θ∗.

Notez que lorsque l’automate est initialisé (c’est-à-dire, quand la séquence d’entrée estε)l’automate ne produit aucun symbole de sortie : par conséquent la longueur de la séquencede sortie est égal à la longueur de la séquence d’entrée.

La représentation graphique de l’automate de Mealy est similaire à un AFD mais chaquetransitionδ(x, e) à une double étiquettee/λ(x, e) spécifiant l’évènement d’entréee quidéclenche la transition et la sortieλ(x, e) qui est produit par la transition.

Exemple 5.2L’automate de Mealy dans la figure 5.2 représente le même système décritpar l’automate de Moore dans l’exemple 5.1. Il y a juste une différence mineure entre lesdeux modèles. Si on suppose que la séquence d’entrée donnée produit sur l’automate deMoore la séquence de sortieY ω, oùω ∈ Θ∗ alors la même séquence d’entrée produit surl’automate de Mealy la séquence de sortieω. ⋄

Notez, enfin, que l’automate de Mealy de l’exemple à moins d’états que son équivalentautomate de Moore. C’est parce que la possibilité d’associer des étiquettes aux transitionsconduit usuellement à un modèle plus compact.

34

Chapitre 6

Diagnostic et diagnosticabilité dessystèmes à évènements discrets à l’aided’automates

Dans ce chapitre, nous présentons un approche au diagnosticdes automates développéspar Lafortune et collègues [6]. Lafortune et ses co-auteurs. Une présentation plus com-plète de l’approche peut se trouver dans [1].

6.1 Le modèle des procédés

Un système à diagnostiquer est modélisée comme un AFD. Puisque nous ne sommespas intéressés par l’ensemble des états finaux, nous désignons un tel automate parG =(X,E, δ, x0). Le comportement du système est décrit par le langageL(G) généré parG.

Le modèle AFD représente à la fois le comportement normale etle comportement dé-fectueux. Son alphabet peut être partitionné commeE = Eo ∪ Euo où :– Eo : est l’ensemble desévènements observables;– Euo : est l’ensemble desévènements non observables. L’ensemble des évènements non

observables peut être partitionné commeEuo = Ef ∪ Ereg où– Ef est l’ensemble desévènements de panne;– Ereg est l’ensemble desévènements réguliersqui, bien que non observables, ne

décrivent pas un comportement défectueux.Dans le reste du chapitre, on fait les hypothèses suivantes :

(A1) L’AFD G ne contient pas états morts.(A2) L’AFD G ne contient pas de cycles d’évènements inobservables.

L’hypothèse (A1) est faite pour des raisons de simplicité. Au contraire, l’hypothèse (A2)est nécessaire et assure que le systèmeG ne génère pas de séquences inobservables dontla longueur peut être infinie.

35

FIG 6.1

x0 x1

a

1

c

b

x2

f

FIGURE 6.1 – Un AFD avec ensemble d’évènements observablesEo = {a, b, c}, évène-ments inobservable réguliersEreg = {ε1} et évènements inobservables de panneEreg ={εf}.

Exemple 6.1Considérons l’automate dans la figure 6.1. L’ensemble des évènements ob-servables estEo = {a, b, c} alors que l’ensemble des évènements inobservables estEuo ={ε1, εf}. En particulier, l’ensemble des évènements réguliers estEreg = {ε1} et l’ensem-ble des évènements de panne estEf = {εf}. L’automate satisfait à la fois l’hypothèse A1et A2. ⋄

Définissons l’opération de projection sur l’ensemble des évènements observables.

Définition 6.1 Étant donné un AFD avec alphabetE = Eo ∪ Euo, la projection surl’ensemble des évènements observables est notéeP : E∗ → E∗

o et est défini comme :

P (ε) = ε

P (e) = e, si e ∈ Eo ;

P (e) = ε, si e ∈ Euo ;

P (se) = P (s)P (e), si s ∈ E∗, e ∈ E .

L’ opération de projection inverseavec co-domain dansL(G) est notéeP−1 : E∗o → 2L(G)

et est défini comme :P−1(w) = {s ∈ L(G) | P (s) = w}.

N

Ainsi, l’opération de projectionP efface dans une séquence tout évènement inobserv-able, tandis que son inverse associe à un motw d’évènements observables l’ensemble desséquences dans le langage deG dont la projection estw. Dans le reste de cette section,nous noteronss ∈ E∗ une séquence d’évènements générée par l’AFD et parw ∈ E∗

o unmot observé, à savoir, la projection observable d’une séquence générée.

Supposons qu’un AFD, à partir de l’état initial, génère une séquences ∈ L(G) ⊆ E∗ etqu’il atteint un nouvel étatx = δ∗(x0, s). Puisque la masque due à la projection caches

36

s L(G) E*

AFD

G séquence

d’évènements

génerée

w Eo*

projection

P mot

observé

FIGURE 6.2 – L’observation d’un AFDà travers un masque de projection.

les évènements inobservables, un agent externe observe un mot w = P (s) ∈ E∗o , comme

représenté sur la figure 6.2. En général, l’agent externe peut ne pas être en mesure dedétecter la séquence exacte qui a produit cette observationou l’état exact qui a été atteint.

Définition 6.2 Soit un AFDG = (X,E, δ, x0) avec alphabetE = Eo∪Euo. Pour chaquemotw ∈ E∗

o on dénote :– S(w) = P−1(w) ⊆ L(G) l’ensemble desséquences compatibles avec l’observationw,

à savoir, l’ensemble des séquences dans le langage deG qui produisent l’observationw ;

– X (w) = {x ∈ X | (∃s ∈ S(w)) δ∗(x0, s) = x} l’ensemble desétats compatibles avecl’observationw, à savoir, l’ensemble des états dans lesquelsG peut être après quew aété observé. N

Exemple 6.2Considérons l’automate dans la figure 6.1 où l’ensemble des évènementsobservables estEo = {a, b, c}.

Supposons que le motbb est observé. Deux calculs différents auraient pu produire cetteobservation :

x0b−→ x1

ε1−→ x0b−→ x1

x0b−→ x1

ε1−→ x0b−→ x1

ε1−→ x0

Par conséquent, l’ensemble des séquences compatibles aveccette observation estS(bb) ={bε1b, bε1bε1} et l’ensemble des états compatibles estX (bb) = {x0, x1}.

Considérez le motbc ∈ E∗o . Étant donné qu’aucune séquence générée par le procédé peut

produire cette observation on aS(bc) = X (bc) = ∅. ⋄

Définition 6.3 Étant donné une séquences ∈ E∗, sonsupportest

||s|| = {e ∈ E | |s|e > 0} ⊆ E,

et se compose de l’ensemble des évènements qui apparaissentau moins une fois dans laséquence. N

Exemple 6.3Considérons à nouveau l’automate dans la figure 6.1 dont l’alphabet estE = {a, b, c, ε1, εf}. Le support de la séquences = aεfac ∈ E∗ is ||s|| = {a, c, εf}. ⋄

37

6.2 Diagnostic

Dans un problème de diagnostic de panne, nous voulons déterminer, à partir du mot ob-servéew ∈ E∗

o , si une panne est survenue, à savoir, si l’occurrence d’une transition mar-quée par un symbole dansEf a eu lieux. Cela conduit à la définition d’un problème dediagnostic.

Problème 6.1 Soit un AFDG avec alphabetE = Eo ∪Euo et ensemble d’évènements depanneEf ⊆ Euo. Etant donné un mot observéw ∈ E∗

o , le problème de diagnostic consisteà déterminer si une séquence qui contient un évènement de panne (c.à.d. un symbole enEf ) a produit l’observationw.

Résoudre un problème de diagnostic nécessite la construction d’une fonction de diagnos-tic.

Définition 6.4 Soit un AFDG avec alphabetE = Eo ∪ Euo et ensemble d’évènementsde panneEf ⊆ Euo. Unefonction de diagnostic:

ϕ : E∗o → {N,F, U}

associe à chaque motw ∈ E∗o observé un état de diagnosticϕ(w) ∈ {N,F, U} comme

suit.– ϕ(w) = N (en anglais : normal = pas de panne) : si pour touts ∈ P−1(w) on a||s|| ∩ Ef = ∅. Cela signifie que aucune séquences compatible avec le mot observéwne contient un évènement de panne, donc par conséquent, aucune panne s’est produite.

– ϕ(w) = F (en anglais : fault = panne) : si pour touts ∈ P−1(w) on a||s||∩Ef 6= ∅. Celasignifie que toute séquences compatible avec le mot observéw contient un évènementde panne, donc par conséquent une faute a certainement eu lieu.

– ϕ(w) = U (en anglais : uncertain = incertain) : s’il existents′, s′′ ∈ P−1(w) tels que||s′|| ∩ Ef = ∅ et ||s′′|| ∩ Ef 6= ∅. Dans un tel cas, ils existent deux séquencess′ et s′′

compatible avec le mot observéw, l’une qui contient un évènement de panne et l’autrequi ne le contient pas. On a donc qu’une panne aurait pu se produire ou pas. N

Nous remarquons que lorsque plusieurs classes de panneEf,1, Ef,2, . . . , Ef,r sont don-nées, on veut diagnostiquer séparément chaque classei pour déterminer si une défail-lance dans cette classe a eu lieu, c.a.d. une transition marquée par un symbole dansEf,i

est survenue. Dans ce cas il faut résoudrer problèmes de diagnostic, à savoir déterminerr fonctions de diagnosticϕi, pouri = 1, 2, . . . , r. Cependant, ce cas ne sera pas discuté.

Exemple 6.4Considérons l’automate dans la figure 6.1 où l’ensemble des évènementsobservables estEo = {a, b, c} et l’ensemble des évènements de panne estEreg = {εf}. Lafonction de diagnostic pour cette AFD est partiellement décrite dans le tableau suivant oùnous avons aussi noté pour chaque mot observée l’ensemble des séquences compatibles

38

S(w) et l’ensemble des états compatiblesX (w).

w S(w) = P−1(w) X (w) ϕ(w)

ε ε {x0} N

a { a, aεf } {x0, x2} U

b { b, bε1 } {x0, x1} N

aa { aεfa, aεfaεf } {x0, x2} F...

......

...

⋄

Une méthode plus intéressante pour représenter une fonction de diagnostic est fondée surle diagnostiquateur, à savoir un AFD sur l’alphabet des évènements observables.

Définition 6.5 Un diagnostiquateurpour l’AFD G = (X,E, δ, x0) avec alphabetE =Eo ∪ Euo et ensemble d’évènements de panneEf ⊆ Euo est un AFD

Diag(G) = (Y,Eo, δy, y0)

sur l’alphabetEo tels que :– Y ⊆ 2X×{N,F}, c.à.d. chaque état du diagnostiquateur est un ensemble de couples

y = {(x1, γ1), (x2, γ2), . . . , (xk, γk)},oùxi ∈ X etγi ∈ {N,F}, pouri = 1, 2, . . . , k.

– δ∗y(y0, w) = yw si et seulement si

yw = {(x,N) | (∃s ∈ S(w)) δ∗(x0, s) = x, ||s|| ∩ Ef = ∅}∪{(x, F ) | (∃s ∈ S(w)) δ∗(x0, s) = x, ||s|| ∩ Ef 6= ∅},

c.à.d., enDiag(G) le motw conduit, à partir de l’étaty0 à un étatyw qui contient :(a) toute couple(x,N) oùx peut être atteint enG en exécutant une séquence compat-

ible avecw qui ne contient pas un évènement de panne ;(b) toute couple(x, F ) oùx peut être atteint enG en exécutant une séquence compat-

ible avecw qui contient un évènement de panne.A chaque étaty = {(x1, γ1), (x2, γ2), . . . (xk, γk)} deDiag(G) on associe une valeur dediagnosticϕ(y) telle que :– ϕ(y) = N (pas de panne) : siγi = N pour touti = 1, 2, . . . , k ;– ϕ(y) = F (panne) : siγi = F pour touti = 1, 2, . . . , k ;– ϕ(y) = U (incertain) : s’il existenti, j ∈ {1, 2, . . . , k} tels queγi = N etγj = F . N

Ainsi, un diagnostiquateur permet d’associer à chaque mot observé une valeur de diag-nosticϕ(w) = ϕ(yw) oùyw = δ∗y(y0, w) est l’état atteint enDiag(G) en exécutant le motw. En outre, le diagnostiquateur contient également des informations sur l’ensemble desétats compatibles avecw, carX (w) = {x ∈ X | yw = δ∗y(y0, w), (x, γ) ∈ yw}.

39

(x0,N) (x2,N)(x0,F)

(x0,F)

(x2,F)

(x0,N)

(x1,N)

(x0,F)

(x1,F)

c a b,c a

a aa

bb

b

y0 [N] y1 [U] y2 [F]

y3 [N] y4 [F]

FIGURE 6.3 – DiagnostiquateurDiag(G) pour le AFD de la figure 6.1.

Exemple 6.5Considérons le procédé de la figure 6.1 où l’ensemble des évènements ob-servables estEo = {a, b, c} et l’ensemble des évènements de panne estEf = {εf}. Lediagnostiquateur pour cette AFD est représenté dans la figure 6.3, où nous avons marquéchaque étaty desDiag(G) avec sa valeur de diagnostic correspondanteϕ(y) entre cro-chets. ⋄

Un algorithme formel pour la construction du diagnostiquateur d’un automateG est main-tenant donné. Cet algorithme est similaire à l’algorithme utilisé pour calculer l’observa-teur deG (à savoir, l’AFD équivalent). Cependant, nous avons maintenant besoin nonseulement de garder mémoire des états possibles où le procédé pourrait être, mais ausside savoir si ces états peuvent être atteints avec ou sans franchir une transition de panne.

Algorithme 6.1 Construction d’un diagnostiquateur.Entrée :Un AFD G = (X,E, δ, x0) avecE = Eo ∪ Euo = Eo ∪ Ereg ∪ Ef

Sortie :Un diagnostiquateurDiag(G) = (Y,Eo, δy, y0) avecL(Diag(G)) = P (L(G)).

1. Pour tout étatx ∈ X deG calculer l’ensemble

Dreg(x) = {x ∈ X | (∃s ∈ E∗reg) δ

∗(x, s) = x)}

contenant tous les états accessibles depuisx en exécutant une séquence (éventuelle-ment vide) de transitions régulières inobservables, et l’ensemble

Df(x) = {x ∈ X | (∃s ∈ E∗uo \ E∗

reg) δ∗(x, s) = x}

contenant tous les états accessibles à partir dex en exécutant une séquence de tran-sitions inobservables qui contient au moins un évènement depanne. On notera que,par définition,x ∈ Dreg(x). Notez également qu’il peut arriver queDreg(x) ∩

40

Df(x) 6= ∅, c.à.d. un étatx pourrait être accessible à partir dex par deux dif-férentes séquences de transitions inobservables, l’une qui ne contient pas de panneet l’autre qui en contient une.

2. Soity0 = {(x,N) | x ∈ Dreg(x0)} ∪ {(x, F ) | x ∈ Df(x0)},

c’est à-dire que l’état initial deDiag(G) est un ensemble de couples(x, γ) où :– γ = N si x est accessible à partirx0 en exécutant une séquence de transitions

non observables qui ne contient pas de panne ;– γ = F si x est accessible à partirx0 en exécutant une séquence de transitions

non observables qui contient une panne.

3. Soit Y = ∅ etYnew = {y0}.(à la fin de l’algorithmeY contiendra tous les états deDiag(G), alors que l’ensem-bleYnew contient à chaque étape, les états deDiag(G) encore à explorer.)

4. Sélectionner un étaty ∈ Ynew.

(a) Pour tout e ∈ Eo :

i. définir les ensembles :

α(y, e) = {(x′, γ) | (x, γ) ∈ y, x′ = δ(x, e)}

etβ1(y, e) = {(x′′, N) | (x′, N) ∈ α(y, e), x′′ ∈ Dreg(x

′)},β2(y, e) = {(x′′, F ) | (x′, N) ∈ α(y, e), x′′ ∈ Df(x

′)},β3(y, e) = {(x′′, F ) | (x′, F ) ∈ α(y, e), x′′ ∈ Dreg(x

′) ∪Df (x′)}.

– L’ensembleα(y, e) contient les couples(x′, γ) telles que l’étatx′estaccessible enG depuis l’étatx exécutant exactement une e-transitionet (x, γ) ∈ y.

– L’ensembleβ1(y, e) contient les couples(x′′, N) telles que l’étatx′′ estaccessible enG depuis l’étatx′ exécutant une séquence de transitionsrégulières et(x′, N) ∈ α(y, e). En effet, six′ est accessible sans panne,tel est aussix′′.

– L’ensembleβ2(y, e) contient les couples(x′′, F ) telles que l’étatx′′ estaccessible enG depuis l’étatx′ exécutant une séquence de transitionsinobservables qui contient une panne et(x′, N) ∈ α(y, e). Dans cecas, même six′ est accessible sans panne, l’étatx′′ est atteint avec unepanne.

– L’ensembleβ3(y, e) contient les couples(x′′, F ) telles que l’étatx′′ estaccessible enG depuis l’étatx′ exécutant une séquence de transitionsinobservables et(x′, F ) ∈ α(y, e). Dans ce cas, puisquex′ est accessi-ble avec une panne, tel est égalementx′′.

ii. Soit y′ = β1(y, e)∪β2(y, e)∪β3(y, e) et on définitδY (y, e) = y′, à savoir,enDiag(G) l’occurrence de l’évènemente depuis l’étaty conduit ày′.

iii. Si y′ 6∈ Y ∪ Ynew alors Ynew = Ynew ∪ {y′}.

41

(x’1,N)

(x’2,N)

(x’3,F)

(x1,N)

(x2,N)

(x3,F)

e

e

y (y,e)

e

(x”1,N)

(x”2,F)

(x”3,F)

w E*reg

w E*uo, w Ef

w E*uo

(y,e)

(y,e)

(y,e)

y’

FIGURE 6.4 – Le calcul d’un nouvel étaty′ = δy(y, e) du diagnostiquateur à l’étape 4.(a)Algorithme 6.1.

(b) Soit Y = Y ∪ {y} etYnew = Ynew \ {y}.5. Si Ynew 6= ∅ alors allez au4. �

En figure 6.4 sont montrés les ensembles calculés à l’étape 4.(a) de l’algorithme.

Nous concluons par la remarque suivante.

Proposition 6.1 Étant donné un procédéG avec ensemble d’étatsX de cardinaliténx,soitDiag(G) son diagnostiquateur avec ensemble d’étatsY de cardinalitény. On any <22nx.

Preuve.Chaque ètat deY est un sous-ensemble non vide d’éléments dans l’ensembleZ = (X×{N})∪(X×{F}) de cardinalité2nx. Le nombre de sous-ensembles possiblesdeZ (y compris l’ensemble vide qui ne peut pas être un état du diagnostiquateur) est22nx.�

6.3 Diagnosticabilité

Définissons maintenant une propriété fondamentale pour la diagnostic de pannes.

Définition 6.6 SoitG un AFD avec alphabetE = Eo ∪ Euo et ensemble d’évènementsde panneEf ⊆ Euo. On appelle l’AFDG diagnostiquablesi pour toute séquenceuef ∈L(G) telle queef ∈ Ef , il existe un entier positifn ∈ N tel que

s = uefv ∈ L(G), |v| ≥ n =⇒ 6 ∃s′ ∈ L(G) ∩ (E \ Ef)∗ tel queP (s) = P (s′).

42

N

Cette propriété peut également être exprimée dans la manière suivante. Supposons quele procédé puisse générer une séquenceuef qui termine avec une panne et supposonsque l’évolution continue. Si le procédé est diagnostiquable, après un nombre fini d’étapesn (qui peut dépendre deuef ), lorsque le nouveau mot observé ests = uefv il n’existeaucune autre séquences′ sans panne dans le langage du procédé qui produit la mêmeobservation des. Cela garantit que chaque fois qu’un évènement de panneef survient,après un nombre fini d’étapes, nous allons détecter sa présence parce que nous allonsobserver un mot qui n’est pas compatible avec un séquence sans panne.

Problème 6.2 Étant donné un AFDG le problème de diagnosticabilitéconsiste à déter-miner siG est diagnostiquable.

Nous allons montrer que le diagnostiquateur, qui fournit une solution au problème de di-agnostic, peut aussi nous aider à résoudre le problème de diagnosticabilité. Mais d’abord,nous avons besoin d’introduire quelques définitions.

Définition 6.7 Étant donné un diagnostiquateurDiag(G), un cycle

yj1e1−→ yj2

e2−→ yj3 · · · yjkek−→ yj1

est appelé uncycle incertainsi tous ses états sont incertains, c.à.d.ϕ(yji) = U for i =1, 2, . . . , k. N

Comme résultat préliminaire, nous pouvons maintenant énoncer une condition suffisantepour la diagnosticabilité.

Proposition 6.2 Un AFDG est diagnostiquable si son diagnostiquateur ne contient pasde cycles incertains.

Preuve.Supposons que l’AFD n’est pas diagnostiquable. Alors, la situation suivante doitse produire :– l’AFD peut générer une séquences = uεf contenant le panneεf ;– la séquences peut être prolongée pour une longueur arbitraire générant les séquencessk = uεfe1e2 . . . ek pourk ≥ 1

– pour toute séquencesk (pourk ≥ 1) il existe une séquence sans pannes′k ∈ (E \ Ef )∗

tel queP (sk) = P (s′k) , c.à.d.,s et s′ produisent la même observation.Cela signifie que dans le diagnostiquateur le mot observéw = P (s) atteint un état in-certainyj1 et depuis cet état, commek se développe, il existent des motswk = P (sk)de longueur illimitée (par l’Assomption A2) qui conduisenttoujours à un état incertain.Étant donné que le nombre d’états du diagnostiquateur est fini, ceci est possible seulements’il existe un cycle d’états incertains. �

Exemple 6.6Considérons à nouveau l’AFD dans la figure 6.1, dont le diagnostiquateura été montré dans la figure 6.3. On peut voir qu’il existent dans ce diagnostiquateur les

43

6 cycles élémentaires ci-dessous (nous avons également montré l’état de diagnostic dechaque état pour une meilleure compréhension) :

y1 [U ]c−→ y3 [N ]

a−→ y1 [U ] y3 [N ]b−→ y3 [N ] y2 [F ]

b−→ y4 [F ]a−→ y2 [F ]

y2 [F ]c−→ y4 [F ]

a−→ y2 [F ] y2 [F ]a−→ y2 [F ] y4 [F ]

b−→ y4 [F ]

Aucun de ces cycles n’est incertain, nous concluons donc quel’AFD est diagnostiquable.⋄

L’exemple suivant montre que cette condition suffisante pour la diagnosticabilité n’esttoutefois pas nécessaire.

Exemple 6.7Considérons l’AFD dans la figure 6.5 (à gauche) où l’ensembledes évène-ments observables estEo = {a, b}, l’ensemble des évènements réguliers est vide etl’ensemble des évènements de panne estEf = {εf}. Le diagnostiquateur de cette AFDest montré dans la figure 6.5 (à droite). On peut voir qu’il existe dans le diagnostiquateurun cycle d’états incertains

y1 [U ]b−→ y2 [U ]

a−→ y1 [U ]

Cependant, on peut facilement vérifier que cette AFD est diagnostiquable. Pour le mon-trer, nous observons que la panne peut se produire dans deux types de séquences dif-férentes.

– Séquences de panne commençant par(ab)kεf . Dans ce cas, après la panne le systèmeatteint l’étatx2, et en seulement deux étapes, lorsque la séquenceaa se produit, le motobservé ests = (ab)kaa. PuisqueP−1(s) = {(ab)kεfaa} il n’existe aucune séquencesans panne compatible avec l’observations et l’occurrence de la panne est détecté.

– Séquences de panne commençant par(ab)kaεf . Dans ce cas, après la panne le systèmeatteint l’étatx3 et en seulement deux étapes, lorsque la séquencebb se produit, le motobservé ests = (ab)kabb. PuisqueP−1(s) = {(ab)kaεfbb} il n’existe aucune séquencesans panne compatible avec l’observations′ et l’occurrence de la panne est détecté.

Donc la présence d’un cycle incertain dans le diagnostiquateur ne signifie pas nécessaire-ment que le procédé produit une observation d’une longueur illimitée après la fautequiest aussi compatible avec séquences sans panne. ⋄

Pour dériver une condition nécessaire et suffisante pour la diagnostiquabilité, il nous fautun concept supplémentaire.

Définition 6.8 (Séquence affinée associée à un cycle incertain) Étant donné un diagnos-tiquateurDiag(G), considérons un cycle incertain

uc = yj1e1−→ yj2

e2−→ yj3e3−→ · · · ek−1−→ yjk

ek−→ yj1.

44

b a

x0 x1

x2 x3

ef ef

a

b

(x0,N)

(x2,F)

(x1,N)

(x2,F)

(x3,F)

(x2,F)

a

a

a

y0 [U] y1 [U]

y3 [F]

(a) (b)

(x0,N)

(x2,F)

(x3,F)

(x3,F)

b

b

y2 [U]

y4 [F]

a

b

FIGURE 6.5 – Le AFD dans l’exemple 6.7 (a) et son diagnostiquateur (b).

qui part deyj1 et produit la séquence d’évènementse1e2 · · · ek. Soity1j1 l’ état de diagnosticaffinéobtenu à partir deyj1 enlevant toutes les couples sans panne(x,N). Uneséquenceaffinéeassociée àuc est une séquence d’états obtenu en appliquant la construction dudiagnostiquateur à partir dey1j1 par répétition de la séquencee1e2 · · · ek :

y1j1e1−→ y1j2

e2−→ y1j3e3−→ · · · ek−1−→ y1jk

ek−→ y2j1e1−→ y2j2

e2−→ · · ·

Il n’est pas difficile de montrer qu’une séquence affinée du diagnostic :– soit atteindra un étatykj = yk+1

j et peut donc se poursuivre indéfiniment ;– ou atteindra un état sans successeur et finira par s’arrêter.

Définition 6.9 (Cycle indéterminé) Un cycle incertainuc est appelé uncycle indéter-minési sa séquence affinée peut être poursuivi indéfiniment. N

Nous pouvons enfin présenter le résultat suivant dont la preuve est fondée sur les résultatsen [6].

Proposition 6.3 Un AFDG est diagnostiquable si et seulement si son diagnostiquateurDiag(G) ne contient pas de cycles indéterminés. �

Exemple 6.8Considérons à nouveu l’AFD dans la figure 6.5 et étudié dans l’exemple 6.7.Nous avons déjà remarqué qu’il existe dans le diagnostiquateur un seul cycle incertainillustré dans la figure 6.6(a) :

y1 [U ]b−→ y2 [U ]

a−→ y1 [U ]

oùy1 = {(x1, N), (x2, F ), (x3, F )} et la séquence d’évènements produite par le cycle estba.

45

(a) (b)

y1 [U]

(x1,N)

(x2,F)

(x3,F)

(x0,N)

(x2,F)

(x3,F)

b

y2 [U]

a

y11

(x2,F)

(x3,F)

(x3,F)

b

y21

a

FIGURE 6.6 – Cycle indéterminé (a) et séquence affinée (b) dans l’exemple 6.8.

Pour construire la séquence affinée, on part de l’état affinéy11 = {(x2, F ), (x3, F )} obtenude y1 en enlevant la couple(x1, N). Nous procédons à la construction de la séquenceaffinée par des occurrences répétées de la séquenceba.

L’évènementb conduit à l’étaty12 = {(x3, F )} (voir figure 6.6(b)) à partir du quel l’évène-menta ne peut pas se produire et la séquence affinée s’arrête. Ainsil’unique cycle incer-tain du diagnostiquateur n’est pas indéterminé. Nous concluons que le système est diag-nostiquable, comme déjà vu dans l’exemple 6.7. ⋄

Enfin, nous présentons un exemple d’AFD non diagnostiquable.

Exemple 6.9Considérons l’AFD dans la figure 6.7(a) où l’ensemble des évènementsobservables estEo = {a, b}, l’ensemble des évènements réguliers estEreg = {ε1} etl’ensemble des évènements de panne estEf = {εf}. Le diagnostiquateur de cette AFDest montré dans la figure 6.7(b). On peut voir qu’il existe dans le diagnostiquateur un seulcycle incertain illustré dans la figure 6.8(a)

y0 [U ]a−→ y1 [U ]

b−→ y0 [U ]

oùy0 = {(x0, N), (x3, F )} et la séquence du cycle estab.

Pour construire la séquence affinée, on part de l’état affinéy10 = {(x3, F )} obtenu dey0en enlevant la couple(x0, N). Nous procédons à la construction de la séquence affinéepar des occurrences répétées de la séquenceab.

Après l’occurrence de l’évènementa nous atteignons l’étaty11 = {(x3, F )} à partir duquell’occurrence de l’évènementb produit y20 = {(x3, F )} (voir figure 6.8(b)). Etant donnéquey10 = y20 la séquence affinée peut être poursuivi indéfiniment. Par conséquent, le cycleincertain du diagnostiquateur est aussi indéterminé. Nousconcluons que le système estnon diagnostiquable.

Remarquons en effet que les deux séquencesεf(ab)k et (aε1b)k produisent la même ob-

servation. Cela signifie que si la séquenceεf(ab)k est générée par le système, après le

panne, nous aurons une observation d’une longueur illimitée qui produit toujours un étatde diagnostic incertain et ne permet pas de détecter l’apparition de la panne. ⋄

46

a,b

x0 x1

x3

ef

a (x0,N)

(x3,F)

(x1,N)

(x2,N)

(x3,F)

(x3,F)

b a

a

a,b

y0 [U] y1 [U]

y2 [F]

b

(a) (b)

x2

e1 b

FIGURE 6.7 – L’automateG dans l’exemple 6.9 (a) et son diagnostiquateur (b).

(a) (b)

(x0,N)

(x3,F)

(x1,N)

(x2,N)

(x3,F)

a

y0 [U] y1 [U]

b

(x3,F)

(x3,F)

a

y01 y1

1

b (x3,F)

y02

FIGURE 6.8 – Cycle indéterminé (a) et séquence affinée (b) dans l’exemple 6.9.

47

Chapitre 7

Synthèse modulaire par produitsynchrone

Un système complexe est souvent composé de plusieurs sous-systèmes plus simples quiinteragissent entre eux. Dans cette section, nous montronsune technique pour constru-ire un modèle d’un système global parsynthèse modulaire, à savoir la composition demanière appropriée de modèles des sous-systèmes (modules). Nous supposons que chaquemodule est décrit par un AFD ; le modèle du système global est un AFD construit en util-isant leproduit synchrone. Cette opération, noté‖, a précédemment été définie commeune opération sur les langages (voir Définition 2.14) ; ici nous montrons qu’elle peut êtreégalement définie sur la structure de transition d’un AFD.

Précisons d’abord comment l’interaction entre les différents sous-systèmes est modéliséedans cette approche. Nous considérons par souci de simplicité le cas de deux modules àcomposer, mais ce que nous disons peut être généralisé à la composition de plus de deuxmodules.

Supposons que nous ayons deux modules (à savoir, AFD)G′ etG′′ dont les alphabets sont,respectivement,E ′ et E ′′. SoitE = E ′ ∪ E ′′ l’union des deux alphabets ; cet ensemblepeut être divisé en trois sous-ensembles disjoints illustrés dans la figure 7.1.– Symboles dansE ′ \E ′′, à savoir, ceux qui appartiennent uniquement au premier alpha-

bet : sont appelés lesévènements privatifs deG′.– Symboles dansE ′′ \E ′, à savoir, ceux qui appartiennent seulement au deuxième alpha-

bet : sont appelés lesévènements privatifs deG′′.– Symboles dansE ′ ∩ E ′′, à savoir, ceux qui sont communs aux deux alphabets : sont

appelésévènements synchronisés.Le système globaleG, dont l’espace des états est notéX, est donné par de la compositiondes modulesG′ etG′′, dont l’espace état est désigné, resp.,X ′ etX ′′. On aX ⊆ X ′×X ′′,à savoir, un état deG prend la formex = (x′, x′′) ∈ X, oùx′ ∈ X ′ etx′′ ∈ X ′′.

Un évènement privatif d’un module peut se produire chaque fois que le module est dansun état dans lequel l’évènement est actif, quel que soit l’état dans lequel l’autre module

48

E’ \ E” E’ ∩ E” E” \ E’

E’ E”

FIGURE 7.1 – Partition de l’alphabetE = E ′∪E ′′ dans les trois sous-ensemblesE ′ \E ′′,E ′ ∩ E ′′ etE ′′ \ E ′.

est : en fait, les évènements privatifs d’un module sont ignorés par l’autre module. Aucontraire, les évènements synchronisés ne peuvent être exécutées que si les deux modulessont dans des états où l’évènement est actif. En outre, il doit être exécuté simultanémentsur les deux modules (d’où le nomsynchronisé). Ainsi, siw est un mot généré parG, sesprojections sur les alphabetsE ′ etE ′′ seront des mots générés, resp., parG′ et parG′′.

Nous pouvons donner la définition suivante.

Définition 7.1 SoitG′ etG′′ deux AFD. Leurproduit synchroneest l’AFDG qui génèrelangageL(G) = L(G′) ‖ L(G′′) et accepte le langageLm(G) = Lm(G

′) ‖ Lm(G′′). Le

nouveau AFD est désigné parG = G′ ‖ G′′. N

La produit synchrone de deux AFD peut être déterminé avec l’algorithme suivant.

Algorithme 7.1 Produit synchrone de deux AFD.Entrée :deux AFDG′ = (X ′, E ′, δ′, x′

0, X′m) etG′′ = (X ′′, E ′′, δ′′, x′′

0, X′′m)

Sortie : un AFD G = (X,E, δ, x0, Xm) tel queL(G) = L(G′) ‖ L(G′′) et Lm(G) =Lm(G

′) ‖ Lm(G′′).

1. SoitE = E ′ ∪ E ′′.

2. Soit x0 = (x′0, x

′′0). (L’état initial deG est donnée par le produit cartésien des états

initiaux deG′ etG′′)

3. Soit X = ∅ etXnew = {x0}. (A la fin de l’algorithmeX ⊆ X ′ × X ′′ contiendratous les états deG, alors que l’ensembleXnew contient à chaque étape les états deG encore à explorer.)

4. Sélectionnez un étatx = (x′, x′′) ∈ Xnew.

(a) Pour tout e ∈ E :

49

FIG 7.2

c

stock convoyeur robot

a b

FIGURE 7.2 – Disposition de l’atelier de production dans l’exemple7.1

i. Soit

δ((x′, x′′), e) =

(x′, x′′) si e ∈ E ′ \ E ′′, δ′(x′, e) = x′

(x′, x′′) si e ∈ E ′′ \ E ′, δ′′(x′′, e) = x′′

(x′, x′′) si e ∈ E ′ ∩ E ′′, δ′(x′, e) = x′, δ′′(x′′, e) = x′′

non defini autrement

ii. Si l’état x = δ(x, e) est défini etx 6∈ X∪Xnew alorsXnew = Xnew∪{x}.(b) SoitX = X ∪ {x} etXnew = Xnew \ {x}.

5. Si Xnew 6= ∅ alors aller à 4.

6. Soit Xm = X ∩ (X ′m ×X ′′

m) (Un étatx deG est final si il est le produit cartésiend’un état final deG′ et un état final deG′′. �

On donne maintenant un exemple d’application de cet algorithme.

Exemple 7.1Considérons un atelier de production composé d’un robot et d’une zone destockage qui contient deux places disponibles (on dit que sacapacité est2). Le robotchoisit des objets dans un convoyeur qui est toujours plein (évènementa) et les déposedans la zone de stockage (évènementb). Les objets peuvent ensuite être retirés (évènementc) de la zone de stockage. La figure 7.2 représente la disposition de cette structure.

L’AFD avec alphabetE ′ = {a, b} dans la figure 7.3(a) modélise le robot :x′0 désigne

l’état robot inoccupé, x′1 désigne l’étatrobot en fonctionnement. L’AFD avec alphabet

E ′′ = {b, c} dans la figure 7.3(b) modélise la zone de stockage : chaque étatx′′k désigne le

nombrek d’objets qu’elle contient (pourk = 0, 1, 2). Le modèle du convoyeur n’est paspris en compte parce que il est toujour plein.

Si le robot est inoccupé, il peut prendre un objet, et cela indépendamment de l’état dela zone de stockage. Pareil, si la zone de stockage n’est pas vide, un objet peu en êtreretiré et cela indépendamment de l’état du robot. Ceci est lerésultat du fait quea est unévènement privatif deG′, et quec est un évènement privatif deG′′. A l’inverse, le dépôtd’un objet dans la zone de stockage peut seulement avoir lieusi le robot a choisi un objet

50

b

x0’

a x1’

c

x0”

b x1”

c

b x2”

c (x0’ ,x0” )

(x0’ ,x1” )

(x0’ ,x2” )

(x1’ ,x0” )

b

(x1’ ,x1” )

(x1’ ,x2” )

c

c c

a a a b

(a) (b)

(c)

FIGURE 7.3 – (a) Model du robot. (b) Model de la zone de stockage 2. (c) Leur produitsynchrone.

(étatx′1) et si la zone de stockage n’est pas pleine (étatx′′

0 ou x′′1). Ceci est le résultat du

fait queb est un évènement synchronisé des deux modules.

L’automate qui modélise le système global est l’AFD dans la figure 7.3(c), représentantle produit synchrone des deux modules.

Etape 1 de l’algorithme : l’alphabet deG est défini parE = {a, b, c}.

Etape 2 : l’état initial deG est défini parx0 = (x′0, x

′′0).

Etape 3 : on aX = ∅ etXnew = {(x′0, x

′′0)}.

Etape 4 : nous choisissons(x′0, x

′′0) ∈ Xnew. L’évènementa appartenant exclusivement

à G′ est actif dansx′0 et conduit àx′

1, ainsi δ((x′0, x

′′0), a) = (x′

1, x′′0), et nous ajoutons

(x′1, x

′′0) àXnew. L’évènementc appartenant exclusivement àG′′ n’est pas actif dansx′′

0,ainsi δ((x′

0, x′′0), c) est non défini. L’évènement synchroniséb n’est pas actif dansx′

0 etactif dansx′′

0, ainsiδ((x′0, x

′′0), b) est non défini : en fait, pour être défini, l’évènement doit

être actif dans les deux modules. Nous changeons l’état(x′0, x

′′0) deXnew versX.

À l’étape 5 on aXnew = {(x′1, x

′′0)} et on revient à l’étape 4.

Etape 4 : nous choisissons(x′1, x

′′0) ∈ Xnew. L’évènementa appartenant exclusivement à

G′ n’est pas actif dansx′1, ainsiδ((x′

1, x′′0), a), est non défini. L’évènementc appartenant

exclusivement àG′′ n’est pas actif dansx′′0, ainsiδ((x′

1, x′′0), c) est non défini. L’évènement

synchroniséb est actif enG′ dansx′1 conduisant àx′

0 et est aussi actif enG′′ dansx′′0

conduisant àx′′1, ainsiδ((x′

1, x′′0), b) = (x′

0, x′′1), et nous ajoutons(x′

0, x′′1) à Xnew. Nous

changeons l’état(x′1, x

′′0) deXnew versX.

51

E ′ \ E ′′ E ′ ∩ E ′′ E ′′ \ E ′

x a b c

(x′0, x

′′0) (x′

1, x′′0) — —

(x′1, x

′′0) — (x′

0, x′′1) —

(x′0, x

′′1) (x′

1, x′′1) — (x′

0, x′′0)

(x′1, x

′′1) — (x′

0, x′′2) —

(x′0, x

′′2) (x′

1, x′′2) — (x′

0, x′′1)

(x′1, x

′′2) — — (x′

1, x′′1)

TABLE 7.1 – Table récapitulative des étapes de l’exemple 7.1.

Nous continuons à répéter la boucle jusqu’àXnew = ∅.

Les différentes étapes ont été récapitulées dans la Table 7.1. A l’étape 6 nous déterminonsXm = X ∩ ({x′

0} × {x′′0}) = {(x′

0, x′′0)}. ⋄

Une remarque importante peut être faite concernant la cardinalité de l’espace d’état dusystème composé. Si nous notons parn′ etn′′ le nombre d’états deG′ etG′′, leur produitsynchroneG peut avoir jusqu’àn′ × n′′ états, parce queX ⊆ X ′ ×X ′′. Supposons main-tenant que nous avonsk modules, chacun avecn états, leur produit synchrone pourraitavoir jusqu’ànk états. Doncla cardinalité de l’espace d’état d’un système composé peutgrandir exponentiellement avec le nombre de modules qui le composent. Ce phénomène,qui a été appelé l’explosion de l’espace d’état, est un des problèmes majeurs auxquelson doit faire face quand les automates sont utilisés pour modéliser des systèmes réels.Ce problème peut être en partie soulagé avec l’utilisation d’autres modèles à évènementdiscrets, comme les réseaux de Petri.

Finalement, on a remarqué dans la Section 2.4 que la produit synchrone de deux langagesavec le même alphabet est l’intersection de ces deux langages. Ainsi Algorithme 7.1 peutaussi être utilisé pour déterminerG = G′ ∩ G′′, c’est-à-dire, un AFDG qui génère etaccepte l’intersection des langages générés et acceptés par deux AFDG′ andG′′.

52

Chapitre 8

La commande supervisée

Ce chapitre est consacré à la théorie de lacommande superviséedue à P. Ramadge età W.M. Wonham [5]. Ces auteurs ont défini un cadre général pourla commande dessystèmes à évènements discrets logiques qui a reçu beaucoupd’attention en littérature.

Suivant le paradigme classique de l’automatique, dans la théorie de la commande su-pervisée on considère unprocédé, à savoir, un système àcontrôler, dont l’évolutionest guidée par un agent de contrôle appelésuperviseur. Ainsi, nous avons le schéma enrétroaction dans la figure 8.1 qui montre lesystème supervisé(ou système en boucle fer-mée), à savoir, le procédé soumis à l’action du superviseur.

procédé

G

Supervisor

S

entréé de commande mot généré

w L(G)

FIGURE 8.1 – Un procédéG contrôlé par un superviseurS.

Le superviseur observe les évènements générés par le procédé et guide son évolution, dés-activant certains évènements pour prévenir leur occurrence et autorisant d’autres évène-ments. Notez que selon ce paradigme, le superviseur peutinterdire certains évènements(c.à.d. actions) qui sont possibles pour le procédé mais il ne peut pas les déclencher. Ondit que le superviseur restreint le comportement du procédé.

53

8.1 Procédé, superviseur et système supervisé

Dans cette section, nous discutons les différentes composantes du système supervisé mon-tré dans la figure 8.1.

8.1.1 Procédé

Dans la théorie de la commande supervisée un procédéG est un système à contrôler.Son comportement est décrit par les séquences d’évènements(à savoir, le langage) qu’ilpeut générer sur un alphabetE. En particulier, deux langages peuvent être associés à unprocédé.– lecomportement closL(G) ⊆ E∗ est le langage clos par préfixe composé par l’ensem-

ble des séquences d’évènements que le système peut générer ;– le comportement marquéLm(G) ⊆ L(G) est le langage composée par les séquences

d’évènements générés par le système qui correspond à la réalisation de certaines tâches.Il est naturel d’utiliser un automate fini déterministe (AFD) pour modéliser une procédéG : son comportement clos correspond au langage généré et son comportement marquécorrespond au langage accepté.

8.1.2 Évènements contrôlables et incontrôlables

La définition suivante précise quelles sont les possibles actions de contrôle qu’un super-viseur peut appliquer à un procédé.

Définition 8.1 L’alphabet des évènementsE d’un procédé est partitionné comme suit

E = Ec ∪ Euc (avecEc ∩ Euc = ∅)

oùEc est le l’ensemble desévènements contrôlablesetEuc est l’ensemble desévènementsincontrôlables. N

L’idée est que lorsque le procédé est prête à exécuter un évènement contrôlablee ∈ Ec lesuperviseur peutdésactiverl’évènement, à savoir en empêcher l’occurrence. Au contraire,le superviseur n’a aucun moyen d’empêcher l’occurrence d’un évènement incontrôlablee′ ∈ Euc.

Exemple 8.1Considérons l’AFDG dans la figure 8.2, où le caractère “ :” désigne unévènement contrôlable. Dans ce cas, l’alphabetE = {a, b, c, d, e, f} est partitionné enEc = {a, b, d, f} etEuc = {c, e}.

Cet AFD représente une presse typographique qui est initialement à repos (état initialx0). Une fois que la forme imprimante a été encré (évènementa) la presse est prête àimprimer (étatx1). De cet état, l’opérateur peut commencer (évènementb) une opération

54

x0 x1 x2

d:

c

e

a:

b:

f:

x3

FIGURE 8.2 – Une procédéG représenté par un AFD.

d’impression (étatx2) ou peut mettre (évènementd) la presse hors ligne (étatx3) pournettoyer ou changer la forme imprimante. Lorsque la presse adémarré l’impression (étatx2) l’opération peut terminer avec succès (évènementc) et la presse revient à l’étatx1,ou une erreur d’impression peut se produire (évènemente) et dans ce cas, la presse vade façon autonome hors ligne. L’exécution d’une maintenance (évènementf ) ramène lamachine à l’état de répos.

Dans cet AFD l’état final coïncide avec l’état initial, pour indiquer que, à la fin d’un ouplusieurs impressions la machine devrait revenir à l’état de repos.

La notion d’évènements contrôlables et incontrôlables a une claire interprétation. A titred’exemple, l’évènementa désigné le fait que la presse est encrée : cette opération estef-fectuée par l’opérateur de la presse et il est raisonnable desupposer que cet évènementpeut être désactivé par un superviseur si nécessaire. Le même raisonnement s’appliqueaux évènementsb (début d’une opération d’impression),d (mise hors-ligne de la presse)ouf (effectuer la maintenance). Au contraire,e représente une défaillance d’impression :évidemment, cela est un évènement indésirable, mais le superviseur n’a aucun moyenpour l’empêcher. De la même manière, on suppose que l’évènementc est lui aussi incon-trôlable, car une fois que la presse a commencé à imprimer il n’y a aucune action qui peutl’empêcher de terminer l’opération.

�

8.1.3 Superviseur

Comme le montre la figure 8.1, on suppose que le superviseur observe le mot d’évène-mentsw ∈ L(G) généré par le procédéG.

Puisque l’action du superviseur dépend du mot observéw ∈ L(G), nous allons donnerune définition plus générale des évènements actifs.

Définition 8.2 Soit un AFDG = (X,E, δ, x0, Xm).

55

Pour chaque étatx ∈ X, l’ensemble des évènements actifs dansG à l’état x est

AG(x) = {s ∈ E | δ(x, s) est défini}.

Pour chaque motw ∈ L(G) l’ ensemble des évènements actifs dansG aprèsw est

AG(w) = {e ∈ E | we ∈ L(G)}.

N

Dans cette définition, par souci de simplicité, la même notation AG est utilisée pourindiquer deux objets différents : une applicationAG : X → 2E et une applicationAG : L(G) → 2E. Il est clair que pour un AFDG si l’état x = δ∗(x0, w) est atteintà partir de l’état initialx0 en générant le motw, on aAG(w) = AG(x).

Exemple 8.2Pour le procédé en figure 8.2 on peut écrireA(ε) = AG(x0) = {a},AG(a) = AG(x1) = {b, d}, AG(ab) = AG(x2) = {c, e} et ainsi de suite. �

Quand le procédé a généré un motw ∈ L(G), un évènement actif et contrôlablee ∈AG(w) ∩ Ec peut être désactivé par le superviseur, c’est à dire que le superviseur peutl’empêcher de se produire. Au contraire, le superviseur n’aaucun moyen de prévoir l’ap-parition d’un évènement actif et incontrôlablee′ ∈ A(w) ∩ Euc. Les évènements qui nesont pas désactivés par le superviseur sont ditsautorisés.

8.1.4 Entrées de commande

Un superviseur guide l’évolution d’un procédé par l’intermédiaire des entrées de com-mande qu’il génère.

Définition 8.3 Étant donné un procédéG dans l’alphabetE, uneentrée de commandeestun sous-ensemble d’évènementsξ ⊆ E. On note2E l’ensemble de toutes les entrées decommande possibles. N

Si e ∈ ξ alors l’évènemente est autorisé par le superviseur, alors qu’à l’inverse sie 6∈ ξ,alorse est désactivé. Puisque les évènements incontrôlables ne peuvent pas être désac-tivées par un superviseur, on applique la définition suivante.

Définition 8.4 Étant donné un procédéG et un motw ∈ L(G), une entrée de commandeξ est diteadmissible aprèsw si Euc ∩ AG(w) ⊆ ξ, c’est à dire qu’elle contient tous lesévènements incontrôlables qui sont actifs enG aprèsw. N

Exemple 8.3Considérons le procédé en figure 8.2. L’entrée de commandeξ = {a, b, c}est admissible aprèsa parce queA(a) = {b, d} et, par conséquent, parmi tous les évène-ments actifs, seul l’évènement contrôlabled est désactivé. La même entrée de commande

56

n’est pas permise aprèsab parce queAG(ab) = {c, e} et, par conséquent, elle désactivel’évènement actif et incontrôlablee. �

Nous pouvons enfin donner une définition formelle d’un superviseur.

Définition 8.5 Un superviseurS contrôlant un procédéG peut être représenté par unefonction

f : L(G) −→ 2E ,

appeléeloi de commande, qui génère une séquence d’entrées de commande admissibles

ξ0 = f(ε), ξ1 = f(e1), ξ2 = f(e1e2), · · ·

en réponse à la séquence d’évènementsw = e1e2 · · · ∈ L(G) générée par le procédé.N

Il est à noter que dans la définition précédente, on admet que,pour tout motw générépar le procédé, l’entrée de commandef(w) déclenchée par le superviseur est admissibleaprèsw.

Exemple 8.4Considérons de nouveau le procédé en figure 8.2. Supposons que le super-viseur veuille être sûr qu’à chaque fois que la presse est encrée, au plus une opérationd’impression pourra être effectuée afin de garantir une impression de haute qualité. Celasignifie que, après chaque évènementa (encrage), au plus un évènementb (lancer l’im-pression) peut se produire jusqu’à ce qu’un nouvel évènement a soit observé. Dans letableau en figure 8.3 est représentée la loi de commandef(w) d’un superviseur qui peutassurer ce comportement.

Comme on peut voir dans le tableau, le superviseur ne bloque initialement aucun évène-ment, c’est à dire que,f(ε) = f(a) = E. Cependant, dès queab est réalisé (donc uneopération d’impression a commencé), l’évènementb sera désactivé jusqu’à ce qu’un nou-vel évènementa soit réalisé, c’est à dire,f(ab) = f(abc) = f(abcd) = f(abcdf) =E \ {b} andf(abcda) = E. �

8.2 Superviseurs AFD et système supervisé

Bien que nous ayons précédemment défini un superviseur commeune fonctionf : L(G) →2E, il est aussi possible de représenter un superviseur comme un système à évènementsdiscrets, c.à.d. un AFDS = (X, E, δ, x0, Xm) sur le même alphabet que le procédéG = (X,E, δ, x0, Xm).

Voici comment un superviseur AFD fonctionne. A chaque fois qu’un évènement estgénéré par le procédé, le même évènement est exécuté par le superviseur. Lorsque le su-perviseur est dans un étatx donné, il envoie au procédé une entrée de commandeAS(x)qui contient tous les évènements actifs dansS à l’état x.

57

w x ξ = f(w)

ε x0 {a, b, c, d, e, f}a x1 {a, b, c, d, e, f}ab x2 {a, c, d, e, f}abc x1 {a, c, d, e, f}abcd x3 {a, c, d, e, f}abcdf x0 {a, c, d, e, f}abcda x1 {a, b, c, d, e, f}· · · · · · · · ·ad x3 {a, b, c, d, e, f}adf x0 {a, b, c, d, e, f}adfa x1 {a, b, c, d, e, f}· · · · · · · · ·

w x ξ = AS(x)

ε y0 {a, b, c, d, e, f}a y0 {a, b, c, d, e, f}ab y1 {a, c, d, e, f}abc y1 {a, c, d, e, f}abcd y1 {a, c, d, e, f}abcdf y1 {a, c, d, e, f}abcda y0 {a, b, c, d, e, f}· · · · · · · · ·ad y0 {a, b, c, d, e, f}adf y0 {a, b, c, d, e, f}adfa y0 {a, b, c, d, e, f}· · · · · · · · ·

FIGURE 8.3 – Loi de commande dans l’exemple 8.4 (à gauche). Loi de commande dansl’exemple 8.5 (à droite).

Ainsi, nous obtenons la procédure suivante qui décrit l’évolution du système supervisé.

Procédure 8.1 (Evolution d’un système supervisé)Soit un procédéG = (X,E, δ, x0, Xm)commandé par un superviseurS = (X, E, δ, x0, Xm).

1. Initialement le procédéG est à l’étatx = x0 et le superviseur est à l’étatx = x0.

2. Soitw = ε.

3. Le superviseur génère l’entrée de commandeξw = AS(x).

4. Le procédé génère un évènemente ∈ AG(x) ∩ ξw et va à l’étatx′ = δ(x, e).

5. Le superviseur exécute l’évènemente et se rend à l’étatx′ = δ(x, e).

6. Soitw = we, x = x′, x = x′.

7. Répéter l’étape 3

Un exemple permettra de clarifier cette procédure.

Exemple 8.5Le superviseur décrit dans l’exemple 8.4 peut également être représenté parl’AFD S sur l’alphabetE illustré dans la figure 8.4. L’AFD possède deux états : à l’étatx0 tous les évènements sont actifs, à savoir, activés. Dès qu’un évènementb se produit,Spasse à l’étatx1 où b n’est pas actif. L’apparition de l’évènementa conduitS à nouveau àl’état x0.

58

b

a

a,c,d,e,f

S

c,d,e,f

x1 x0

FIGURE 8.4 – Un superviseur AFD pour le procédé en figure 8.2.

Pour montrer que le systèmeS est équivalent au superviseur décrit par le tableau sur lecôté gauche de la figure 8.3, les entrées de commandes sont représentées sur la droite. Pourchaque mot généré par le procédé contrôlé, l’étatx attient parS est représenté ainsi quel’ensemble des évènements actifs qui déterminent l’entréede commande. En comparantles deux tableaux de la figure 8.3, on peut immédiatement vérifier qu’ils décrivent lamême loi de commande. �

Un avantage important d’avoir un superviseur représenté comme un AFD est qu’on déter-mine immédiatement l’AFD qui représente le système supervisé. En fait, si l’on considèrel’Algorithme 8.1, nous pouvons directement voir qu’un motw généré par le système enboucle fermée est à la fois un mot deG (car généré par le système) et un mot deS (parceque, à chaque étape, l’évènement généré appartient à l’entrée de commande et il est doncactif dans systèmeS).

Définition 8.6 Soit un procédéG contrôlé par un superviseurS. Le système en bouclefermée(ou système supervisé) est l’AFD 1 S/G = G ∩ S = G ‖ S, dont le langage closestL(S/G) = L(G)∩L(S) et dont le langage marqué estLm(S/G) = Lm(G)∩Lm(S) =Lm(G) ‖ Lm(S). N

Il est à noter que nous pouvons écrireG ∩ S = G ‖ S parce queS et G ont le mêmealphabet. Ainsi, il est possible de construire le système enboucle fermée en utilisantl’opération deproduit synchrone‖ défini dans le chapitre précédent.

On remarque que si l’on considère un superviseur AFDS il y a deux possibilités.– Superviseur non-marquant. Le superviseur ne précise pas quels mots sont finaux et tous

les mots qui conduisent à un état final dans le procédé sont considérés comme finaux.Dans ce cas, on suppose que l’ensemble des états finaux du superviseur estXm = X(tous ses états sont finaux), et donc le langage marqué du système supervisé est

Lm(S/G) = Lm(G) ∩ Lm(S) = Lm(G) ∩ L(S)

c.à.d. qu’il contient tous les mots acceptés par le procédé qui sont maintenus soussurveillance.

1. Le nom deS/G (S surG) pour le système en boucle fermée indique qu’on l’obtient par l’action deS surG.

59

(x0, 0)

d

c

e

a b

f

(x1, 0) (x2, 1) (x1, 1)

(x3, 1)

d

f

S/G

(x0, 1)

a

(x3, 0)

FIGURE 8.5 – Le système supervisé dans l’exemple 8.6.

– Superviseur marquant. Le superviseur spécifie quels mots sont finaux et donc un motest final s’il conduit à la fois le procédé et le superviseur à un état final. Dans ce cas,nous supposons que l’ensemble des états finaux du superviseur estXm ( X (tous sesétats ne sont pas finaux).

Exemple 8.6Considérons le procédéG de la figure 8.2 contrôlé par le superviseurSillustré dans la figure 8.4. Le système en boucle ferméeS/G construit par compositionconcurrente est représenté en figure 8.5. Notons que dans ce cas, le superviseur est non-marquant : les états marqués dans le système supervisé sont tous les états(x, x) où x ∈Xm, a savoir(x0, x0) et (x0, x1). �

8.3 Spécifications de contrôle

Une spécificationdécrit quel est le comportement souhaité d’un système contrôlé : unsuperviseur doit être conçu pour veiller à ce que le système supervisé respecte une tellespécification.

Nous considérons ici deux types de spécifications.

Définition 8.7 (Spécification d’état) Étant donné un procédé dont l’espace d’état estX,unespécification d’étatconsiste en un sous-ensembleL ⊆ X qu’on appelleensemble desétats admissibles. N

Une telle spécification est représentée sur la figure 8.6. Lesétats se trouvant dans l’ensem-bleF = X \ L sont appelésétats interdits.

Définition 8.8 (Spécification de langage)Étant donné un procédé dont le langage closestL(G) ⊆ E∗, unespécification du langageconsiste en un langageK ⊆ E∗ qu’onappelleensemble des mots admissibles. N

60

L

états

interdits

F

X

états

admissibles

FIGURE 8.6 – Une spécification d’état pour un procédé avec un espace d’étatX.

Une telle spécification est représentée sur la figure 8.7. Lesmots du langageLK =L(G) ∩ K, qui sont générés par le procédé et sont également admissibles, sont appelésmots desirés. Les mots du langageFK = L(G)\K, qui sont générés par le procédé, maisne sont pas admissibles, sont appelésmots interdits.

L(G) K

E*

mots

interdits

mots

desirés

L K F

K

mots

admissibles

FIGURE 8.7 – Une spécification de langageK pour un procédé avec langage closL(G) ⊆E∗.

Dans les sections suivantes, nous allons discuter de comment il est possible de concevoirun superviseur capable de faire respecter ces deux types de spécifications.

8.4 Conception d’un superviseur pour les spécificationsd’états

Parlons d’abord du problème de contrôle dont nous allons parler dans cette section.

61

F

X

L

wuc Euc*

Fweak

FIGURE 8.8 – L’ensemble des états faiblement interditsFweak contient tous les états ad-missibles en rouge clair qui peut incontrôlablement atteindre un état interdit.

Définition 8.9 (Problème de contrôle pour une spécification d’état) Considérons unprocédéG avec l’ensemble des étatsX et soit une spécification qui consiste en un ensem-ble d’états admissiblesL ⊆ X. Trouver un superviseur maximalement permissif2 S telsque le système supervisé n’atteindra jamais un état interdit dansF = X \ L. N

8.4.1 États faiblement interdits

Pour éviter que les états dansF = X \ L soient atteints, il est nécessaire de désactiver ledéclenchement de tous les évènements menant d’un état admissiblex ∈ L à un état inter-dit x′ ∈ F . Cependant, il peut arriver qu’à partir d’un état admissible, il existe une suiteincontrôlable (à savoir, une séquence composée par des transitions incontrôlables) quidonne un état interdit et une telle séquence ne peut pas être désactivée par un superviseur.Pour cette raison, nous avons besoin d’introduire la définition suivante.

Définition 8.10 (États faiblement interdits) Étant donné un procédéG = (X,E, δ, x0, Xm)et un ensemble d’états admissibleL, nous définissons l’ensemble desetats faiblement in-terdits

Fweak = {x ∈ L | (∃wuc ∈ E∗uc) δ

∗(x, wuc) = x′ ∈ F}contenant tous les états admissibles du procédé à partir desquels un état interdit est acces-sible par une séquence qui ne contient que des évènements incontrôlables. N

Ceci est illustré à la figure 8.8, oùFweak est donnée par l’ensemble des états admissiblesà partir duquel un état interdit est accessible par une séquence incontrôlable (en rougeclair).

Ainsi, en présence d’évènements incontrôlables, le superviseur doit veiller à ce que leprocédé ne parvienne pas à un état interdit ou faiblement interdit. Le superviseur est dit

2. La notion de superviseur maximalement permissif pour unespécification d’état sera précisée dans laprochaine sous-section.

62

maximalement permissifs’il empêche seulement d’atteindre des états interdits ou faible-ment interdits.

8.4.2 Conception d’un superviseur

Nous pouvons maintenant présenter l’algorithme suivant pour construire le superviseurdésiré.

Algorithme 8.1 Conception d’un superviseur pour les spécifications d’étatEntrée :Un procédéG ; un ensemble d’états admissiblesL ⊆ X.Sortie : Un superviseurS maximalement permissif (qui représente aussi le système enboucle ferméeS/G).

1. Déterminer F ∪ Fweak, l’ensemble d’états interdits et faiblement interdits deG.

2. Si l’état initial deG appartient àF ∪ Fweak RETOUR : il n’y a pas de solution.

3. ÉmonderG de tous les étatsF ∪ Fweak et leurs arcs de sortie et d’entrée.

4. La structure restante est le superviseurS et aussi le modelé du système en boucleferméeS/G. �

L’algorithme consiste à débarrasserG de tous les états interdits et faiblement interdits.Notez que l’automate finalS peut contenir certains états inaccessibles, et que l’on peutencore réduire l’automate pour les supprimer (ce qui ne change pas le comportement enboucle fermée).

Exemple 8.7Considérons le système de transport illustré à la figure 8.9.(a). Le systèmeest composé de deux AGV (véhicules à guidage automatique) qui se déplacent sur deuxpistes différentes. Le premier AGVG1 dessert quatre stations (A, B, C et D). Le deuxièmeAGV G2 dessert deux stations (D et E). Les modèles AFD des deux AGV sont présentésà la figure 8.9.(b) : nous supposons que l’emplacement initial et final de l’AGSG1 sont lastation A, tandis que la position initiale et finale de l’AGSG2 sont la station E. L’alphabetdeG1 estE1 = {a, b, c, d}, tandis que l’alphabet deG2 estE2 = {e, f}. Nous supposonsque les évènementsb et c sont incontrôlables.

Nous construisons le modèle du procédéG = G1 ‖ G2, également montré à la fig-ure 8.9.(b) par produit synchrone sur l’alphabetE = E1 ∪ E2 = {a, b, c, d, e, f}. Ici unétat, disons AE, indique que le premier AGV est dans la station A et la seconde dans lastation E.

Le système doit être contrôlé pour faire respecter la spécification suivante : les deux AGVne devraient pas être dans la même station (c.à.d., dans la station D) au même momentpour éviter une collision. Ainsi, nous avons un ensemble d’états admissibles

L = {x′x′′ | x′ ∈ {A,B,C,D}, x′′ ∈ {D,E}, x′ 6= x′′}

63

A B C

d:

a: b

G1

E Df:

e: G2

cD

A

B

C

D E

a

b c

d

f

e

AE

a: b

Gf:e:

a: b

BE CE

f:e:f:e:

d:

c

f:e:

c

DE

ADBD CD DD

(a)

(b)

FIGURE 8.9 – Un système de transport constitué par deux AGS dans l’exemple 8.7 (a).Les modèles AFD de AGVG1 etG2 ; le modèleG du système global (b).

64

AE

a b

S

BE CE

fe

d

c

DE

AD

FIGURE 8.10 – Le superviseurS et aussi le système en boucle ferméeS/G dans l’exem-ple 8.7.

L’état DD interdit deG est en rouge foncé dans la figure 8.9.(b). En raison de la présencedes évènements incontrôlablesb et c l’ensemble des états faiblement interdits contient lesétats BD et CD colorés en rouge clair. En retirant les états interdits et faiblement interdits,nous obtenons le superviseurS illustré à la figure 8.10. �

Nous concluons avec deux observations finales concernant lesuperviseur conçu par l’Al-gorithme 8.1.

Tout d’abord, on constate que ce superviseur est :– admissible, à savoir, il désactiveuniquement les évènements incontrôlables;– correct, à savoir, il désactivetoutesles apparitions d’évènements qui conduisent à un

état interdit ;– maximalement permissif, à savoir, il désactiveuniquementl’apparition d’évènements

qui conduisent à un état interdit ou faiblement interdit.A titre d’exemple, le superviseur de la figure 8.10 désactive: l’évènement contrôlableedepuis les états BE, CE et DE, et les évènements contrôlablea depuis l’état AD.

Deuxièmement, on remarque que le système en boucle ferméeS/G coïncide avec le su-perviseurS. En fait, commeS affineG, on aL(S) ⊆ L(G) andLm(S) ⊆ Lm(G). Ainsi,le système en boucle ferméeS/G = G ‖ S = G∩ S (voir Paragraphe 8.2) a langage closL(S/G) = L(G) ∩ L(S) = L(S) et langage marquéLm(S/G) = Lm(G) ∩ Lm(S) =Lm(S).

8.5 Conception d’un superviseur pour les spécificationsde langage

Présentons d’abord le problème que nous allons évoquer danscette section.

65

Définition 8.11 (Problème de contrôle pour les spécifications de langage)Consid-érons un procédéG avec langage closL(G) ⊆ E∗ et soit une spécificationK ⊆ E∗

consistant en un langage clos par préfixe3 de mots admissibles. Trouvez un superviseurmaximalement permissif4 S tel queL(S/G) ⊆ K. N

En d’autres termes, on cherche à trouver un superviseurS tel que le système en bouclefermée génère seulement les mots autorisés dansLK = L(G) ∩K.

8.5.1 Mots faiblement interdits

Pour éviter que des mots interdits soient atteints, il est nécessaire, une fois qu’un motautoriséw′ ∈ LK a été généré, de désactiver le déclenchement de tous les évènementse qui produisent un mot interditw = w′e ∈ FK . Cependant, il peut arriver qu’une foisqu’un mot permisw′ ait été générée, il existe une séquence incontrôlablewuc (à savoir,une séquence constituée par un ou plusieurs évènements incontrôlables) de telle sorte quew = w′wuc ∈ FK est un mot interdit et une telle séquence ne peut pas être désactivé parun superviseur. Pour cette raison, nous avons besoin d’introduire la définition suivante.

Définition 8.12 (Mots faiblement interdits) Soit un procédéG = (X,E, δ, x0, Xm) etune spécification de langageK, clos par préfixe. On définit l’ensemble desmots faible-ment interdits

FKweak = {w′ ∈ LK | (∃wuc ∈ E∗

uc) w = w′wuc ∈ FK}

contenant tous les mots autorisés qui peuvent être poursuivis dans un mot interdit par uneséquence qui ne contient que des évènements incontrôlables. N

Ceci est illustré sur la figure 8.11, oùFKweak est représenté en rouge clair.

Ainsi, en présence d’évènements incontrôlables, le superviseur doit veiller à ce que lesystème ne génère pas un mot interdit ou un mot faiblement interdit. Le superviseur estmaximalement permissifs’il empêche seulement de générer des mots interdits ou faible-ment interdits.

8.5.2 Automate composé et contrôlabilité

Dans cette section, nous examinons comment est-il possiblede contrôler le procédé, desorte qu’aucun mot interdit ne soit généré. Notez que l’on doit également vérifier s’ilexiste des mots faiblement interdits, et les empêcher aussid’être générés.

3. Une version généralisée dit queK peut ne pas être clos par préfixe. Dans ce cas, S doit assurer queL(S/G) ⊆ K et queLm(S/G) ⊆ K.

4. La notion de superviseur maximalement permissif pour lesspécifications de langage sera détailléedans la prochaine sous-section.

66

L(G) K

E*

F K L

K

wuc Euc*

weakF

K

mots

admissibles

FIGURE 8.11 – L’ensemble des mots faiblement interditsFKweak pour une spécification de

langageK contient tous les mots acceptés en rouge clair qui peuvent être incontrôlable-ment poursuivis dans un mot interdit.

Pour résoudre ce problème, nous allons utiliser un AFD pour représenter la spécificationde langage.

Définition 8.13 (Automate de spécification)Étant donné une spécification de langageK ⊆ E∗, l’automate de spécificationcorrespondantH = (X ′, E, δ′, x′

0, X′m) est tel que

Lm(H) = K etL(H) = K, à savoir, cet AFD accepteK et génère tous ses préfixes.N

Notez que lorsqueK est clos par préfixe on aLm(H) = L(H) = K doncX ′m = X ′, à

savoir, tous les états deH sont finaux.

Exemple 8.8L’exemple suivant sera utilisé dans cette section pour présenter la concep-tion d’un superviseur pour les spécifications de langage. Considérons une cellule de fab-rication dont la disposition est illustrée à la figure 8.12.(a). Les deux principales com-posantes de cette cellule sont une machine et un robot. La machine est chargée avec unepartie (évènementa) et après l’avoir usiné (évènementb) la délivre en sortie dans un stock(évènementc). Le robot prend une partie du stock (évènementd) et la déplace (évènemente) sur un convoyeur qui l’enlève.

Dans la figure 8.12.(b) nous avons l’AFDG1 sur l’alphabetE1 = {a, b, c} qui décrit lamachine et l’AFDG2 sur l’alphabetE2 = {d, e} qui décrit le robot. Le procédé est décritpar l’AFD G = G1 ‖ G2 sur l’alphabetE = E1 ∪ E2 obtenu par produit synchrone desdeux modules. Cet automate est également représenté sur la figure 8.12.(b). Supposonsque l’ensemble des évènements contrôlables estEc = {a, d} alors que l’ensemble desévènements incontrôlables estEuc = {b, c, e}.

La spécification est la suivante. D’abord, le robot doit démarrer une opération de déplace-ment (évènementd) seulement après que la machine ait produit une partie (casc). En

67

FIG 8.12

x0 x1 x2

c

a: bG1

x0 x1

e

d:

G2

x00

c

a: b

Ged:

a: b

x10 x20

x01 x11 x21

ed:ed:

c

a cb

machine stock robot

d e

convoyeur

(a)

(b)

FIGURE 8.12 – La disposition d’une cellule de fabrication (a). Le modèleG1 de la ma-chine, le modèleG2 du robot et le modèleG = G1 ‖ G2 du système global (b).

68

c

d

a,b,e

H

a,b,e

x'1x'0

FIGURE 8.13 – Automate de spécification pour la cellule de fabrication dans l’exem-ple 8.8.

outre, étant donné que le stock a une capacité d’un, la machine devrait mettre une nou-velle pièce dans le stock seulement après que le robot ait pris la précédente. En d’autrestermes, les évènementsc etd doivent être exécutées alternativement à partir d’unc. Ceciest représenté par l’automate de spécificationH dans la figure 8.13. �

Il peut sembler naturel d’utiliser l’automate de spécification en tant que superviseur : enfait, dans un tel cas, le système en boucle ferméeG ‖ H génère le langageL(G)∩L(H) =L(G)∩K = LK contenant seulement des mots admissibles. Cependant, utiliserH commesuperviseur peut être impossible car il n’y a aucune garantie queH ne produit que desentrées de commande admissibles, à savoir, il peut essayer de désactiver une transitionincontrôlable pour éviter de générer un mot interdit. Cela se produit, évidemment, s’ilexiste des mots faiblement interdits.

Pour cette raison, on peut aussi définir la propriété suivante.

Définition 8.14 Soit G un procédé. Un automate avec le même alphabetH est appeléadmissible pourG si, lorsqu’il est utilisé en tant que superviseur, il produit toujours desentrées de commande admissibles. N

Nous montrons maintenant comment il est possible de vérifiersi un automate donnéH estadmissible pour un procédéG. La procédure nécessite de construire l’automate composéF = G ‖ H qui génère l’ensemble des mots desirésLK . Notez que par constructionchaque état de cet automate est une couple(x, x′) où x ∈ X est un état deG etx′ ∈ X ′

est un état deH.

La définition suivante caractérise les situations dans lesquelles l’automate de spécificationne peut pas produire une entrée de commande admissible en raison de la présence d’unmot faiblement interdit.

Définition 8.15 Un état(x, x′) de l’automate composéF = G ‖ H est appéle :– incontrôlables’il existe e ∈ Euc tel quee ∈ AG(x) ∧ e 6∈ AF ((x, x

′)), à savoir,l’évènement incontrôlablee est actif dansG à l’étatx, mais pas actif dansF à l’état(x, x′) ;

– faiblement incontrôlables’il existe un mot d’évènements incontrôlablesw ∈ E∗uc

69

x00,0c

e

a bx10,0 x20,0 bax00,1 x10,1 x20,1

d d

ba

e

x11,1x01,1

c

ba

x11,0 x21,0x01,0

c

x21,1

c

e e e e

d

F

FIGURE 8.14 – Le produit synchroneF = G ‖ H dans l’exemple 8.9.

(éventuellement vide) qui conduitF de l’état(x, x′) à un état incontrôlable quelconque.On noteU l’ ensemble des états incontrôlableset Uweak l’ ensemble des états faiblementincontrôlables. Notez que par définitionU ⊆ Uweak. N

La signification des états incontrôlables est la suivante : un tel état est atteint lorsque l’ongénère un mot autoriséw′ de telle sorte que la survenance d’uneuc d’évènements incon-trôlables donne un mot interditw = w′euc. De même, un état faiblement incontrôlable estatteint lorsqu’on génère un mot autoriséw′ tel que l’occurrence d’une séquence d’évène-ments incontrôlableswuc donne un mot interditw′wuc. Il est évident que un mot est faible-ment interdit si et seulement si il conduit l’automateF à un état faiblement incontrôlable.

Nous pouvons énoncer le résultat suivant.

Proposition 8.1 Un automate de spécification est admissible par rapport au procédéG siet seulement si l’automate composéF = G ‖ H n’a pas d’état incontrôlable. �

Exemple 8.9Considérons à nouveau la cellule de fabrication discutée dans l’exemple 8.8.Pour déterminer si l’automate de spécificationH dans la figure 8.13 est admissible, on lecompose avec le procédéG à la figure 8.12 pour obtenir l’automate composéF illustréà la figure 8.14 (ignorer les arcs en pointillésc marqués). Dans cet automate un étatxij,k désigne dans un format compact un état(xij , x

′k) où le procédéG est à l’étatxij et

l’automate de spécificationH est dans l’étatx′k.

Dans le tableau suivant, pour chaque évènement incontrôlable de l’ensembleEuc ={b, c, e} nous avons répertorié les états du procédéG dans lesquels il est actif.

70

évènement incontrôlableactif dansG à l’état

b x10, x11

c x20, x21

e x01, x11, x21

Nous pouvons observer ce qui suit.– l’évènement incontrôlableb ne provoque pas des états incontrôlables dansF . En fait,

pour tous les états où le premier composant estx10 oux11 (à partir du tableau ci-dessus)tel évènement est activé dansF .

– L’évènement incontrôlablec provoque des états incontrôlables dansF . En fait, il ex-iste deux états dansF dont la première composante est soitx20 ou x21 (à partir dutableau ci-dessus), mais l’évènement n’est pas activé. Cesétats sontx20,1 et x21,1 : ilssont doncincontrôlables. Dans la figure, les deux états incontrôlables sont marqués enrouge foncé. Pour une meilleure compréhension, nous avons également ajouté dans lafigure un arc en pointillé avec l’étiquettec sortant des deux états pour mettre en év-idence que l’incontrolabilité suit de la désactivation de l’évènementc (ces deux arcssont manquants dansF ).En outre, nous avons aussi deuxétats faiblement incontrôlablesx10,1 et x11,1 (marquéen rouge clair) à partir de laquelle une séquencewuc = b d’évènements incontrôlablesconduit à un état incontrôlable.

– l’évènement incontrôlablee ne provoque pas des états incontrôlables dansF . En fait,pour tous les états deF dont la première composante estx01, x11 ou x21 (à partir dutableau ci-dessus) tel évènement est activé dansF .

En conséquence, nous concluons que l’automate de spécification H n’est pas admissiblecar il contient des états incontrôlablesU = {x20,1, x21,1}. L’ensemble d’états faiblementincontrôlables estUweak = {x10,1, x11,1, x20,1, x21,1}. Tous les mots conduisant à un étatfaiblement incontrôlable sont faiblement interdits. À titre d’exemple, considérons le motw′ = abca queF rendements étatx10,1 à partir de l’état initial. Ce mot est faiblementinterdit, car il peut être poursuivi avecwuc = bc le mot interditw = w′wuc = abcabccorrespondant au fait que la machine a mis une deuxième partie dans le stock avant quela première partie ait été enlevée par le robot. �

8.5.3 Conception d’un superviseur

Si un automate de spécification est admissible, alors il est le superviseur désiré. Sinon, ilest nécessaire de restreindre davantage le comportement duprocédé pour assurer qu’au-cun mot faiblement interdit n’est généré. L’algorithme suivant montre comment un super-viseur peut être conçu.

Algorithme 8.2 Conception d’un superviseur pour les spécifications de langageEntrée :Un procédéG ; une spécification de langageK ⊆ E∗ décrite par l’automateH.Sortie :Un superviseur maximalement permissifS ; le système en boucle ferméeS/G.

71

x00,0c

e

a bx10,0 x20,0 x00,1

d

e

x01,1

ba

x11,0 x21,0x01,0

c

e e S

FIGURE 8.15 – SuperviseurS dans l’exemple 8.10.

1. Construire par produit synchrone l’automate composéF = G ‖ H.

2. Calculer Uweak, l’ensemble d’états faiblement incontrôlables deF .

3. Si Uweak = ∅ alors RETOUR :– S = H, parce queH est admissible et peut être utilisé en tant que superviseur ;– S/G = F , à savoir,F décrit le système en boucle fermée.

4. Si l’état initial deF appartient àUweak alors RETOUR : il n’y a pas de solution.

5. ÉmonderF en enlevant tous les étatsUweak et leurs arcs de sortie d’entrée.

6. La structure restante est le superviseurS et aussi le modelé du système en boucleferméeS/G. �

Cet algorithme fonctionne comme suit. D’abord, il vérifie sil’automate de spécificationest admissible : dans ce cas, il peut être utilisé en tant que superviseur, à savoir,S = H etcomme d’habitude le système en boucle fermée estS/G = G ‖ S = F . SiF a des étatsfaiblement incontrôlables (c’est-à-dire, ils existent des états faiblement interdits) il estnécessaire d’éviter de les atteindre. En retirant tous ces états, nous avons un automate quigénère des mots admissibles et non faiblement interdits : ildécrit le superviseurS maisen même temps, décrit également le système en boucle ferméeS/G (on peut facilementvérifier que dans ce casS/G = G ‖ S = S) : un tel superviseur est appelé unsuperviseurmonolithique.

Notez que si l’automate finaleS contient certains états inaccessibles, il peut encore êtreémondé pour les enlever.

Exemple 8.10Considérons à nouveau la cellule de fabrication discuté dans l’exemple 8.8.L’automate composéF illustré à la figure 8.14 n’est pas admissible, tel que discuté dansl’exemple 8.9. S’il est émondé, éliminant tous les états faiblement incontrôlables, on ob-tient le superviseur illustré à la figure 8.15. �

72

Comme dernière remarque, nous observons que le superviseurconstruit par l’Algorithme 8.2est :– admissible, à savoir, il désactive uniquement les évènements incontrôlables ;– correct, à savoir, le système en boucle fermée génèreseulement des mots permis;– maximalement permissif, à savoir, il empêche le système de générer desmots faiblement

interdits.

73

Annexe A

Fonctions et relations

A.1 Définitions de base

Définition A.1 Unefonctionf : X → Y d’un ensembleX (appelédomaine) à l’ensem-ble Y (appelécodomaine) associe un élémentx ∈ X à un élémentf(x) ∈ Y . Unefonction est appeléetotalesi elle est définie pour tous les éléments de son domaine etpartielleautrement. N

En figure A.1 on a représenté graphiquement une fonctionf : X → Y . Le domaine estX = {x1, x2, x3, x4}, le codomaine estY = {y1, y2, y3} et on a :f(x1) = y1, f(x2) = y1,f(x3) = y2, La fonction n’est pas totale parce que elle n’est pas définiepourx4 ∈ X.

Exemple A.1Etant donné l’ensemble des entiersZ = {0,±1,±2, . . .} et l’ensembleS = {−, 0,+}, la fonctionf : Z → S définie comme

f(x) = signe(x) =

− si x < 0,

0 si x = 0,

+ si x > 0,

associe à chaque entierx ∈ Z son signe. Cette fonction est totale. ⋄

Exemple A.2Etant donné l’ensemble des nombres naturelsN = {0, 1, 2, . . .}, la fonctionf : N → R définie commef(x) = x−1 associe à un nombre naturelx ∈ N son inverse.Cette fonction est partielle parce qu’elle n’est pas définiepourx = 0. ⋄

Une fonction associe à un élément dans le domaineX un seul élément dans le codomaineY . Nous pouvons généraliser ce concept définissant unerelationqui associe à un élémentdeX un sous-ensemble deY . Introduisons d’abord la notion d’ensemble despartiesd’unensemble.

74

1111

Exemple A.1 Etant donné l'ensemble des entiers Z = {0, ± 1, ± 2,. . .} et l'ensemble S =

x1

X

(domaine)

Y

(co-domaine)

x2

x3

x4

y1

y2

y3

FIGURE A.1 – Représentation graphique d’une fonctionf : X → Y .

Définition A.2 Etant donné l’ensemble1 X, sonensemble des parties

2X = {U | U ⊆ X}

est l’ensemble de tous les sous-ensembles deX. N

Notez que lorsqueX est un ensemble fini de cardinalité|X| = n son ensemble des partiesa cardinalité|2X| = 2n. Ceci explique la notation utilisée pour dénoter ensemble desparties d’un ensemble.

Exemple A.3Etant donné l’ensembleX = {1, 2, 3}, son ensemble des parties est

2X = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

L’ensembleX a cardinalitén = 3 et donc l’ensemble2X a cardinalité23 = 8. ⋄

Nous pouvons formellement définir une relation comme suit.

Définition A.3 Unerelationd’un ensembleX à un ensembleY est un fonction

R : X → 2Y

associant à chaque élément deX un sous-ensembleR(x) ⊆ Y .

Équivalemment, nous pouvons définir une relation de l’ensembleX à l’ensembleY commeun sous-ensemble

R = {(x, y) | x ∈ X, y ∈ R(x) } ⊆ X × Y.

Pour dénoter que la couple(x, y) appartient àR on écrit(x, y) ∈ R or xRy. N

1. Cette définition s’applique à tous ensemblesX , que ces soit finis, dénombrables ou non dénom-brables.

75

x1

X

(domaine)

Y

(co-domaine)

x2

x3

x4

y1

y2

y3

FIGURE A.2 – Représentation graphique d’une relationR ⊂ X × Y .

En figure A.2 on a représenté graphiquement une relationR ⊂ X×Y oùX = {x1, x2, x3, x4}et Y = {y1, y2, y3}. On a :R = {(x1, y1), (x1, y3), (x2, y1), (x3, y2), (x3, y3)} . Cette re-lation est aussi une fonctionR : X → 2Y avecR(x1) = {y1, y3}, R(x2) = {y1},R(x3) = {y2, y3} etR(x4) = ∅.

Exemple A.4Etant donné l’ensemble des nombres naturelsN, la relationR : N → 2N

associant chaque élément dex à l’ensemble des nombres naturels inférieurs ou égaux àxest

R(x) = {0, 1, . . . , x}.Nous pouvons de façon équivalente définir cette relation comme l’ensemble

R = {{0, 0}, {1, 0}, {1, 1}, {2, 0}, {2, 1}, {2, 2}, {3, 0}, . . .} ⊆ N× N.

⋄

Exemple A.5RelationR = { (a, b) | a est l’auteur du livreb } ⊆ Auteurs× Livresassocie à un auteur les livres qu’il a écrit. ⋄

Notez qu’une fonction est une forme restreinte de relation où l’ensembleR(x) est unsingleton (i.e., contient un seul élément) ou l’ensemble vide (si la fonction partiellefn’est pas définie pourx).

Exemple A.6La fonction signe: Z → S précédemment définie peut également êtredécrit comme signe⊆ Z× S énumérant toutes les couples(x, s), i.e.,

sign= {(0, 0), (1,+), (−1,−), (2,+), (−2,−), . . .}.⋄

Notez que lorsquef est une fonction, il n’existent pas deux couples(x, y), (x, y′) ∈ favecy 6= y′.

76

A.2 Relations binaries

Une classe intéressante des relations sont les relations binaires.

Définition A.4 Une relationR ⊆ X ×X dont le codomaine coïncide avec son domaineX, est appelée unerelation binaire surX. N

Exemple A.7La relation binaireR′ = { (x, x2) | x ∈ R } ⊆ R×R associe à un nombreréelx ∈ R son carré. La relation binaireR′′ = { (x, 2x) | x ∈ R } ⊆ R × R associe àun nombre réelx ∈ R son double. ⋄

Nous pouvons aussi définir l’inverse d’une relation.

Définition A.5 Etant donné une relationR ⊆ X × Y sarelation inverseest la relation

R−1 = { (y, x) | (x, y) ∈ R } ⊆ Y ×X.

N

Exemple A.8L’inverse de la relationR définie dans l’exemple A.5 est

R−1 = { (b, a) | le livre b est écrit par l’auteura } ⊆ Livres× Auteurs.

L’inverse de la relationR′ dans l’exemple A.7 est

(R′)−1 = { (x, y) | x ∈ R≥0, y = ±√x } ⊆ R× R,

qui associe un nombre réel non négatif2 à sa racine carrée (positif ou négatif).

L’inverse de la relationR′′ définie dans Exemple A.7 est

(R′′)−1 = { (x, x/2) | x ∈ R } ⊆ R× R,

qui associe un nombre réel à sa moitié. ⋄

Nous concluons en définissant une famille spéciale de relations (ce sont en réalité desfonctions totales) appeléeisomorphisme.

Définition A.6 Une relationR ⊆ X × Y est unisomorphismesi les deux conditionssuivantes sont vérifiées :

(a) pour toutx ∈ X il existe et est unique élémenty ∈ Y tel que(x, y) ∈ R ;

(b) pour touty ∈ Y il existe et est unique élémentx ∈ X tel que(y, x) ∈ R−1.

Équivalemment, nous disons que la relationR ⊆ X × Y est unisomorphismesi les deuxrelationsR etR−1 sont fonctions totales. N

2. Ici R≥0 désigne l’ensemble des nombres réels non négatifs.

77

Exemple A.9Considérons les relations définies dans l’exemple A.8.

La relationR n’est pas un isomorphisme. En fait, un livre peut avoir plus d’un auteur etun auteur peut avoir écrit plus d’un livre.

La relationR′ n’est pas un isomorphisme. En fait, alors que relationR′(x) = x2 est unefonction totale dansR, la relation inverse(R′)−1(x) =

√x n’est pas une fonction totale.

Tout d’abord, la racine carrée n’est pas définie pour les nombres négatifs (sauf si l’onconsidère le domaine des nombres complexes). Deuxièmement, pour tous réels positifsxla racine carrée peut être à la fois un réel positif ou négatif, par exemple,

√4 = {−2, 2}.

La relationR′′ est un isomorphisme. En fait, pour chaque nombre réelx, on peut calculerson doubleR′′(x) = 2x et, à l’inverse, pour chaque nombre réel x on peut calculer samoitié (R′′)−1(x) = x/2. ⋄

A.3 Relations d’équivalence

Définition A.7 Une relation binaireR ⊆ X ×X est appelée unerelation d’équivalence(ou équivalencetout court) si satisfait les trois propriétés suivantes :

– transitif : (x, x′) ∈ R, (x′, x′′) ∈ R =⇒ (x, x′′) ∈ R;– symétrique: (x, x′) ∈ R =⇒ (x′, x) ∈ R;– réflexive: pour tousx ∈ X : (x, x) ∈ R.

N

Exemple A.10Considérons la relation∼ dans l’ensemble des nombres réels définis commex ∼ y si ⌊x⌋ = ⌊y⌋, i.e.,x ety ont la même partie entière3. A titre d’exemple,1 ∼

√2 ∼

1.999. Nous pouvons facilement vérifier que cette relation est transitive, symétrique etréflexive, il est donc une équivalence. ⋄

Etant donnée une relation d’équivalenceR sur l’ensembleX, nous pouvons définir lesclasses d’équivalencecorrespondant.

Définition A.8 SoitR ⊆ X × X une relation d’équivalence et considéronsx ∈ X. Laclasse d’équivalence dex par rapport à la relationR est l’ensemble[x] := {x′ ∈ X |(x, x′) ∈ R } de tous ces éléments deX qui sont en relation avecx. N

Exemple A.11Etant donné la relation∼ comme dans l’exemple A.10, la classe d’équiv-alence d’un nombre réel arbitrairex est l’ensemble[x] = [ ⌊x⌋, ⌊x⌋ + 1 ), i.e., l’intervalleréel entre la partie entière dex (inclus) et le nombre entier suivant (exclu). Par exemple,[√2] = [1, 2). ⋄

3. 3 La partie entière d’un nombre réelx est le plus grand entier inférieur ou égal àx.

78

Un résultat important est présenté dans la prochaine proposition, dont la preuve est omise.

Proposition A.1 Etant donné une relation d’équivalenceR ⊆ X × X, l’ensembleΠR

de ses classes d’équivalence4 par rapport àR induit une partition deX. �

Exemple A.12Dans l’exemple précédent, les classes d’équivalence pour la relation∼sont tous les intervalles de la formeπk = [k, k + 1) aveck ∈ Z et l’ensembleΠ∼ :={ πk | k ∈ Z} est une partition deR. ⋄

Enfin, nous notons qu’une relation d’équivalenceR est parfaitement caractérisée parl’ensemble de ses classes d’équivalenceΠR. En fait, si une partitionΠR = {π1, π2, . . . , πk}est donnée, on peut définir la relation correspondante commesuit : R = { (x, x′) |(il existeπ ∈ ΠR) x, x

′ ∈ π }.

4. L’ensemble des classes d’équivalence par rapport à la relationR est également notée parX/R et estappeléquotient deX parR.

79

Annexe B

Eléments de la théorie de graphes

De nombreux modèles d’évènements comme les automates, les chaines de Markov, lesréseaux de Petri sont basés sur des graphes. Une introduction à ce domaine peut êtretrouvée dans l’excellent livre [2].

B.1 Définitions de base

Définition B.1 Un grapheest une coupleG = (V,A), oùV est un ensemble denœuds(nommés aussisommets), etA ⊆ V ×V est un ensemble d’arêtes(nomeés aussiarcs). N

Chaque arête relie 2 nœuds et 2 nœuds connectés par une arête sont appelés adjacents. Lafigure B.1(a) montre le grapheG = (V,A) avec un ensemble de nœudsV = {v1, v2, v3}et un ensemble d’arêtesA = {a1, a2}. Les nœuds sont représentés par des points ou descercles et les arêtes par des traits. On peut également définir une arête par une couplenon ordonnée de nœuds : par exemple, les 2 arêtes du graphe de la figure B.1 (a) sonta1 = {v1, v2} eta2 = {v2, v3}.

Définition B.2 Un graphe orientéest un graphe dont les arêtes sont orientées d’un nœud

v1

a1

v2

v3

a2

v1

a1

v2

v3

a2

v1

a1

v2

v3

a2

a3

(a) (b) (c)

a4

FIGURE B.1 – Trois graphes.

80

queueà un nœudtête. L’orientation est représenté par une flèche qui va de laqueueà latête. N

Dans un graphe orienté on note une arrête de queuev et de têtev′ par la coupleordonnée(v, v′). Dans un graphe orienté on peut avoir des boucles, c’est-à-dire des arêtes avec lemême nœud comme tête et queue.

Dans la figure B.1, le graphe (a) est non orienté tandis que les graphes (b) et (c) sont desgraphes orientés. Dans le graphe de la figure B.1(b) on peut écrirea1 = (v1, v2) oùv1 estla queue etv2 la tête de l’arêtea1. Dans le graphe de la figure B.1(c) l’arêtea4 = (v3, v3)est une boucle sur le nœudv3.

Définition B.3 Un grapheG = (V,A) est dit biparti s’il existe une partition de sonensemble de nœuds en 2 sous-ensembles disjointsV = V1 ∪ V2, de sorte queA ⊆(V1 × V2) ∪ (V2 × V1), c.à.d., chaque arête chaque arête ait une extrémité dansV1 l’autredansV2. N

La définition de graphebiparti peut aussi naturellement s’étendre àk partitions : ungraphe estk-parti siV = V1 ∪ · · · ∪ Vk (avecVi ∩ Vj = ∅ pour i 6= j) et si chaque arêterejoint des nœuds appartenant à deux différentes partitions, c’est-à-dire,A∩(Vi×Vi) = ∅pour touti.

Dans la figure B.1, les graphes (a) et (b) sont bipartis si on considèreV1 = {v1, v3} etV2 = {v2} et ils peuvent mêmes être tripartis si on considère chaque nœud dans unepartition contenant lui-même. Le graphe dans la figure B.1(c), au contraire, ne peut pasêtrek-parti pour aucun valeur dek à cause de la présence de la bouclea4.

B.2 Chemins et cycles

Définition B.4 Un chemindans un graphe, est une séquence composée de façon alternéepar des nœudsvji appartenant àV et une arêteaji appartenant àA, avecaji = {vji−1

, vji}i.e chaque nœudvji−1

est adjacent par une arêteaji au nœuds suivantvji. On peut aussidire que ce chemin mène devj0 versvjk a unelongueurk (la longueur du chemin est égaleau nombre d’arêtes qui le compose).

Un cheminγ = vj0aj1vj1aj2 · · · ajkvjk estorientési aji = (vji−1, vji), soit chaque arête

est orientée du nœudsaji vers le nœudvji−1to nodevji. N

Par exemple, soitγ = v1a1v2a2v3. Dans le graphe de la figure B.1(a), γ gamma est unchemin. Dans le graphe de la figure B.1(b), γ est un chemin orienté. Dans le graphe de lafigure B.1(c), γ est un chemin mail n’est pas un chemin orienté.

Définition B.5 Un cycleest un cheminγ = vj0aj1vj1aj2 · · · ajkvjk où vj0 = vjk , i.e., lenœud initial correspond aussi au nœud final. Un cycle est ditorientési chaque arcaji est

81

orienté du nœudvji−1vers le nœudvji. Un cycle est ditélémentaires’il ne passe pas deux

fois par le même nœud, i.e.,vjq 6= vjp pourq, p = 0, 1, . . . , k − 1. N

Dans le graphe en B.1(a) et B.1(b) il n’y a pas de cycles. Dans le graphe B.1(c), lescheminsv1a3v3a2v2a1v1 et v3a4v3 sont tous les deux des cycles élémentaires orientésalors que le cheminv3a3v1a1v2a2v3 n’est pas un chemin élémentaire orienté. Enfin, dansle graphe B.1(c), les cheminsv3a2v2a1v1a3v3a4v3 et v3a4v3a4v3 sont deux exemples decycles orientés mais non-élémentaires.

Définition B.6 Un graphe est ditconnexesi pour chaque nœudsv, v appartenant àV ilexiste un chemin dev versv′. Un graphe orienté est ditfortement connexesi pour toutcouple ordonnée de nœudsv, v′ appartenant àV il existe un chemin orienté dev versv′.N

Les trois graphes de la figure B.1 sont connexes. Le graphe orienté dans la figure B.1(b)n’est pas fortement connexe : par exemple, il n’y a pas de chemin orienté dev2 versv1(notez pourtant qu’il existe un chemin orienté dev1 vers v2). Le graphe orienté de lafigure B.1(c) est fortement connexe.

Le graph de la figure B.2(a) n’est pas connexe : par exemple, il n’y a pas de chemin allantdev1 versv4. Les graphes B.2(b) et B.2(c) sont connexes mais pas fortement connexes :dans les deux cas, il n’y a pas de chemin orienté dev1 versv4. Le graph de la figure B.2(d)est fortement connexe.

B.3 Sous-graphes et composantes

Définition B.7 Une forêt est un graphe qui ne contient pas de cycles. Unarbre est ungraphe connecté qui ne contient pas de cycles. Un graphe orienté est ditacycliques’il necontient pas de cycles orientés. N

Les graphes des figure B.1(a) et figure B.1(b) sont des arbres. Le graphe de la figure B.2(a)est une forêt composée de deux arbres. Le graphe de la figure B.2(b) est un arbre. Legraphe de la figure B.2(c) est un graphe acyclique car il ne contient pas de cycles ori-entés, mais ce n’est pas un arbre car il contient des cycles non orientés. Le graphe de lafigure B.2(d) est un graphe cyclique.

Définition B.8 Un grapheG ′ = (V ′, A′) est appelé unsous-graphedeG = (V,A) si V ′

est inclus ou égal àV etA′ inclus ou égal àA∩ (V ′ × V ′). Dans ce cas, on écritG′ ⊆ G.

En particulier, siA′ = A ∩ (V ′ × V ′), i.e.,G ′ contient tous les arcs deG connectant lesnœuds dansV ′, on dit queG ′ est unsous-graphe induit parV ′. N

Dans la figure B.2, le graphe (a) est un sous-graphe de (b), qui est lui-même un sous-graphe de (c).

82

v1 v2

(a) (b) (c)

v3 v4

v1 v2

v3

v1 v2

v3

(d)

v1 v2

v3 v4 v4 v4

FIGURE B.2 – Une forêt (a), un arbre (b), un graphe acyclique (c), un graphe cyclique(d).

v1 v2

(a) (b) (c)

v3 v4

v1 v2

v3

v2 v1

v3

FIGURE B.3 – Un grapheG (a), son sous-grapheG ′ induit parV ′ = {v1, v2, v3} (b), ungrapheG ′′ isomorphe àG ′ (c).

Dans la figure B.3, le graphe (b) est un sous-graphe de (a) induit par l’ensemble de nœudsV ′ = {v1, v2, v3}.

Soit un grapheG = (V,A), donné, son sous-graphe induit par un ensemble des nœudsV ′

inclut ou égal àV peut être obtenu en retirant àG tous les nœuds dansV \ V ′ et tous lesarcs associés.

Enfin, notez que le graphe de la figure B.3(c) estisomorpheau graphe de la figure B.3(b),dans le sens où l’un est obtenu à partir de l’autre, simplement en changeant le nom desnœuds.

Définition B.9 Une composantedu grapheG = (V,A) est un sous-grapheG ′ ⊆ G quiest connexe et maximal, i.e., il n’existe aucun autre sous-grapheG ′′ connexe tel queG ′ (

G ′′ ⊆ G. N

Si un grapheG est connexe, son unique composante est le graphe lui-même.

La forêt non connectée dans la figure B.2(a) a deux composantes. La première est l’arbreG1 = (V1, A1), avecV1 = {v1, v2} et A1 = {(v1, v2)}. La deuxième est l’arbreG2 =(V2, A2), avecV2 = {V3, V4} etA2 = {(V3, V4)}. Notez que les composantes d’une forêtsont toujours des arbres.

83

v1 v3

v2 v4

v5 v7

v6

G1

G2 G4

G3

FIGURE B.4 – Un graphe orienté et ses composantes fortement connexes.

Définition B.10 Unecomposante fortement connexed’un graphe orientéG = (V,A) estun sous-grapheG ′ ⊆ G qui est fortement connexe et maximal, i.e., il n’existe aucun autresous-grapheG ′′ fortement connexe tel queG ′ ( G ′′ ⊆ G. N

Si un grapheG est fortement connexe, son unique composante fortement connexe est legraphe lui-même. Le graphe de la figure B.4 a 4 composantes fortement connexesG1, G2,G3 andG4, comme indiqué sur la figure.

Les composantes fortement connexes d’un graphe orienté induisent une partition de sesnœuds.

Proposition B.1 Soit un graphe orientéG = (V,A) avecr composantes fortement con-nexes, l’ensemble des nœudsV peut être partitionné enr sous-ensemblesV = V1 ∪ V2 ∪· · · ∪ Vr tel que chaque sous-graphe induit par le sous-ensembleVi est une composantefortement connexe deG.

Proof. Considérons une relation binaireR ⊆ V × V entre les nœuds du graphe définicomme suit :vRv′ ’il existe un chemin orienté du nœudv versv′ et un chemin orienté dunœudv versv′. Il est facile de montrer que cette relation est une relationd’équivalence(voir section A.3), et chaque classe d’équivalence corresponde exactement à l’ensemblede nœuds d’une composante fortement connexe. Ces classes représentent donc une parti-tion deV . �

Par exemple, les deux composantes fortement connexes de la forêt dans la figure B.2(a) sont deux arbres correspondants à la partition deV = V1 ∪ V2, avecV1 = {v1, v2}et V2 = {V3, V4}. Les 4 composantes fortement connexes du graphe de la figure B.4correspondent à la partition deV = V1 ∪ V2 ∪ V3 ∪ V4, avecV1 = {v1} et V2 = {v2},V3 = {v3, v4} etV4 = {v5, v6, v7}.

Une fois que les composantes fortement connexes ont été déterminées, il est possible deles classifier en deux catégories.

84

Définition B.11 Une composante fortement connexesG ′ = (V ′, A′) d’un graphe orientéG = (V,A) est nommé :– ergodiquesA ∩ (V ′ × (V \ V ′)) = ∅, i.e., il n’y a pas d’arc dansG qui va d’un nœud

deV ′ vers un nœud qui n’est pas dansV ′ ;– transitoiresi A ∩ (V ′ × (V \ V ′)) 6= ∅, i.e., il y a au moins un arc dansG qui va d’un

nœud deV ′ vers un nœud qui n’est pas dansV ′. N

Selon cette définition, les composantes fortement connexesG1 etG3 du graphe de la fig-ure B.4 sont transitoires. En effet, la composanteG1 a deux arcs de sortieU– un orientévers la composanteG2 et l’autre orienté vers la composanteG3 — alors que la composanteG3 a un arc de sortie orienté vers la composanteG4. Les composantesG2 et G4 sont er-godiques. Notons qu’un graphe orienté a au moins une composante ergodique, alors qu’ilpeut avoir 0 composantes transitoire ou plus. Un graphe orienté fortement connexeG a ununique composante ergodique qui est le graphe lui-même et ilest aussi ditirréductible.

Le principale intérêt de cette classification de composantes en ergodique et transitoirevient de l’observation suivante. Supposons que l’on parcourt un graphe orienté se dé-plaçant d’état à état en suivant un chemin orienté. De chaquenœud d’une composantefortement connexe il y’a toujours un chemin orienté qui mèneà n’importe quel nœud dela même composante. Bien que, dès lors qu’il y’a une composante transitoire franchir unede ses arrêtes de sortie ne permet pas de revenir dans la composante. Inversement unecomposante ergodique a une double propriété : une fois atteinte il n’y a pas de cheminpour la quitter.

85

Annexe C

Bibliographie

[1] C.G. Cassandras, S. Lafortune,Introduction to discrete event systems, Springer,2008.

[2] R. Diestel,Graph theory(2nd edition), Springer–Verlag, 1999.

[3] J.E. Hopcroft, J.D. Ullman,Introduction to automata theory, languages, and com-putation, Addison-Wesley, 1979.

[4] H.R. Lewis, C.H. Papadimitriou,Elements of the theory of computation, Prentice-Hall, 1981.

[5] P.J. Ramadge, W.M. Wonham, "The control of discrete event systems", Proceedingsof the IEEE, vol. 77, n. 1, pp. 81–98, 1Jnuary 989.

[6] M. Sampath, R. Sengupta, S. Lafortune, K. Sinnamohideen, D. Teneketzis, “Diag-nosability of Discrete-Event Systems,”IEEE Transaction on Automatic Control, vol.40, n. 9, pp. 1555–1575, September 1995.

[7] C. Seatzu, M. Silva, J.H. van Schuppen (Eds),Control of Discrete-Event Systems.Automata and Petri Net Perspectives, Lecture Notes in Control and Information Sci-ence, Vol. 433, Springer, 2012.

86