TD8 - Automates et Langages - RICM

Rappel: pour minimiser un automate déterministe il faut

Méthode pratique de construction de la relation d'équivalence:

  1. On construit un tableau de taille N x N (N est le nombre d'états de notre automate). Chaque case dans ce tableau correspond à un couple d' états (p,q). Pour ne pas avoir deux fois le même couple ((p,q) et (q,p)) ni les couples inutiles (p,p), on garde seulement la partie triangulaire supérieure du tableau. (Notre but final est de cocher toute les cases (p,q) pour des états p et q non-quivalents)
  2. Au début on coche chaque case (p,q) correspondant à  un état final et à  un état non-final (c'est à dire p dans F et q dans Q-F ou à l'envers, p dans Q-F et q dans F).
  3. On balaie toutes les cases vides du tableau d'une manière quelconque en le modifiant de façon suivante : pour chaque case (p,q) et lettre a, on calcule delta(p,a)=p' et delta(q,a)=q'. On coche (p,q) si et seulement si la case (p',q') est déjà cochée.
  4. On répète le balayage jusqu'au moment quand le tableau ne se modifie plus.
  5. La relation d'équivalence se cache dans le tableau final : deux états p et q sont équivalents si et seulement si la case (p,q) n'est pas cochée.

Exercice 1. On minimise.

1. Calculer l'automate minimal équivalent à (=acceptant le même langage que) l'automate suivant: Q={a,b,c,d,e,f,g,h}, S={0,1}, q0=a, F=d, d est donné par la table:
 

 

a

b

c

d

e

f

g

h

0

b

a

d

d

d

g

f

g

1

a

c

b

a

f

e

g

d

2. Même question pour Q={a,b,c,d,e}, S={0,1}, q0=a, F={a,c}, d est donné par la table:
 

 

a

b

c

d

e

0

b

e

d

e

e

1

e

c

e

a

e

Pourquoi les états a et b ne sont pas équivalents? a et e?

Trouver les calculs de l'automates original et minimal sur 010111 et les comparer.

Exercice 2. On déterminise et minimise.

Calculer l'automate minimal équivalent à (=acceptant le même langage que) l'automate suivant:

Q={0,1,2,3,4,5}, S={a,b}, q0=0, F=4, d est donné par la table:
 

 

0

1

2

3

4

5

a

12345

23

014

0

1

2

b

 

4

123

125

 

235

Indication: n'oubliez pas de déterminiser d'abord

Quel est le langage accepté?

 

Retour