Lire un automate

1. On déroule. ab : $0\to 1\to 2$, reconnu. abb : $0\to 1\to 2\to 0$, refusé. aba : $0\to 1\to 2\to 1$, refusé. bbab : $0\to 0\to 0\to 1\to 2$, reconnu. ba : $0\to 0\to 1$, refusé. $\epsilon$ : on reste en $0$, refusé.

2. Le langage est celui des mots se terminant par ab, soit $(a|b{)}^{\ast }ab$. La lecture des états le montre : $1$ signifie « la dernière lettre lue est un a », $2$ signifie « les deux dernières lettres lues sont ab », $0$ signifie « ni l'un ni l'autre ». Chacune des six transitions se relit dans ces termes, et l'invariant est conservé.

3. On obtient les mots contenant le facteur ab. La modification rend l'état $2$ absorbant : une fois le motif vu, on n'en sort plus.

Ce que l'exercice met en scène. Une case de la table sépare « se terminer par » de « contenir ». C'est la différence entre un état qui mémorise la fin du mot lu et un état qui mémorise un événement passé. Rien dans la notation ne signale cette différence : il faut la lire dans les transitions.

Les deux automates ont été exécutés sur les $2047$ mots de longueur au plus $10$ et comparés aux deux prédicats « se termine par ab » et « contient ab » : accord complet dans les deux cas.