Construire un automate à la main devient vite pénible. Trois opérations permettent de l'assembler à partir d'automates plus simples, et chacune a un coût prévisible.
Les trois opérations
| Opération | Construction | Nombre d'états |
|---|---|---|
| Complément | échanger acceptants et non-acceptants | inchangé |
| Union | couples d'états, acceptant si l'un des deux l'est | produit |
| Intersection | couples d'états, acceptant si les deux le sont | produit |
Objectif
Chiffrer le coût de chaque assemblage.
La condition qu'on oublie
Le complément n'est correct que si l'automate est déterministe et complet. Sur un automate incomplet, une lecture bloquée n'est ni acceptée ni refusée : elle s'arrête, et échanger les états acceptants ne la fait pas basculer du bon côté. Complémenter sans compléter d'abord produit un automate qui refuse des mots que le complément devait accepter, et l'erreur est silencieuse.