Siirtymäsääntöjä

Siirtymäsääntöjä (transition rules) ovat säännöt, jotka määrittelevät, miten järjestelmä siirtyy tilasta toiseen tietyn tilan ja syötteen perusteella. Ne ovat keskeisiä käsite- ja malliteorian malleissa, kuten valmius- tai automaattimalleissa (finite state machines, automaatit), joissa tila kuvaa järjestelmän nykyistä tilaa ja siirtymät määrittelevät, mihin tilaan siirrytään seuraavan syötteen kohdalla.

Automaatteissa siirtymäsäännöt voivat ilmetä useassa muodossa. Yleisesti ne esitetään siirtymäfunktiona δ, joka kuvaa tilan ja mahdollisen syötteen vaikutuksen seuraavaan tilaan.Deterministisessä finite automaatissa δ: Q × Σ → Q antaa täsmällisen seuraavan tilan jokaiselle tilalle q ja syötteen symbolille a. Nondeterministisessa automaatissa δ: Q × Σ → P(Q) voi johtaa useaan mahdolliseen seuraavaan tilaan. Joissakin malleissa, kuten ε-siirtymillä, voi olla myös siirtymiä ilman syötettä (epsilon-siirtymät). Turingin koneella siirtymä määritellään yleensä tilan, luettavan merkin, kirjoitettavan merkin, pään liikuttamisen suunta ja seuraavan tilan kohdalla.

Siirtymäsääntöjä voidaan esittää rakenteisesti taulukon, funktion tai sääntöparien muodossa. Esimerkki: DFA, jossa tilat ovat {q0, q1}, = Σ = {0,1}, δ(q0,0)=q0, δ(q0,1)=q1, δ(q1,0)=q0, δ(q1,1)=q1. Tämä malli opissee tilansiirtymää, joka riippuu nykyisestä tilasta ja luetusta merkkijonon symbolista.

Sovelluksissa siirtymäsääntöjä käytetään muun muassa kieli- ja protokollanarvioinnissa, suunnittelussa ja todentamisessa sekä kontrollijärjestelmissä. Ne muodostavat perustan sille, miten järjestelmät tunnistavat, validoivat tai tuottavat loogisen toiminnan.

Näkökulmia: siirtymäsääntöjä voidaan käsitellä sekä teoreettisina rakenteina että käytännön toteutuksina, ja niitä tarkastellaan eri mallien kuten automaattien, Turingin koneiden ja soluautomaatioiden yhteydessä. Lisätietoa löytyy automaati- ja kieliteorian lähteistä.