Valtion kone

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

Äärillinen automaatti (KA) on algoritmien teoriassa matemaattinen abstraktio , malli diskreetistä laitteesta , jolla on yksi tulo, yksi lähtö ja joka on yhdessä tilassa useista mahdollisista kulloinkin. Se on abstraktin diskreetin automaatin erikoistapaus , jonka mahdollisten sisäisten tilojen määrä on äärellinen .

Toiminnan aikana tulotoiminnot vastaanotetaan peräkkäin SC:n sisääntulossa ja lähdössä SC generoi lähtösignaaleja. Yleensä syötevaikutuksissa automaatin syöte hyväksytään yhden aakkoston symbolien syötteeksi , ja KA:n lähtö toimintaprosessissa antaa symboleja yleensä erilaisessa, ehkä jopa ei leikkaa aakkosten kanssa. syöttö, aakkoset.

Äärillisten automaattien lisäksi on olemassa myös äärettömiä diskreettejä automaatteja - automaatteja, joissa on ääretön määrä sisäisiä tiloja, esimerkiksi Turingin kone .

Siirtyminen avaruusaluksen sisäisestä tilasta toiseen voi tapahtua paitsi ulkoisista vaikutuksista myös spontaanisti.

On olemassa deterministisiä KA -automaatteja, joissa seuraava tila määräytyy yksiselitteisesti nykyisen tilan mukaan ja lähtö riippuu vain nykyisestä tilasta ja nykyisestä sisääntulosta sekä epädeterministinen KA , jonka seuraava tila on yleensä määrittelemätön ja vastaavasti. , lähtösignaalia ei ole määritetty. Jos siirtyminen seuraaviin tiloihin tapahtuu tietyllä todennäköisyydellä, niin tällaista CA:ta kutsutaan todennäköisyyspohjaiseksi CA : ksi.

Mikä tahansa digitaalinen järjestelmä, esimerkiksi tietokoneet tai jotkin tietokoneiden loogiset solmut muistitriggereillä ja muilla laitteilla , voivat toimia esimerkkeinä KA:n fyysisestä toteutuksesta . Yhdistelmäsekvenssilogiikka ei voi olla CA, koska sillä ei ole sisäisiä tiloja (sillä ei ole muistia).

Abstraktista näkökulmasta CA tutkii diskreetin matematiikan osaa - äärellisten automaattien teoriaa .

Äärillisten automaattien teoriaa käytetään käytännössä laajalti esimerkiksi jäsentimissä ja leksereissä , mallipohjaisissa ohjelmistotestauksissa .

Tilakoneen muodollinen kuvaus

Yleinen muodollinen kuvaus

Muodollisesti CA määritellään joidenkin joukkojen järjestetyksi viideksi elementiksi:

A=(S,X,Y,\delta ,\lambda ),

missä on äärellinen joukko automaatin tiloja;

S

X,Y

ovat viimeiset tulo- ja lähtöaakkoset, joista muodostetaan merkkijonoja, jotka automaatti lukee ja tulostaa;

\delta :S\times X\rightarrow S

- siirtymätoiminto;

\lambda :S\times X\rightarrow Y

on lähtöjen funktio.

Abstraktia automaattia, jolla on jokin valittu tila (tätä tilaa kutsutaan alkutilaksi ) , kutsutaan aloitusautomaatiksi . Koska jokaisella KA:lla on äärellinen määrä tiloja ja mikä tahansa sen tila voidaan määrittää alkutilaksi, vastaa sama automaatti alkuautomaatteja, eli KA:n sisäisten tilojen lukumäärää. Siten abstrakti CA määrittelee alkuautomaattien perheen. Jos alkutilaa ei ole määritelty, niin automaattinen käyttäytyminen on aina epädeterminististä, automaatin lähtösana riippuu alkutilasta, joten automaatin täydellinen deterministinen kuvaus tulee olemaan [1] : $s_{0}$ $N$ $N$

A=(S,X,Y,\delta ,\lambda ,s_{0}).

KA:lla on kaksi luokkaa: Moore-automaatti - KA, jossa lähtösignaali riippuu vain sisäisestä tilasta, kuvan mukaan Moore-automaatilla ei ole yhteyttä tulosta lähtötoimintoon ja Mealy-automaatti - lähtösignaali riippuu sekä sisäisestä että tulon tilasta. $x(t)$ $\lambda$

Yleinen kuvaus

On olemassa useita tapoja määrittää algoritmi äärellisen automaatin toiminnalle. Esimerkiksi äärellinen automaatti voidaan määritellä joidenkin joukkojen järjestetyksi viideksi elementiksi :

M=(V,Q,q_{0},F,\delta ),

missä on syöteaakkosto (äärellinen joukko syöttösymboleita ), joista syötesanat muodostetaan ja jonka äärellinen automaatti havaitsee;

V

K

on joukko sisäisiä tiloja ;

q_{0}

- alkutila ;

(q_{0}\in Q)

F

- joukko lopullisia tai lopullisia tiloja ;

(F\alajoukko Q)

\delta

on siirtymäfunktio, joka määritellään kuvaukseksi siten, että ts. järjestetyn parin (tila, tulosymboli tai tyhjä merkkijono) siirtymäfunktion arvo on joukko kaikkia tiloja, joihin siirtyminen tietystä tilasta on mahdollista annettu syöttösymboli tai tyhjä merkkijono, joka yleensä merkitään kirjaimella

\delta \colon Q\times (V\cup \{\varepsilon \})\rightarrow Q

\delta (q,a)=\{r\colon q\,\,{\underset {a}{\to }}\,\,r\}

\varepsilon.

CA:ta analysoitaessa on tapana olettaa, että äärellinen automaatti alkaa jostain alkutilasta , vastaanottaa peräkkäin yhden merkin syöttösanasta (syöttömerkkien ketju). Lukumerkki voi siirtää automaatin uuteen tilaan tai olla siirtymättä uuteen tilaan siirtymäfunktion mukaisesti. $q_{0}$

Vastaanottaa syötetyn merkkijonon ja tehdä siirtymiä tilasta tilaan, automaatti kun on vastaanottanut viimeisen merkin $x$ [ selventää ] syöttösana on jossain tilassa . $q'$

Jos tämä tila on lopullinen, automaatin sanotaan hyväksyneen sanan $x$ [ tyhjentää ]

Muita tapoja määrittää avaruusaluksen toiminta

Alkutila _	seuraava osavaltio
Alkutila _	Syötä merkki a	Syötä merkki b	Mikä tahansa muu hahmo
p0	p1	p0	p0
p1	p1	p2	p1
p2	p3	p4	p2
p3	p3	p5	p3
p4	p4	p4	p4
p5	p3	p5	p5

Tilakaavio (tai joskus siirtymäkaavio ) on graafinen esitys tilajoukosta ja siirtymäfunktiosta. Se on nimetty suunnattu graafi , jonka kärjet ovat KA:n tilat, kaaret ovat siirtymiä tilasta toiseen ja kaarien nimet ovat symboleja, joilla siirtyminen tilasta toiseen tapahtuu . Jos siirtyminen tilasta q 1 tilaan q 2 voidaan suorittaa yhdellä useista symboleista, tulee ne kaikki merkitä kaavion kaaren yläpuolelle.
Siirtymätaulukko on funktion δ taulukkoesitys . Tyypillisesti tällaisessa taulukossa jokainen rivi vastaa yhtä tilaa ja jokainen sarake vastaa yhtä kelvollista syötemerkkiä. Rivin ja sarakkeen leikkauskohdassa oleva solu sisältää tilan, johon automaatin on mentävä, jos se lukee annetun syötesymbolin tässä tilassa. Oikealla on esimerkki kuvan 1 kaaviona esitetystä automaattista hyppytaulukosta.

Päättäväisyys

Tilakoneet jaetaan deterministisiin ja ei- deterministisiin .

Deterministinen äärellinen automaatti (DFA) on sellainen automaatti, jossa ei ole kaaria, joiden tunniste on ε (lause, joka ei sisällä yhtä symbolia), ja mistä tahansa symbolin tilasta siirtyy enintään yhteen tilaan. mahdollista.
Ei-deterministinen äärellinen automaatti (NFA) on deterministisen yleistys. Automaattien epädeterminismi voidaan saavuttaa kahdella tavalla: joko voi tapahtua tyhjän symboliketjun aiheuttamia siirtymiä tilasta tilaan, toisin sanoen spontaaneja siirtymiä ilman ulkoisia vaikutteita, tai KA voi siirtyä tilasta eri tiloihin. saman symbolin vaikutuksesta.

Jos tarkastellaan tapausta, jossa automaatti määritellään muodollisesti seuraavasti: , missä on automaatin alkutilojen joukko , jolloin , tulee kolmas epädeterminismin merkki - useiden alku- (aloitus)tilojen läsnäolo automaatilla . $M=(V,Q,S,F,\delta )$ $S$ $S\subseteq Q$ $M$

Määrittelylause väittää, että mille tahansa äärellistilakoneelle voidaan rakentaa vastaava deterministinen äärellinen kone (kahden äärellistilakoneen sanotaan olevan ekvivalentti, jos niiden kielet ovat samat[ selkeä ] ). Koska tilojen määrä vastaavassa DFA:ssa pahimmassa tapauksessa kasvaa eksponentiaalisesti alkuperäisen NFA:n tilojen lukumäärän kasvaessa, ei käytännössä tällainen määrittäminen aina ole mahdollista. Lisäksi äärelliset automaatit ulostulolla ovat yleensä indeterministisiä.

Kahdesta viimeisestä huomautuksesta johtuen epädeterminististen äärellisten automaattien monimutkaisemmasta monimutkaisuudesta huolimatta juuri NFA:ita käytetään pääasiassa tekstinkäsittelyyn liittyviin tehtäviin. .

Automaattiset ja tavalliset kielet

Äärilliselle automaatille on mahdollista määritellä aakkosissa kieli (sanajoukko), jonka se sallii , eli kutsutaan sanoja, joiden lukeminen siirtää automaattin alkutilasta johonkin lopputiloista. $V$

Kleenen lause sanoo, että kieli on säännöllinen silloin ja vain, jos jokin kyseisessä kielessä käytettävä tilakone sallii sen.

Automaattien minimointi

Jokaiselle säännölliselle kielelle on olemassa ainutlaatuinen, isomorfismiin asti , automaatti, joka hyväksyy tämän kielen ja jolla on pienin mahdollinen määrä tiloja. Deterministisen äärellisen automaatin antaman kielen minimiautomaatti voidaan toteuttaa polynomiajassa, jolloin voidaan optimoida automaatin kanssa työskentelyyn tarvittava muistinkulutus sekä ratkaista ongelmia, kuten kahden automaatin vastaavuuden tarkistaminen polynomiajassa. .

Erikoistuneet ohjelmointikielet

SFC ( Sequential Function Chart ) on graafinen ohjelmointikieli , jota käytetään laajalti teollisuuslogiikkaohjaimien ( PLC ) ohjelmointiin.

Graafisessa kielessä SFC ohjelmaa kuvataan kaavamaisena vaiheiden sarjana, jotka yhdistetään siirtymillä.

Mallin kehittäminen äärellistiloisilla koneilla

Rajallisten automaattien avulla voit rakentaa malleja rinnakkaisista prosessointijärjestelmistä, mutta jos haluat muuttaa rinnakkaisten prosessien määrää tällaisessa mallissa, sinun on tehtävä merkittäviä muutoksia itse malliin. Lisäksi yritys kehittää äärellisellä automaatilla toteutettu monimutkainen malli johtaa automaatin tilojen määrän nopeaan kasvuun, mikä tekee tällaisen mallin kehittämisestä lopulta erittäin aikaavievää. Kuten edellä todettiin, jälkimmäinen ongelma voidaan ratkaista käyttämällä ei-determinististä automaattia.

Mitä äärellistilakone ja peräkkäinen kone voivat "tehdä"?

Vastaus annetaan eri termein riippuen siitä, onko automaatti (vastaavasti P-kone) itsenäinen vai ei [2] . Autonominen äärellinen automaatti, joka alkaa tietystä syklistä, voi generoida vain jaksollisen sekvenssin tiloja x (vastaavasti P-kone on sarja lähtösymboleja y ). Jos tämä sarja koostuu vain yhdestä symbolista, niin tämä tarkoittaa, että automaatti saavuttaa tasapainotilan äärellisessä määrässä syklejä. Jos tämä sekvenssi sisältää useita symboleja, tämä tarkoittaa, että automaatti kulkee peräkkäin näitä symboleja vastaavien tilojen läpi, jolloin automaatin toiminta toistuu määräajoin loputtomasti. Lisäksi, olipa äärellisen pituisten tilojen jaksollinen järjestys mikä tahansa, voidaan aina rakentaa autonominen äärellinen automaatti, joka toisesta jaksosta alkaen generoi tämän sekvenssin. Mitään muuta, paitsi saman tilan tai äärellisen tilasarjan jaksoittaista toistamista, autonominen automaatti ei voi "tehdä". Kuitenkin johtuen siitä, että tietyn toimintasyklin peräkkäinen suorittaminen on tyypillistä monille modernin teknologian alueille, dynaamisia järjestelmiä, joita hyväksyttävässä idealisaatiossa voidaan pitää autonomisena automaatina, käytetään laajalti.

Klassinen esimerkki on nukkeautomaatit, jotka suorittavat monimutkaisia toimintosarjoja, esimerkiksi: tietyn tekstin kirjoittaminen paperille, valmiiden soittojen soittaminen pianolla jne.

Nykyaikainen esimerkki ovat monet automaattiset koneet, automaattiset linjat ja automaattiset ohjausjärjestelmät syklistä tuotantoa varten. Jos automaatti ei ole itsenäinen, eli syötteen tila muuttuu syklistä toiseen, niin vastaus kysymykseen, mitä äärellinen automaatti voi "tehdä" ja mitä ei "tehdä", voidaan antaa eri termein. Vastaus voidaan muotoilla esimerkiksi tapahtumaesityskielellä. Itse asiassa ei-autonominen äärellinen automaatti tai peräkkäinen kone muuntaa vain syötetyt merkkisekvenssit tila- tai ulostulomerkkijonoiksi, ja sanoa, mitä äärellinen automaatti voi ja ei voi "tehdä", on selvittää, mitkä sekvenssimuunnokset ovat mahdollisia äärellisessä automaatissa ja jotka ovat mahdottomia. Mutta koska tilojen (vastaavasti lähtösymbolien) määrä on äärellinen, tämä kysymys vastaa seuraavaa kysymystä: missä tulosekvenssissä kukin mahdollinen tila (tai jokainen lähtösymboli) esiintyy? Tämä viimeinen kysymys äärellisten automaattien teoriassa hyväksytyin termein on muotoiltu seuraavasti: mitä tapahtumia voidaan ja mitä ei voi esittää äärellisessä automaatissa kullakin mahdollisella tilalla (tai jokaisella lähtösymbolilla).

Vastauksen antavat Kleenen lauseet . Tämä vastaus on oikea, koska Kleenen lauseet asettavat välttämättömät ja riittävät edellytykset tapahtumasarjan esitettävyydelle automaatissa, nimittäin: erityiset syötesymbolien sarjat erotetaan - säännölliset joukot . Sitä, että syötesekvenssi ilmestyy tällaisesta joukosta, kutsutaan vastaavaksi säännölliseksi tapahtumaksi. Kleenen lauseet osoittavat, että vain säännölliset tapahtumat voidaan esittää äärellisessä automaatissa. Tapahtumien esittämisen kielellä vastaus kysymykseen, mitä äärellinen automaatti voi "tehdä", on siis annettu yksiselitteisesti: äärellinen automaatti voi edustaa vain säännöllisiä tapahtumia. Useat tärkeät syöttösekvenssit, joita käytännössä joutuu usein käsittelemään, ovat ilmeisen säännöllisiä. Joten esimerkiksi joukon, joka koostuu mistä tahansa äärellisestä määrästä äärellisen pituisia syötesarjoja, tiedetään olevan säännöllisesti säännöllinen; minkä tahansa jaksollisen syöttösekvenssin joukko; joukko äärettömiä sekvenssejä, jotka sisältävät tietyt äärelliset sekvenssit muutaman viime syklin ajalta jne.

Yleisessä tapauksessa, jos ääretön joukko syötesarjoja annetaan jollain mielivaltaisella tavalla, niin kysymys siitä, onko tämä joukko säännöllinen, jää avoimeksi. Asia on siinä, että säännöllisen joukon käsite otetaan käyttöön induktiivisesti, eli muodostetaan algoritmi minkä tahansa säännöllisen joukon muodostamiseksi. Ei kuitenkaan ole olemassa riittävän tehokasta tapaa ratkaista käänteisongelma, eli määrittää, onko jokainen annettu joukko säännöllinen.

Vaikka Kleenen teoreemat vastaavat kysymykseen, mitä tilakone voi tehdä, ne vastaavat tähän kysymykseen tehottomasti. Ensimmäiset yritykset on tehty rakentamaan muita kieliä, joilla vastaus voidaan antaa tehokkaasti. Tämä kieliongelma, jolla on keskeinen rooli tehokkaan vastauksen saamisessa kysymykseen siitä, mitä äärellinen automaatti voi ja mitä ei voi "tehdä", on myös ratkaiseva automaatisynteesin ensimmäisille vaiheille, toisin sanoen, jotta voidaan vastata automaation toiseen vaiheeseen. yllä oleviin kysymyksiin. Jos laajennamme dynaamisten järjestelmien luokkaa, jonka olemme määrittäneet termeillä "äärellinen automaatti" ja "peräkkäinen kone", sisällyttämällä siihen äärettömän muistin (äärettömän muistin malli voi olla esimerkiksi ääretön nauha symbolien tallentamiseen tai ääretön määrä tiloja), sitten tämän laajemman luokan dynaamisille järjestelmille (tämän luokan abstrakteja järjestelmiä kutsutaan Turingin koneiksi ) vastaus kysymykseen "mitä he voivat tehdä?" paljon yksinkertaisempi - ne voivat toteuttaa minkä tahansa ennalta määritellyn algoritmin . Samaan aikaan algoritmin käsite tulkitaan modernissa matematiikassa minkä tahansa rekursiivisen funktion arvojen laskemisen toteutuksena . Tällainen yksiselitteinen ja selkeä vastaus kysymykseen "mitä Turingin kone voi tehdä?" mahdollistaa Turingin koneen käsitteen asettamisen algoritmin käsitteen määrittelyn perustaksi: algoritmi on mikä tahansa prosessi, joka voidaan suorittaa äärellisellä automaatilla, jota on täydennetty äärettömällä muistilla, eli algoritmisesti täydellisillä koneilla, Turingin koneella, Postikoneella jne.

Katso myös

Mili kone
Mooren konepistooli
JFLAP - cross-platform simulaattoriohjelma (automaatit, Turingin koneet, kieliopit)
Automaattinen ohjelmointi
Peräkkäinen toimintokaavio
Kääntäjä
Kääntäjä
Petrin verkot
Jaksologiikka (Sequential Logic)
Päätöstaulukko
Suffiksiautomaatti

Muistiinpanot

↑ Kuznetsov O. P., Adelson-Velsky G. M. Automata // Diskreetti matematiikka insinöörille. - M . : Energia, 1980. - 344 s.
↑ Aizerman M. A., Gusev L. A., Rozonoer L. I., Smirnova I. M., Tal A. A. Logic. Automaatti. Algoritmit. Osavaltio. toim. Fys.-Math. Kirjallisuus 1963, 556 sivua.

Kirjallisuus

Belousov A. I., Tkachev S. B. Diskreetti matematiikka. - M .: MGTU, 2006. - S. 460-587. — ISBN 5-7038-2886-4 .
John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Diskreetti matematiikka. - 2. painos - Williams, 2002. - 528 s. - (Algoritmit ja menetelmät. Ohjelmoinnin taito).
Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Ohjelmointikielten teoria ja toteutus - M.: MZ-Press, 2006, 2. painos. — ISBN 5-94073-094-9
Automaattiteoria / E. A. Yakubaitis, V. O. Vasyukevitš, A. Yu. Gobzemis, N. E. Zaznova, A. A. Kurmit, A. A. Lorents, A. F. Petrenko, V. P. Chapenko // Todennäköisyysteoria. Matemaattiset tilastot. Teoreettinen kybernetiikka. - M.: VINITI, 1976. - T. 13. - S. 109-188. - URL http://www.mathnet.ru/php/getFT.phtml?jrnid=intv&paperid=28&what=fullt&option_lang=rus
Äärillisten automaattien käyttö automaatioongelmien ratkaisemiseen
Glushkov V. M. Digitaalisten automaattien synteesi. — M.: GIFML , 1962. — 476 s.

Linkit

Muodolliset kielet ja viralliset kieliopit
Yleiset käsitteet	Chomsky-hierarkia Aakkoset Sana
Tyyppi 0	Rajoittamaton kielioppi Turingin kone lueteltu kieli Ratkaiseva kieli
Tyyppi 1	Tilanneherkkä kielioppi Tilannekohtainen kieli Lineaarisesti rajattu automaatti
Tyyppi 2	Kontekstiton kielioppi Epäselvä kielioppi Kontekstiton kieli Työntöautomaatti ( deterministinen ) Kasvu Lemma Ogdenin Lemma Cookin lause
Tyyppi 3	Tavallinen kielioppi tavallinen kieli Tavallinen ilme Tilakone ( deterministinen , ei - deterministinen ) DFA-minimointi NFA:n määrittäminen Myhill-Neroden lause
jäsentäminen	LL analysaattori LR jäsentäjä Rekursiivinen laskeutumismenetelmä Kok-Younger-Kasami-algoritmi

Bibliografisissa luetteloissa	NKC : ph210246