Automata sorgép

Az elméleti számítógép-tudomány , különösen automaták elmélete , egy sorban automatát (angolul „  farok automata  ” ) egy véges automata végtelen memória szervezett kisegítő fájlt . Ez egy számítási modell, amely egyenértékű a Turing-gépekkel , és ezért elfogadja ugyanazt a nyelvosztályt . Ebben a modell különbözik a lehúzható automatáktól, amelyek csak algebrai nyelveket ismernek fel . Amíg az akkumulátoros PLC-k utoljára, először ki (LIFO) módban működnek, egy sor PLC működik az első be, az első ki (FIFO) módban .

Hivatalos leírás

A sorautomatát a következő adatok alkotják: M=(Q,Σ,Γ,$,s,δ){\ displaystyle M = (Q, \ Sigma, \ Gamma, \ $, s, \ delta)}

• Q{\ displaystyle \, Q}véges állapothalmaz  ;
• Σ{\ displaystyle \ Sigma}a bemeneti ábécé  ;
• Γ{\ displaystyle \, \ Gamma}a verem ábécé , a ; az ábécé elkészült;Σ⊆Γ{\ displaystyle \, \ Sigma \ subseteq \ Gamma}
• $∈Γ∖Σ{\ displaystyle \, \ $ \ in \ Gamma \ setminus \ Sigma}egy speciális szimbólum, az úgynevezett kezdeti sor szimbólum  ;
• s∈Q{\ displaystyle \, s \ Q} a kezdeti állapot  ;
• δ:Q×Γ→Q×Γ∗{\ displaystyle \, \ delta: Q \ times \ Gamma \ rightarrow Q \ times \ Gamma ^ {*}}Az átmeneti függvény (ahol a készlet véges szavak feletti , azaz Kleene csillaga a ).Γ∗{\ displaystyle \, \ Gamma ^ {*}}Γ{\ displaystyle \, \ Gamma}Γ{\ displaystyle \, \ Gamma}

A PLC konfiguráció egy pár, amelyet az állapota és a sor tartalma alkot . A kezdeti konfigurációt egy adott beviteli szóval az , és az egyik konfigurációból a másikba való átmenet viszonyát a következő határozza meg: (q,γ)∈Q×Γ∗{\ displaystyle \, (q, \ gamma) \ Q \ alkalommal \ Gamma ^ {*}}q{\ displaystyle q}γ{\ displaystyle \ gamma}x{\ displaystyle \, x}(s,x$){\ displaystyle \, (s, x \ $)}→M{\ displaystyle \ rightarrow _ {M}}

(o,NÁL NÉLα)→M(q,αγ){\ displaystyle \, (p, A \ alpha) \ rightarrow _ {M} (q, \ alfa \ gamma)}

hol van egy szimbólum a verem ábécéjéből, és . Ebben a viszonylatban az "első az elsőben" tulajdonság látható azáltal, hogy a szimbólumot eltávolítják a fejétől, és a szót hozzáadják a farokhoz. NÁL NÉL{\ displaystyle A}α∈Γ∗{\ displaystyle \ alfa \ a \ Gamma ^ {*}}(q,γ)=δ(o,NÁL NÉL){\ displaystyle (q, \ gamma) = \ delta (p, A)}NÁL NÉL{\ displaystyle A}α{\ displaystyle \ alpha}

A gép akkor fogadja el a beviteli szót, ha véges számú átmenet után a gép eléri a konfigurációt, ahol a sor üres, vagy hax∈Σ∗{\ displaystyle \, x \ in \ Sigma ^ {*}}

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

Példa

Az adott ábécé szavainak négyzetkészletét egy fájlautomaták fogadják el. xx{\ displaystyle xx}

A teljesség Turing értelmében

Bizonyítható, hogy a fájlautomaták egyenértékűek a Turing-gépekkel. Ahhoz, hogy egy Turing-gépet egy sorautomata segítségével szimuláljunk, megépítünk egy olyan automatát, amely mindig a sorában tartja a Turing-gép szalagjának tartalmát, két külön jelölővel, az egyik a gép fejének helyzetére vonatkozik. a gép, a másik a szalag végére. Az automata és a sor közötti átmenetek szimulálják a Turing-gépét, azáltal, hogy áthaladnak a teljes soron, eltávolítják a szimbólumokat a sor elején és hozzáadják őket a sor végén, miközben végrehajtják, az olvasási-írási fej körül. Turing gép, egyik átmenete.

Ezzel ellentétben szimulálhatunk egy sorautomatát egy Turing-gép segítségével, két sávval, az egyik a bemeneti adatokhoz, a másik a sorhoz, a megfelelő átmenetekkel. A hivatalos igazolás néha egy elméleti informatikai tanfolyam gyakorlata.

Alkalmazások

A várakozó gépek egyszerű modellt nyújtanak, amelyre a számítógép hardverarchitektúrája , bizonyos programozási nyelvek vagy algoritmusok épülhetnek .

Kapcsolódó cikkek

• Számíthatóság
• Turing-ekkel egyenértékű modell  (in)
• Determinisztikus véges automata
• Elemmel működő automata
• Tag rendszer
• Post rendszer

Megjegyzések és hivatkozások

(en) Ez a cikk részben vagy egészben az angol Wikipedia "  Queue automaton  " című cikkéből származik ( lásd a szerzők felsorolását ) .

1. Dexter C. Kozen , Automata and Computability , New York, Springer-Verlag, 1997( 1 st  ed. 1951), 400  p. ( ISBN  978-0-387-94907-9 , online előadás ) , p.  368–370.
2. Bernard Vauquelin és Paul Franchi-Zannettacci , „  Automatizál egy fájlt  ”, Elméleti számítástechnika , vol.  11, n o  21980, P.  221-225 ( DOI  10.1016 / 0304-3975 (80) 90047-X , olvasható online , elérhető augusztus 10, 2017 )
3. A Vauquelin és Franchi-Zannettacci (1980) definíciója eltér.
4. (in) Teodor Rus , "  Turingi gépek változatai  " [ archívum 2008. szeptember 21] [PDF] , A számítási elméletet leíró előadási jegyzetek , University of Iowa, Iowa City, IA, 52242-1419 (hozzáférés : 2007. november 6. ) .
5. M. Feller és Miloš D. Ercegovac, „Vonalgépek  : párhuzamos számítások szervezete  ”, Lecture Notes in Computer Science , vol.  111, tizenkilenc nyolcvan egy, P.  37 ( DOI  10.1007 / BFb0105108 , online olvasás , hozzáférés : 2007. november 6. )
6. Herman Schmit , Benjamin Levine és Benjamin Ylvisaker, „  Queue Machines: Hardware Compilation in Hardware  ”, 10. éves IEEE szimpózium a terepi programozható egyedi számítástechnikai gépekről (FCCM'02) , 2002, P.  152. szám ( DOI  10.1109 / FPGA.2002.1106670 , online olvasás , hozzáférés : 2007. november 6. )
7. .
8. Manfred von Thum , „  A sorban gép értékelésére kifejezések  ” [ archív 2007. augusztus 7] , LaTrobe Egyetem,2007(megtekintés : 2007. november 6. ) .

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">