Aller au contenu

Automate à file

Un article de Wikipédia, l'encyclopédie libre.


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

[modifier | modifier le code]

Un automate à file est composé des données suivantes :

  • est un ensemble fini d'états ;
  • est l’alphabet d’entrée ;
  • est l’alphabet de pile, avec ; l’alphabet est fini ;
  • est un symbole spécial appelé symbole de file initial ;
  • est l’ état initial ;
  • la fonction de transition (où est l’ensemble des mots finis sur , c'est-à-dire l’étoile de Kleene de ).

Une configuration de l’automate est un couple composé de son état et du contenu de la file. La configuration initiale avec un mot d’entrée donné est définie par , et la relation de transition d’une configuration à une autre est définie par:

est un symbole de l’alphabet de pile, , et . Dans cette relation, la propriété « first-in-first-out » est visible par le fait que le symbole est retiré en tête, et le mot est ajouté en queue..

La machine accepte le mot d’entré si, après un nombre fini de transitions, la machine atteint une configuration où la file est vide, soit si[1]

L’ensemble des carrés des mots sur un alphabet donné est accepté par un automate à file[2],[3].

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

[modifier | modifier le code]

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

[modifier | modifier le code]

Notes et références

[modifier | modifier le code]
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Queue automaton » (voir la liste des auteurs).
  1. a et b Dexter C. Kozen, Automata and Computability, New York, Springer-Verlag, (1re éd. 1951), 400 p. (ISBN 978-0-387-94907-9, présentation en ligne), p. 368–370.
  2. Bernard Vauquelin et Paul Franchi-Zannettacci, « Automates a file », Theoretical Computer Science, vol. 11, no 2,‎ , p. 221–225 (DOI 10.1016/0304-3975(80)90047-X, lire en ligne, consulté le )
  3. La définition donnée dans Vauquelin et Franchi-Zannettacci (1980) est différente.
  4. (en) Teodor Rus, « Variants of Turing Machines » [archive du ] [PDF], Lecture Notes Covering Theory of Computation, University of Iowa, Iowa City, IA, 52242-1419 (consulté le ).
  5. M. Feller et Miloš D. Ercegovac, « Queue machines: An organization for parallel computation », Lecture Notes in Computer Science, vol. 111,‎ , p. 37 (DOI 10.1007/BFb0105108, lire en ligne, consulté le )
  6. Herman Schmit, Benjamin Levine et Benjamin Ylvisaker, « Queue Machines: Hardware Compilation in Hardware », 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'02),‎ , p. 152 (DOI 10.1109/FPGA.2002.1106670, lire en ligne, consulté le )
  7. Christopher Moore, « Queues, Stacks, and Transcendentality at the Transition to Chaos », Algorithms Project's Seminar, INRIA, (consulté le ).
  8. Manfred von Thum, « A queue machine for evaluating expressions » [archive du ], LaTrobe University, (consulté le ).