Un automate fini (finite state machine) est une construction abstraite susceptible d'être dans un nombre fini d'états ; un seul état à la fois. Le passage d'un état à un autre est dirigé par un événement ou une condition ; ce passage est appelé "transition".
Un automate à pile (pushdown automaton) ressemble à l'automate fini mais il possède une mémoire infinie organisée en pile (premier entré, dernier sorti). Lors d'une transition, l'état courant peut être détruit, remplacé par un nouveau ou conservé mais placé sous le prochain état qui devient l'état courant.
D'après l'exemple de Wikipédia : "Un portillon, utilisé dans certains métros [...] est une barrière avec trois bras rotatifs à hauteur de la taille. Au début, les bras sont verrouillés et bloquent l'entrée, et empêchent les usagers de passer. L'introduction d'une pièce de monnaie [...]] débloque les bras et permet le passage d'un et un seul usager à la fois. Une fois l'usager entré, les bras sont à nouveaux bloqués jusqu'à ce qu'un nouveau jeton soit inséré."
État du portillon :
D'après l'exemple de Fernando Bevilacqua : Une fourmis cherche de la nourriture qu'elle veut ramener à son nid. Pendant qu'elle cherche de la nourriture, si le curseur s'approche d'elle, elle s'enfuie.
État de la fourmis :
Dans l'exemple précédent, la fourmis n'a pas peur du curseur lorsqu'elle revient vers sa maison parce qu'il est impossible de savoir si elle était en train de chercher de la nourriture ou de revenir vers la maison lorsqu'elle sort de l'état de fuite. En utilisant une pile, la machine ajoute de nouveaux états sur le dessus de la pile et réagit toujours en fonction de l'état en tête de pile à un moment donné.
État(s) de la fourmis :
Qu'arrive-t-il quand ce comportement est appliqué à un nid de fourmis en entier ?
Les fourmis font un point chaque fois qu'elle revienne au nid avec un morceau de nourriture.
Comme les fourmis ne communiquent pas entre elles, elles peuvent essayer de ramasser le même morceau de nourriture. Si une autre a ramassé le morceau qu'une fourmis voulait ramasser, cette dernière choisira celui qui est la plus proche d'elle et du nid.
Pour éviter que les fourmis se marchent les unes sur les autres, le concept de séparation utilisé dans le jeu de la « Semaine 5 - Nuée d'oiseaux » a été utilisé.