Le langage des mots formés de fois la lettre a suivies de fois la lettre b est l'exemple
canonique de ce qu'un automate fini ne sait pas faire. Le vérifier pour un borné est
possible, et coûte cher ; le vérifier sans borne est impossible.
L'automate pour n borné
Il compte les a en montant, puis les b en descendant. Un état par valeur du compteur, dans
chaque sens.
Objectif
Mesurer le coût pour deux bornes, puis répondre à la question sans borne.
Pourquoi la réponse est zéro
Un automate fini a un nombre d'états fixé à la construction. Une fois ce nombre dépassé, le jeton repasse forcément par un état déjà visité, et la machine a oublié la différence entre les deux passages. C'est le raisonnement du chapitre, et il ne dépend d'aucune ingéniosité de construction : il vaut pour tous les automates finis à la fois.
Où cela se rencontre
Un parenthésage équilibré, des blocs imbriqués, du JSON, du XML, du HTML. Aucune expression régulière ne validera jamais complètement l'un de ces formats, et toute tentative sérieuse finit par écrire un analyseur.