Le complémentaire d'un automate incomplet

1. $L(A)=a^{\ast }{b}^{+}$ : une suite de a, puis au moins un b. Lire un a après un b bloque l'automate, et un mot sur lequel la lecture bloque n'est pas reconnu.

2. Avec $F=\{0\}$, l'automate de l'élève reconnaît $a^{\ast }$ — et rien d'autre, car il bloque toujours au même endroit. Or le vrai complémentaire contient $\epsilon$, a, ba, aba, bab… Le plus court témoin est ba : il n'est pas dans $L(A)$, donc il doit être dans le complémentaire ; l'automate de l'élève le refuse, car il bloque sur le a.

3. Il faut compléter d'abord. On ajoute un état puits $p$, non acceptant, absorbant, et l'on y envoie toutes les transitions manquantes :

$$\delta (1,a)=p,\delta (p,a)=\delta (p,b)=p.$$

L'automate a maintenant trois états. On échange ensuite : $F=\{0,p\}$. Le puits, devenu acceptant, est exactement ce qui recueille les mots sur lesquels la lecture bloquait.

Le piège nommé. Un automate incomplet refuse deux sortes de mots : ceux qui finissent hors de $F$, et ceux dont la lecture bloque. L'échange des états acceptants ne retourne que la première sorte. La règle du chapitre — « le complémentaire exige un automate déterministe et complet » — n'a pas d'autre contenu que celui-là.