Finite State Automaton Challenges

Finite State Automaton Challenges vous propose 80 casse-têtes à résoudre en concevant des automates finis. Les défis portent sur les chaînes de caractères, les nombres binaires et des situations du quotidien. Un tutoriel vous présente les concepts.

Concevoir des automates

Un automate fini se compose d'états et de règles de transition qui décrivent ses passages d'un état à l'autre. Vous vous en servez pour déterminer quelles chaînes en entrée sont acceptées ou rejetées. Par exemple, un automate peut reconnaître des adresses e-mail ou des numéros de téléphone valides. Parmi les défis, vous devrez créer des automates qui acceptent la chaîne « ab » ou l'un des caractères « a » et « b ».

Le jeu propose aussi des niveaux avec différents types d'états, au-delà des états de départ, d'acceptation et normaux traditionnels. Certaines énigmes font appel à des automates finis non déterministes : une entrée est acceptée si au moins un chemin possible dans l'automate aboutit à un état d'acceptation. L'automate peut ainsi faire des suppositions lorsqu'il traite une chaîne.