Minimisation d'un automate
Rendre un automate déterministe complet le plus petit possible : états inaccessibles, états équivalents, mot séparateur, raffinement de partition de Moore, automate quotient et unicité de l'automate minimal.
- 25 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
État inaccessible : de quoi s'agit-il ?
Voir la réponse
État qu'aucun mot ne permet d'atteindre depuis l'état initial.
On le supprime d'abord : il ne change pas le langage reconnu. Un état autre que l'initial qui n'a que des flèches sortantes est inaccessible, quel que soit leur nombre.
Cet automate a 6 états, 1 initial, 5 et 6 acceptants. La partition de départ est {1, 2, 3, 4} et {5, 6}. Quelle est la partition après le premier tour ?
```text
a b
→ 1 2 3
2 4 5
3 4 1
4 2 6
*5 2 1
*6 4 3`- {1, 3}, {2, 4}, {5, 6}
- {1, 2, 3, 4}, {5, 6}
- {1, 3, 5, 6}, {2, 4}
- {1}, {2}, {3}, {4}, {5, 6}
Voir la réponse
{1, 3}, {2, 4}, {5, 6}
On range chaque état selon la classe de ses successeurs par a et par b. 1 et 3 vont dans {1,2,3,4} par a comme par b ; 2 et 4 vont par b dans {5,6}, donc se séparent de 1 et 3. 5 et 6 restent ensemble : leurs successeurs sont tous dans la première classe.
L'algorithme de Moore part de la partition … / non acceptants et s'arrête quand un tour ne … plus la partition.
Voir la réponse
L'algorithme de Moore part de la partition acceptants / non acceptants et s'arrête quand un tour ne change plus la partition.
Comme chaque tour ne peut que découper des classes, et qu'il n'y a qu'un nombre fini d'états, l'algorithme s'arrête toujours.
États équivalents : de quoi s'agit-il ?
Voir la réponse
Deux états tels que, pour tout mot, lu depuis l'un et depuis l'autre, on aboutit à deux états acceptants ou à deux états non acceptants.
Deux états équivalents jouent le même rôle et peuvent être fusionnés sans changer le langage. Ils sont inséparables, quel que soit le mot lu.