Exercice 3

Question 1

a

état initial	suite entrée	suite sortie
s1	c	z✅
s2	c	x✅
s3	c	y
s4	c	y
s5	c	y

état initial	suite entrée	suite sortie
s3	b	x✅
s4	b	z✅
s5	b	y✅
W = \{c,b\}
`UIO(S1) = c/z`
`UIO(S2) = c/x`
`UIO(S3) = b/x`
`UIO(S4) = b/y`
`UIO(S5) = a/y`

b

TS_{UIO}(\text{S2, by, 2}) = R/N a/x b/y, b/y, c/x

Question 2

a

5 propriétés majeures de l’automate :

Déterministe (=1 sortie par input) ? Oui
Minimal (= tous les états sont uniques) ? Non, S2 et S3 sont équivalentes (transitions sortantes similaires) ainsi que S4, S5, S6
Fortement connexe (à partir de n’importe quel état, je peux atteindre n’importe quel état) ? Oui
Pas d’état transients (normalement, on n’en aura jamais) ? Isok
Complets (je peux tirer tous les inputs de mon système pour chaque état) ? Bien sûr

Il faut minimiser l’automate. Attention, il faut toujours minimiser par paire, pour éviter du non déterministe.
exo3-2b

Là, il y a un cycle : DS : aaa

état initial	suite entrée	suite sortie
s1	aaa	yxxx
s2,3	aaa	xxxy
s4,5	aaa	xxyx
s6	aaa	xyxx
W = \{aaa\}

UIO(S1) = a/y
UIO(S2/S3) = a/x a/x a/x
UIO(S4/S5) = a/x a/x a/y
UIO(S6) = a/x a/y

b

Stratégie de notre choix = très souvent les UIO

Ici S2 équivaut à S2/S3

TS_{UIO}(\text{S1, ay, S2}) = R/N, a/y, a/x a/x a/x

3

Déterministe ? Non
Minimal ? Non : S3 et S4
Fortement connexe ? Non : S1 inaccessible
Complets ? Oui

On minimalise le système :
exo3-3a

Déterministe ? Oui
Minimal ? Non : S1 et S3/S4
Fortement connexe ? Non : S1 inaccessible

On minimalise encore
exo3-3a2

b

TS_{DS}(\text{S2, by, S2}) = R/N a/x, b/y, b/y

c

On travail toujours sur le dernier système, donc celui qu’on a dessiné. Pas celui de l’énoncé

Inconclusif : problème dans le préambule
+ On n’a pas le bon nombre de sorties

4

a

pas complet
pas minimale (1, 3 et 4) (2 et 5)
- On doit garder des paires et fusionner 3 créer du non déterministe, alors on le laisse et on fusionne 1 et 4.

état initial	suite entrée	suite sortie
s1,s4	aaa	xyx
s2,s5	aaa	yxx
s3	aaa	xxx
s6	aaa	xxy
W = \{aaa\} (merci le cycle)

UIO(S1/S4) = a/x a/y
UIO(S2/S5) = b/y ou a/y
UIO(S3) = a/x b/x
UIO(S6) = b/x

b

TS_{W}(\text{1, a/x, 2}).(\text{2, b/y, 3}) = R/N, ax, ay, bx, ax, by, ax bx

R/N, ax, ay, bx, ax, by, ax bx
---  --  --  --  --  --  -----
|    |   |   |   |   |   |> UIO(3)
|    |   |   |   |   |> b/y
|    |   |   |   |> Deuxième préambule
|    |   |   |> Postambule (court chemin pour revenir à l'état initial)
|    |   |> UIO(2)
|    |> a/x
|> Préambule

c

x y x x y x x \ra PASS

Mais si on a une autre écriture : R/N, ax, by, ax, bx, ax, by ax bx on a un INCONCLUSIVE.
Mais si on a une autre écriture : R/N, ax, ay, ax, ax, by, ax bx on a un PASS.

d

Ou alors au lieu du postambule, on met un R/N : R/N, ax, ay, R/N ax, by, ax bx ax on a un FAIL pour erreur mixte.

R/N, ax, ay, R/N ax, by, ax bx ax
---  --  --  ------  --  --------
|    |   |   |       |   |> UIO(3) + ax qui permet de rallonger
|    |   |   |       |> b/y
|    |   |   |> Deuxième préambule
|    |   |> UIO(2)
|    |> a/x
|> Préambule

Mais si on a une autre écriture : R/N, ax, by, R/N ax, by, ax bx ax on a un FAIL pour erreur mixte