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 q₀, 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 Q_f, 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 automat	ruotsi (svenska)
äärellinen automaatti	suomi (suomi)

Alaviitteet

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

Siirry tarkastelemaan sivun muokkaushistoriaa →