Automatisk radmaskin
I teoretisk informatikk , spesielt i automatteori , er en køautomat (på engelsk " tail automaton " ) en endelig automat med uendelig minne organisert som hjelpefil . Det er en beregningsmodell som tilsvarer Turing-maskiner , og aksepterer derfor samme klasse av språk . I denne, skiller denne modellen seg fra pushdown automata som bare gjenkjenner algebraiske språk . Så mye som batteridrevne PLCer fungerer i sist i, først ut (LIFO) -modus, fungerer en kø-PLC i først inn, først ut (FIFO) -modus .
Formell beskrivelse
En køautomat består av følgende data:
M=(Q,Σ,Γ,$,s,δ){\ displaystyle M = (Q, \ Sigma, \ Gamma, \ $, s, \ delta)}![{\ displaystyle M = (Q, \ Sigma, \ Gamma, \ $, s, \ delta)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba64f99b6703690ec46c9d1ee97c2a944f4feb3c)
-
Q{\ displaystyle \, Q}
er et endelig sett med stater ;
-
Σ{\ displaystyle \ Sigma}
er inngangsalfabetet ;
-
Γ{\ displaystyle \, \ Gamma}
er stabelalfabetet , med ; alfabetet er ferdig;Σ⊆Γ{\ displaystyle \, \ Sigma \ subseteq \ Gamma}![{\ displaystyle \, \ Sigma \ subseteq \ Gamma}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cb3a7b265405af76cb5ab83fc1050ec937185e1)
-
$∈Γ∖Σ{\ displaystyle \, \ $ \ i \ Gamma \ setminus \ Sigma}
er et spesialsymbol kalt det første køsymbolet ;
-
s∈Q{\ displaystyle \, s \ i Q}
er den opprinnelige tilstanden ;
-
δ:Q×Γ→Q×Γ∗{\ displaystyle \, \ delta: Q \ times \ Gamma \ rightarrow Q \ times \ Gamma ^ {*}}
av overgangsfunksjonen (der er et sett av endelige ord i løpet , dvs. Kleene stjerne av ).Γ∗{\ displaystyle \, \ Gamma ^ {*}}
Γ{\ displaystyle \, \ Gamma}
Γ{\ displaystyle \, \ Gamma}![\, \ Gamma](https://wikimedia.org/api/rest_v1/media/math/render/svg/329aab33a119bfeac6ac1f1d7bc37818b42b9443)
En PLC- konfigurasjon er et par som består av tilstanden og innholdet i køen. Den opprinnelige konfigurasjonen med et gitt inngangsord er definert av , og overgangsforholdet fra en konfigurasjon til en annen er definert av:
(q,γ)∈Q×Γ∗{\ displaystyle \, (q, \ gamma) \ i Q \ times \ Gamma ^ {*}}
q{\ displaystyle q}
γ{\ displaystyle \ gamma}
x{\ displaystyle \, x}
(s,x$){\ displaystyle \, (s, x \ $)}
→M{\ displaystyle \ rightarrow _ {M}}![{\ displaystyle \ rightarrow _ {M}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de84fb9500e1ced8c528607a9eb5469a44df3f33)
(s,PÅα)→M(q,αγ){\ displaystyle \, (p, A \ alpha) \ rightarrow _ {M} (q, \ alpha \ gamma)}![{\ displaystyle \, (p, A \ alpha) \ rightarrow _ {M} (q, \ alpha \ gamma)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d10df15f290cea100665e77034e34625a799475)
hvor er et symbol fra stabelalfabetet ,, og . I denne relasjonen er "først-inn-først-ut" -egenskapen synlig ved at symbolet fjernes ved hodet, og ordet legges til i halen.
PÅ{\ displaystyle A}
α∈Γ∗{\ displaystyle \ alpha \ in \ Gamma ^ {*}}
(q,γ)=δ(s,PÅ){\ displaystyle (q, \ gamma) = \ delta (p, A)}
PÅ{\ displaystyle A}
α{\ displaystyle \ alpha}![\ alfa](https://wikimedia.org/api/rest_v1/media/math/render/svg/b79333175c8b3f0840bfb4ec41b8072c83ea88d3)
Maskinen godtar inntastingsordet hvis maskinen etter et endelig antall overganger når en konfigurasjon der køen er tom, eller hvisx∈Σ∗{\ displaystyle \, x \ in \ Sigma ^ {*}}![{\ displaystyle \, x \ in \ Sigma ^ {*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba18fb61b1fd305e9467b31eee164df9c522a6ba)
(s,x$)→M∗(q,ϵ).{\ displaystyle \, (s, x \ $) \ rightarrow _ {M} ^ {*} (q, \ epsilon).}![{\ displaystyle \, (s, x \ $) \ rightarrow _ {M} ^ {*} (q, \ epsilon).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/932fd05e4ad6481f7285b339e006d3d9369808b6)
Eksempel
Settet med kvadrater med ord på et gitt alfabet aksepteres av en filautomat.
xx{\ displaystyle xx}![xx](https://wikimedia.org/api/rest_v1/media/math/render/svg/01942dcb4131a025f2584b13809d039803492ffd)
Det kan bevises at filautomater tilsvarer Turing-maskiner. For å simulere en Turing-maskin ved hjelp av en køautomat, konstruerer vi en automat som til enhver tid holder innholdet på Turing-maskinbåndet med to spesielle markører, en for posisjonen til maskinhodet. maskinen, den andre for enden av båndet. Automat-til-kø-overgangene simulerer Turing-maskinens ved å krysse hele køen, fjerne symbolene øverst i køen og legge dem til på slutten av køen mens du utfører rundt lese- / skrivehodet til Turing-maskin, en av overgangene.
Omvendt kan vi simulere en køautomat av en Turing-maskin med to bånd, en for inngangsdata, den andre for køen, med tilsvarende overganger. Et formelt bevis er noen ganger en øvelse i et teoretisk datavitenskapskurs.
applikasjoner
Kømaskiner gir en enkel modell som datamaskinens maskinvarearkitektur , visse programmeringsspråk eller algoritmer kan baseres på .
Relaterte artikler
Merknader og referanser
(fr) Denne artikkelen er helt eller delvis hentet fra den
engelske Wikipedia- artikkelen med tittelen
" Køautomat " ( se listen over forfattere ) .
-
Dexter C. Kozen , Automata and Computability , New York, Springer-Verlag,
1997( 1 st ed. 1951), 400 s. ( ISBN 978-0-387-94907-9 , online presentasjon ) , s. 368–370.
-
Bernard Vauquelin og Paul Franchi-Zannettacci , “ Automates a file ”, Theoretical Computer Science , vol. 11, n o to1980, s. 221–225 ( DOI 10.1016 / 0304-3975 (80) 90047-X , lest online , åpnet 10. august 2017 )
-
Definisjonen gitt i Vauquelin og Franchi-Zannettacci (1980) er forskjellig.
-
(in) Teodor Rus , " Variants of Turing Machines " [ arkiv
21. september 2008] [PDF] , Lecture Notes Covering Theory of Computation , University of Iowa, Iowa City, IA, 52242-1419 (åpnet 6. november 2007 ) .
-
M. Feller og Miloš D. Ercegovac, “ Køen maskiner: en organisasjon for parallell databehandling ”, forelesningsnotater i Computer Science , vol. 111,
nitten åtti en, s. 37 ( DOI 10.1007 / BFb0105108 , leses online , åpnet 6. november 2007 )
-
Herman Schmit , Benjamin Levine og Benjamin Ylvisaker, “Kømaskiner : maskinvarekompilering i maskinvare ”, 10. årlige IEEE-symposium om feltprogrammerbare tilpassede datamaskiner (FCCM'02) ,
2002, s. 152 ( DOI 10.1109 / FPGA.2002.1106670 , lest online , åpnet 6. november 2007 )
-
.
-
Manfred von Thum , " En kømaskin for evaluering av uttrykk " [ arkiv av
7. august 2007] , LaTrobe University,2007(åpnet 6. november 2007 ) .
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">