Automate à file

En informatique théorique, et notamment en théorie des automates, un automate à file (en anglais « queue automaton ») est un automate fini doté d’une mémoire auxiliaire infinie organisée en file. C’est un modèle de calcul qui est équivalent aux machines de Turing, et accepte donc la même classe de langages. En cela, ce modèle diffère des automates à pile qui ne reconnaissent que les langages algébriques. Autant les automates à pile opèrent en mode last in, first out (LIFO), un automate à file travaille en mode first in, first out (FIFO).

Description formelle

Un automate à file ${\displaystyle M=(Q,\Sigma ,\Gamma ,\$,s,\delta )}$ est composé des données suivantes :

• ${\displaystyle \,Q}$ est un ensemble fini d'états ;
• ${\displaystyle \Sigma }$ est l’alphabet d’entrée ;
• ${\displaystyle \,\Gamma }$ est l’alphabet de pile, avec ${\displaystyle \,\Sigma \subseteq \Gamma }$; l’alphabet est fini ;
• ${\displaystyle \,\$\in \Gamma \setminus \Sigma }$ est un symbole spécial appelé symbole de file initial ;
• ${\displaystyle \,s\in Q}$ est l’ état initial ;
• ${\displaystyle \,\delta :Q\times \Gamma \rightarrow Q\times \Gamma ^{*}}$ la fonction de transition (où ${\displaystyle \,\Gamma ^{*}}$ est l’ensemble des mots finis sur ${\displaystyle \,\Gamma }$, c'est-à-dire l’étoile de Kleene de ${\displaystyle \,\Gamma }$).

Une configuration de l’automate est un couple ${\displaystyle \,(q,\gamma )\in Q\times \Gamma ^{*}}$ composé de son état ${\displaystyle q}$ et du contenu ${\displaystyle \gamma }$ de la file. La configuration initiale avec un mot d’entrée donné ${\displaystyle \,x}$ est définie par ${\displaystyle \,(s,x\$)}$, et la relation de transition ${\displaystyle \rightarrow _{M}}$ d’une configuration à une autre est définie par:

${\displaystyle \,(p,A\alpha )\rightarrow _{M}(q,\alpha \gamma )}$

où ${\displaystyle A}$ est un symbole de l’alphabet de pile, ${\displaystyle \alpha \in \Gamma ^{*}}$, et ${\displaystyle (q,\gamma )=\delta (p,A)}$. Dans cette relation, la propriété « first-in-first-out » est visible par le fait que le symbole ${\displaystyle A}$ est retiré en tête, et le mot ${\displaystyle \alpha }$ est ajouté en queue..

La machine accepte le mot d’entré ${\displaystyle \,x\in \Sigma ^{*}}$ si, après un nombre fini de transitions, la machine atteint une configuration où la file est vide, soit si^[1]

${\displaystyle \,(s,x\$)\rightarrow _{M}^{*}(q,\epsilon ).}$

Exemple

L’ensemble des carrés ${\displaystyle xx}$ des mots sur un alphabet donné est accepté par un automate à file^[2],[3].

Complétude au sens de Turing

On peut prouver que les automates à file sont équivalents aux machines de Turing. Pour simuler une machine de Turing par un automate à file, on construit un automate qui conserve à tout moment dans sa file le contenu de la bande de la machine de Turing, avec deux marqueurs particuliers, l’un pour la position de la tête de lecture-écriture de la machine, l’autre pour la fin de la bande. Les transitions de l’automate à file simulent celles de la machine de Turing en parcourant toute la file, supprimant les symboles en tête de file et les rajoutant en fin de file, tout en réalisant, autour de la tête de lecture-écriture de la machine de Turing, une de ses transitions.

Réciproquement, on peut simuler un automate à file par une machine de Turing à deux bandes, l’une pour la donnée d’entrée, l’autre pour la file, avec les transitions correspondantes. Une preuve formelle est parfois un exercice d’un cours en informatique théorique^[1],[4].

Applications

Les automates à file fournissent un modèle simple sur lequel peut être fondée l’architecture matérielle d’un ordinateur^[5],[6], certains langages de programmation, ou des algorithmes^[7],[8].

Articles liés

• Calculabilité
• Modèle équivalent aux machines de Turing (en)
• Automate fini déterministe
• Automate à pile
• Système de tague
• Système de Post