tilakoneiden

Tilakoneet ovat abstrakti laskentamalli, jolla kuvataan järjestelmän käyttäytyminen tilojen ja niiden välisten siirtymien avulla. Tilakone kuvaa tilojen joukkona, aloitustilan sekä mahdolliset hyväksytyt tilat, ja siirtymät määrittelevät, miten tila kehittyy syötteiden vastaanottamisen myötä. Tilakoneet voivat olla deterministisiä tai ei-deterministisiä, ja niitä käytetään sekä teoreettisessa laskennassa että käytännön sovelluksissa.

Deterministinen tilakone (DFA) tarkoittaa, että jokaiselle tilalle ja jokaiselle mahdolliselle syötteelle on tarkalleen yksi seuraava tila. Ei-deterministinen tilakone (NFA) sallii useita mahdollisia seuraavia tiloja tai kaikkien syötteiden vaihteluita. Yleisiä erotteluja ovat myös Mealy-koneet, joissa tuotokset riippuvat sekä tilasta että syötteestä, sekä Moore-koneet, joissa tuotokset määräytyvät pelkästään tilasta.

Käyttökohteet: Tilakoneita käytetään laajalti ohjelmistotekniikassa ja tietojenkäsittelytieteessä esimerkiksi sanoman- tai säännöstöjen jäsentämisessä, protokollien mallinnuksessa, käyttöliittymien navigoinnin simuloinnissa sekä ohjausjärjestelmien suunnittelussa. Ne ovat myös keskeisiä automaatti- ja muodollisen verifioinnin menetelmissä.

Esimerkki on yksinkertainen kaksitilan järjestelmä, jossa tilat ovat Lukittu ja Vapaa. Siirtymät: tilassa Lukittu vastaanotetaan syöte Coin, jolloin siirrytään tilaan Vapaa; tilassa Vapaa vastaanotetaan syöte Push, jolloin siirrytään tilaan Lukittu. Muissa tilanteissa tila pysyy ennallaan. Tämä kuvaa tilakoneiden peruslogiikkaa, jota voidaan laajentaa Mealy- tai Moore-tyypeiksi tuotosten määrittämiseksi.