Language Technology:finite-state-machine
finite-state automaton
finite-state machine | |||
finite-state automaton | |||
FSM |
Äärellisen automaatin tehtävänä on hyväksyä tai hylätä merkkijonoja, jotka koostuvat annetun aakkkoston merkeistä. Äärelliset automaatit ovat joko deterministisiä tai epädeterministisiä (jos eivät ole deterministisiä). Äärellisesä automaatissa on joukko tiloja Q ja joukko tilojen välisiä siirtymiä. Automaatti aloittaa yhdestä tilastaan q0, joka on osoitettu sen alkutilaksi. Automaatti hyväksyy merkkijonoa siirtymällä kunkin merkin kohdalla tilasta toiseen (tai samaan tilaan) seuraten jotakin senhetkisestä tilasta lähtevää siirtymää. Ollakseen deterministinen, kustakin tilasta saa lähteä enintään yksi siirtymä millekään aakkoston merkille. Automaatti hylkää merkkijonon mm. jos jossakin kohdassa sille ei ole vuorossa olevaa merkkiä varten siirtymää. Osa automaatin kaikista tiloista merkitään ns. lopputiloiksi Qf, joka tarkoittaa sitä, että jos automaatti on saanut siirrytyksi merkkijonon kaikilla merkeillä ja päätyy yhteen näistä lopputiloista, automaatin katsotaan hyväksyneen merkkijonon. Jos automaatti päätyy lopuksi muuhun kuin lopputilaan, automaatin katsotaan hylänneen merkkijonon.
Automaateista piirretään usein graafisia kuvia, jolloin tiloja esitetään ympyröillä ja siirtymiä nuolilla, jotka lähtevät tiloista ja vievät (toisiin) tiloihin. Alkutilaan voi osoittaa nuoli vasemmalta tyhjästä ja lopputilat merkitään usein kaksinkertaisilla ympyröillä.Erikieliset vastineet
ändlig automat | ruotsi (svenska) | |
äärellinen automaatti | suomi (suomi) |
Alaviitteet
Lähdeviittaus tähän sivuun:
Tieteen termipankki 5.11.2024: Language Technology:finite-state-machine. (Tarkka osoite: https://tieteentermipankki.fi/wiki/Language Technology:finite-state-machine.)