Language Technology:deterministic-fsa
deterministic FSA
| deterministic FSA (luo nimityssivu) |
Määritelmä
Äärellisen automaatin tehtävänä on hyväksyä tai hylätä merkkijonoja,jotka koostuvat annetun aakkkoston merkeistä.Äärellisesä automaatissa on joukko tiloja Q ja setoimii siirtymällä tunnistettavan merkkijonon kunkin kohdalla tilastatoiseen (tai samaan tilaan). Tiloja kuvataan usein ympyröillä.Siirtyminen tapahtuu ns. tilasiirtymienmukaisesti. Siirtymiä kuvataan usein nuolella, joka lähteetämänhetkisestä tilasta ja päättyy uuteen tilaan. Ollakseendeterministinen, kustakin tilasta saa lähteä enintään yksi siirtymämillekään aakkoston merkille. Eräs tiloista on alkutila q0 ja automaatti on ennen ensimmäisen merkintunnistamista siinä tilassa. Automaatti hylkää merkkijonon mm. josjossakin kohdassa sille ei ole vuorossa olevaa merkkiä vartensiirtymää. Osa automaatin kaikista tiloista merkitään ns. lopputiloiksi Qf, joka tarkoittaa sitä, että josautomaatti on saanut siirrytyksi merkkijonon kaikilla merkeillä japäätyy yhteen näistä lopputiloista, automaatin katsotaan hyväksyneenmerkkijonon. Jos automaatti päätyy lopuksi muuhun kuin lopputilaan,automaatin katsotaan hylänneen merkkijonon.[1]
Erikieliset vastineet
| ändlig automat | ruotsi (svenska) |
Alaviitteet
- ↑ Lähde:Jurafsky&Martin2000Section 2.2,ss. 33-49.
Lähdeviittaus tähän sivuun:
Tieteen termipankki 20.4.2024: Language Technology:deterministic-fsa. (Tarkka osoite: https://tieteentermipankki.fi/wiki/Language Technology:deterministic-fsa.)