Rappel: pour minimiser un automate déterministe il faut
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.
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é?