Language Technology:finite-state-machine

From Tieteen termipankki
Jump to: navigation, search

finite-state automaton

finite-state automaton
finite-state machine
FSM
Definition tiloihin ja tilojen välisiin siirtymiin perustuva automaatti, joka hyväksyy tai hylkää merkkijonoja
Definition (en) an automaton based on a finite number of states and transitions between states, and which accepts or rejects strings
Explanation Ää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ä.
Explanation (en) The task of a finite-state machine is to accept or reject strings which consist of characters in a given Language_Technology:alphabet.

Equivalents

ändlig automatruotsi
äärellinen automaattisuomi



References

Lähdeviittaus tähän sivuun:
Tieteen termipankki 17.11.2019: Language Technology:finite-state-machine. (Tarkka osoite: https://tieteentermipankki.fi/wiki/Language Technology:finite-state-machine.)


Siirry tarkastelemaan sivun muokkaushistoriaa →