Kieliteknologia:äärellinen automaatti
äärellistilainen automaatti | äärellinen automaatti
| äärellistilainen automaatti | |||
| äärellinen automaatti |
Määritelmä
tiloihin ja tilojen välisiin siirtymiin perustuva automaatti, joka hyväksyy tai hylkää merkkijonoja
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ä.
Erikieliset vastineet
| FSM | englanti (English) | |
| finite-state automaton | englanti (English) | |
| finite-state machine | englanti (English) | |
| automate fini | ranska (français) | |
| machine à états finis | ranska (français) | |
| tillståndsmaskin | ruotsi (svenska) | |
| ändlig automat | ruotsi (svenska) | |
| Zustandsautomat | saksa (Deutsch) | |
| Zustandsmaschine | saksa (Deutsch) | |
| endlicher Automat | saksa (Deutsch) |
Lähikäsitteet
- alphabet (osa)
- automaton (yläläsite)
- deterministinen äärellinen automaatti (alakäsite)
- epädeterministinen äärellinen automaatti (alakäsite)
- start-state (osa)
- tila (osa)
Käytetyt lähteet
Alaviitteet
Lähdeviittaus tähän sivuun:
Tieteen termipankki 5.11.2024: Kieliteknologia:äärellinen automaatti. (Tarkka osoite: https://tieteentermipankki.fi/wiki/Kieliteknologia:äärellinen automaatti.)