Siirtymäfunktio

Siirtymäfunktio kuvaa tilanmuutoksen dynaamisessa järjestelmässä. Se määrittelee, mihin tilaan järjestelmä siirtyy nykyisestä tilasta q ja annetusta syötteestä a. Järjestelmä voidaan mallintaa tiloilla Q ja syötteillä Σ, ja funktio δ ohjaa tilamuutoksen.

Matemaattisesti malleja on eri tasoisesti. DFA:n kohdalla δ: Q × Σ → Q antaa kullekin tilalle ja syötteelle tarkan seuraavan tilan, kun taas NFA:ssa δ: Q × Σ → P(Q) palauttaa mahdollisten seuraavien tilojen joukon. Mealy- ja Moore-koneissa siirtymän ohella määritellään myös ulostulot, mutta ytimessä ovat tilanmuutokset. Stokastisissa malleissa siirtymä voi olla todennäköisyysjakauma: δ: Q × Σ → Dist(Q), jolloin siirtyminen tapahtuu todennäköisyyksien perusteella.

Eroa on myös siirtymäfunktiosta, jota joskus kutsutaan transition-relationsiksi. Relaatio R ⊆ Q × Σ × Q kuvaa tilojen ja syötteiden mahdollisia siirtymiä yleisesti; δ on funktiona erityistapaus, jossa yhdelle tilapaarille annetaan täsmällinen seuraava tila (tai joukko seuraavia tiloja NFA:ssa).

Esimerkki: DFA, Q = {q0, q1}, Σ = {0,1}, δ(q0,0)=q1, δ(q0,1)=q0, δ(q1,0)=q0, δ(q1,1)=q1. Alustila q0 ja hyväksyvät tilat F = {q1}. Tämä siirtymäfunktio määrittelee, miten tilat vaihtuvat syötteen perusteella.

Käytöt kattavat automaatit ja kielten tunnistus, protokollamallit, ohjelmointikielet sekä tilaverkkojen ja Markov-ketjujen kaltaisten järjestelmien rakentamisen ja analysoinnin.