Abstrakti automaatti

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7.5.2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Abstrakti automaatti ( algoritmien teoriassa ) on matemaattinen abstraktio , malli diskreetistä laitteesta , jolla on yksi tulo, yksi lähtö ja joka on yhdessä tilassa monista mahdollisista kulloinkin. Tämä laite vastaanottaa yhden aakkoston symbolit sisääntulossa , ja ulostulossa se tuottaa (yleisessä tapauksessa) toisen aakkoston symboleja.

Muodollisesti abstrakti automaatti määritellään viideksi

${\boldsymbol {A=(S,X,Y,\delta ,\lambda )))$

Missä S on automaatin tilojen äärellinen joukko , X, Y ovat vastaavasti äärelliset tulo- ja lähtöaakkoset, joista muodostuvat automaatin lukemat ja tulostamat merkkijonot, on siirtymäfunktio, on lähtöfunktio. $\delta :S\times X\rightarrow S$ $\lambda :S\times X\rightarrow Y$

Abstraktia automaattia, jolla on erottuva alkutila , kutsutaan alkuautomaatiksi. Siten abstrakti automaatti määrittelee alkuautomaattien perheen

${\boldsymbol {(s_{i},A),s_{i}\in S))$

Jos siirtymä- ja lähtöfunktiot on määritelty yksilöllisesti kullekin parille , niin automaattia kutsutaan deterministiseksi. Muussa tapauksessa automaattia kutsutaan ei-deterministiseksi tai osittain määriteltyksi. ${\boldsymbol {(s,x)\in S\times X}}$

Jos siirtymäfunktio ja/tai tulosfunktio ovat satunnaisia, niin automaattia kutsutaan todennäköisyyksiksi .

Abstraktin automaatin tilojen lukumäärän rajoittaminen määritteli sellaisen käsitteen äärelliseksi automaatiksi .

Automaatti toimii kahden sekvenssin generoimisena: automaatin seuraavien tilojen sekvenssin ja lähtösymbolien sekvenssin, jotka symbolisarjalle avautuvat diskreeteillä ajanhetkillä t = 1, 2, 3, .. Diskreettejä ajanhetkiä kutsutaan sykleiksi. ${\boldsymbol {s_{1}[1]s_{2}[2]s_{3}[3]...))$ ${\boldsymbol {y_{1}[1]y_{2}[2]y_{3}[3]...))$ ${\boldsymbol {x_{1}[1]x_{2}[2]x_{3}[3]...))$

Automaattin toimintaa diskreeteinä aikoina t voidaan kuvata toistuvuusrelaatiojärjestelmällä: ${\boldsymbol {s(t+1)=\delta (s(t),x(t));}}$

${\boldsymbol {y(t)=\lambda (s(t),x(t)).))$

Abstraktien automaattien ominaisuuksien selventämiseksi on otettu käyttöön luokitus .

Abstraktit automaatit muodostavat perustavanlaatuisen luokan diskreettejä malleja sekä omana mallina että Turingin koneiden , työntöautomaattien , äärellisten automaattien ja muiden tiedonmuuntimien ydinkomponenttina.

Abstraktia automaatiomallia käytetään laajalti perusmallina luotaessa diskreettejä automaattimalleja, jotka tunnistavat, luovat ja muuntavat merkkijonoja .

Kirjallisuus

Viktor Mihailovich Glushkov . Abstrakti automaattiteoria. - Advances in Mathematical Sciences , osa XVI, no. 5 (101). - M. , 1961. - S. 476.

Viktor Mihailovich Glushkov . Digitaalisten automaattien synteesi. - M . : Valtion fysiikan ja matemaattisen kirjallisuuden kustantamo , 1962. - S. 476.

Sanakirjat ja tietosanakirjat	Iso venäläinen