Université Bordeaux I
Licence Informatique TD OMI 2001
Feuille d'exercices 1
Corrigé de l'exercice 6
L
1
est reconnu par l'automate non déterministe suivant:
On le déterminise:
a
b
0
0,1
0
0,1
0,1
0,2
0,2
0,1,3
0
0,1,3
0,1,3
0,2,3
0,2,3
0,1,3
0,3
0,3
0,1,3
0,3
et après avoir renommé les états on obtient:
Remarque: on voit facilement qu'il n'est pas minimal: les trois états terminaux peuvent ``fusionner'' en un seul état.
L
2
est reconnu par l'automate non déterministe suivant:
On le déterminise:
a
b
0
0,1
0,2
0,1
0,1,3
0,2
0,2
0,1
0,2,4
0,1,3
0,1,3,5
0,2
0,2,4
0,1
0,2,4
0,1,3,5
0,1,3,5
0,2
et après avoir renommé les états on obtient:
L
3
est reconnu par l'automate non déterministe suivant:
On le déterminise:
a
b
0
0,1
0,2
0,1
0,1,3
0,1,2
0,2
0,1,2
0,2,4
0,1,3
0,1,3
0,1,2
0,1,2
0,1,2,3
0,1,2,4
0,1,2,3
0,1,2,3
0,1,2,4
0,1,2,4
0,1,2,3
0,1,2,4
et après avoir renommé les états on obtient:
Remarque: on voit facilement qu'il n'est pas minimal: les états {0,1,2,3} et {0,1,2,4} peuvent ``fusionner'' en un seul état.
This document was translated from L
A
T
E
X by
H
E
V
E
A
.