Voir la source de Automate à file



En [[informatique théorique]], et notamment en [[théorie des automates]], un '''automate à file''' (en anglais {{Citation étrangère|langue=en|queue automaton}}) est un [[automate fini]] doté d’une mémoire auxiliaire infinie organisée en [[file (structure de données)|file]]. C’est un modèle de calcul qui est équivalent aux [[machine de Turing|machines de Turing]], et accepte donc la même classe de [[langage formel|langages]]. En cela, ce modèle diffère des [[automate à pile|automates à pile]] qui ne reconnaissent que les [[langage algébrique|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'' <math>M = (Q, \Sigma, \Gamma, \$, s, \delta)</math> est composé des données suivantes :
* <math>\,Q</math> est un [[ensemble fini]] d{{'}}''états'' ;
* <math>\Sigma</math> est ''l’alphabet d’entrée'' ;
* <math>\,\Gamma</math> est l’''alphabet de pile'', avec <math>\,\Sigma \subseteq \Gamma</math>; l’alphabet est fini ;
* <math>\,\$ \in \Gamma \setminus \Sigma</math> est un symbole spécial appelé ''symbole de file initial'' ;
* <math>\,s \in Q</math>  est l’ ''état initial'' ;
* <math>\,\delta : Q \times \Gamma \rightarrow Q \times \Gamma^*</math> la ''fonction de transition'' (où <math>\,\Gamma^*</math> est l’ensemble des mots finis sur <math>\,\Gamma</math>, c'est-à-dire l’[[étoile de Kleene]] de <math>\,\Gamma</math>).

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

:<math>\,(p,A\alpha) \rightarrow_M (q,\alpha\gamma)</math>

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

La machine ''accepte'' le mot d’entré  <math>\,x\in\Sigma^*</math> si, après un nombre fini de transitions, la machine atteint une configuration où la file est vide, soit si<ref name= "Kozen">
{{Ouvrage
 |prénom1=Dexter C.
 |nom1=Kozen
 |titre=Automata and Computability
 |éditeur=Springer-Verlag
 |lieu=New York
 |série=Undergraduate Texts in Computer Science
 |année=1997
 |année première édition=1951
 |pages totales=400
 |passage=368–370
 |isbn=978-0-387-94907-9
 |isbn10=0-387-94907-0
 |présentation en ligne=https://books.google.com/books?id=8lKyxS8_CNoC&printsec=frontcover
}}.
</ref>
: <math>\,(s,x\$)\rightarrow_M^*(q,\epsilon).</math>

== Exemple ==
L’ensemble des carrés <math>xx</math> des mots sur un alphabet donné est accepté par un automate à file<ref name="VZ">{{Article|prénom1=Bernard|nom1=Vauquelin|prénom2=Paul|nom2=Franchi-Zannettacci|titre=Automates a file|périodique=Theoretical Computer Science|volume=11|numéro=2|date=1980|doi=10.1016/0304-3975(80)90047-X|lire en ligne=http://www.sciencedirect.com/science/article/pii/030439758090047X|consulté le=2017-08-10|pages=221–225}}</ref>{{,}}<ref>La définition donnée dans {{harvsp|Vauquelin|Franchi-Zannettacci|(1980)}} est différente.</ref>.

== [[Turing-complet|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<ref name= "Kozen"/>{{,}}<ref>
{{Lien web
 |langue       = en
 |format       = pdf
 |url          = http://www.cs.uiowa.edu/~rus/Courses/Theory/Notes/turing3.pdf
 |titre        = Variants of Turing Machines
 |consulté le = 2007-11-06
 |nom          = Rus
 |prénom      = Teodor
 |série       = Lecture Notes Covering Theory of Computation
 |éditeur     = University of Iowa, Iowa City, IA, 52242-1419
 |archive-url  = https://web.archive.org/web/20080921051611/http://www.cs.uiowa.edu/~rus/Courses/Theory/Notes/turing3.pdf
 |archive-date = 21 septembre 2008
 |brisé le    = 23 juillet 2018
}}.</ref>.

== Applications ==
Les automates à file fournissent un modèle simple sur lequel peut être fondée l’[[architecture matérielle]] d’un ordinateur<ref>
 {{Article |nom=Feller |prénom=M. |auteur2=Miloš D. Ercegovac  |année=1981 |titre=Queue machines: An organization for parallel computation |journal=Lecture Notes in Computer Science |volume= 111|numéro= |pages= 37|id= |url=http://www.springerlink.com/content/m8w6x22741k5u093/ |consulté le=2007-11-06 |doi=10.1007/BFb0105108}}
</ref>{{,}}<ref>
{{Article |nom=Schmit |prénom=Herman |lien auteur= |auteur2=Benjamin Levine |auteur3=Benjamin Ylvisaker  |année= 2002|titre=Queue Machines: Hardware Compilation in Hardware |journal=10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM'02) |volume= |numéro= |pages=152 |id= |url=http://doi.ieeecomputersociety.org/10.1109/FPGA.2002.1106670 |consulté le=2007-11-06|doi=10.1109/FPGA.2002.1106670}}</ref>, certains [[Langage de programmation|langages de programmation]], ou des [[algorithme]]s<ref>
{{Lien web |url=http://algo.inria.fr/seminars/sem99-00/moore1.html 
 |titre=Queues, Stacks, and Transcendentality at the Transition to Chaos 
 |consulté le=2007-11-06 
 |nom=Moore |prénom=Christopher |date=1999-09-20   
 |série=Algorithms Project's Seminar |éditeur=INRIA}}.
</ref>{{,}}<ref>
{{Lien web |url=http://www.latrobe.edu.au/philosophy/phimvt/misc/queue.html |titre=A queue machine for evaluating expressions |consulté le=2007-11-06 |nom=von Thum |prénom=Manfred |année=2007 |éditeur=LaTrobe University |archive-url=https://web.archive.org/web/20070807192327/http://www.latrobe.edu.au/philosophy/phimvt/misc/queue.html |archive-date=7 août 2007 |brisé le=23 juillet 2018 }}.</ref>.

== Articles liés ==
* [[Calculabilité]]
* {{Lien|trad=Turing machine equivalents|fr=Modèle équivalent aux machines de Turing}}
* [[Automate fini déterministe]]
* [[Automate à pile]]
* [[Système de tague]]
* [[Système de Post]]

== Notes et références ==
{{Traduction/Référence|en|Queue automaton|792866187|type=note}}
{{Références}}

{{DEFAULTSORT:Queue Machine}}
[[Catégorie:Théorie des automates]]
[[Catégorie:Modèle de calcul]]

{{Portail|informatique théorique}}