tilakoneet

Tilakoneet ovat abstrakteja laskentamalleja, jotka kuvaavat järjestelmän tilojen välistä käyttäytymistä syötteiden perusteella. Jokaisella tilakoneella on tilojen joukko, aloitustila, säännöt tilojen välisille siirtymille sekä usein hyväksymistilat, jotka kertovat, milloin syötteen perusteella saavutetaan haluttu lopputulos. Tilakoneen toiminta määritellään syötteellä sekä nykyisellä tilalla, ja siirtymät sekä mahdolliset ulostulot määräytyvät näiden tekijöiden mukaan.

Tilakoneita on useita tyyppejä. Deterministiset tilakoneet (DFA) määrittävät yhdelle tilalle ja yhdelle syötteelle aina saman seuraavan tilan. Ei-deterministiset tilakoneet (NFA) voivat johtaa useampaan mahdolliseen seuraavaan tilaan tai olla siirtymättä mihinkään. Mealy-tilakoneet tuottavat ulostulon siirtymän mukana, eli ulostulo riippuu sekä nykyisestä tilasta että syötteestä, kun taas Moore-tilakoneet tuottavat ulostulon tilasta riippuen, joten ulostulo on sidottu tilaan.

Tilakoneet ovat keskeisiä automaatioteoriassa ja käytännön suunnittelussa. Ne ovat hyödyllisiä mallintamaan protokollia, käyttöliittymien hallintaa sekä digitaalisen logiikan piirejä. Teoreettisesti tilakoneet liittyvät säännöllisiin kieliin: ne voivat tunnistaa vain säännöllisiä kieliä, ja NFA:n voi muuntaa DFA:ksi. Tilakoneet voidaan usein minimoida, jolloin tilojen määrä pienenee säilyttäen tunnistuskyvyn.

Käytännössä tilakoneita sovelletaan esimerkiksi leksikaalisessa analyysissä, ohjelmistojen tilaresurssien kuvaamisessa sekä protokollien ja käyttöjärjestelmien tilapohjaisissa malleissa. Ne tarjoavat selkeän ja jäsennellyn tavan kuvata dynaamista käyttäytymistä, kun syötteet etenevät.