Language Technology:finite-state-machine

    Tieteen termipankista

    finite-state automaton

    finite-state machine
    finite-state automaton
    FSM
    Määritelmä tiloihin ja tilojen välisiin siirtymiin perustuva automaatti, joka hyväksyy tai hylkää merkkijonoja
    Määritelmä (en) an automaton based on a finite number of states and transitions between states, and which accepts or rejects strings
    Selite

    Ää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ä.
    Selite (en) The task of a finite-state machine is to accept or reject strings which consist of characters in a given Language_Technology:alphabet.

    Erikieliset vastineet

    ändlig automatruotsi (svenska)
    äärellinen automaattisuomi (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.)