Automate

Voici un petit (micro) jeu de robosomes :

Entrer ci-dessus le programme à appliquer aux robots (suite de lettres A, D ou G) :

Il est suffisamment petit pour qu'on puisse lister les états possibles de la grille, numérotés de 0 à 4 :

L'état 4 est l'état final. Jouer consiste à atteindre l'état final (celui où tous les robots sont sortis de la grille). Or on constate que :

• Depuis l'état 0,
  • A fait rester dans l'état 0,
  • D fait aller dans l'état 1,
  • G fait aller dans l'état 2.
  (dorénavant on ne dessinera plus les flèches étiquetées A puisqu'elles sont sur chaque sommet du graphe)
• Depuis l'état 1,
  • A fait rester dans l'état 1,
  • D fait aller dans l'état 3,
  • G fait revenir à l'état 0.
• Depuis l'état 2,
  • A fait rester dans l'état 2,
  • D fait revenir à l'état 0,
  • G fait aller dans l'état 3.
• Depuis l'état 3,
  • A fait aller dans l'état 4 (final),
  • D fait aller dans l'état 2,
  • G fait aller dans l'état 1.
• Depuis l'état 4, A, D et G font rester dans l'état 4 (état final).

Résoudre un robosomes, c'est trouver un chemin dans le graphe ci-dessus, allant de l'état initial 0 jusqu'à l'état final 4. Les lettres étiquetant les arcs parcourus, forment alors un mot gagnant (le programme). Comme l'automate a un nombre fini (quoique parfois très grand) d'états, le langage formé par les mots gagnants d'un robosomes est régulier.

L'ensemble des solutions d'un robosomes peut être décrit par une expression régulière (ou RegEx). Pour le robosomes ci-dessus, en posant B = DA*D et C = GA*G, une Regex décrivant les mots gagnants est ((B|C)(B|C))*(B|C)A.

Le fait qu'une solution d'un robosomes est un chemin allant de l'état initial à un état final, donne un algorithme pour un solveur de robosomes :

• Construire l'automate (graphe orienté dont les arcs sont étiquetés par A, D ou G).
• Partir, dans ce graphe, de l'état initial.
• Effectuer un parcours en largeur d'abord de ce graphe.
• S'arrêter dès qu'on est arrivé à un état final, ou que le parcours est terminé.

Alors, si le parcours est terminé sans qu'on soit arrivé à un état final, c'est que le robosomes en question n'a pas de solution. Sinon, la suite des lettres lues dans le parcours trouvé est une solution du robosomes.

Le fait qu'on ait effectué un parcours en largeur garantit que, non seulement on trouve une solution (s'il y en a une) mais en plus elle est la plus courte possible.