Language Technology:deterministic-fsa

From Tieteen termipankki
Jump to: navigation, search

deterministic FSA

deterministic FSA (luo nimityssivu)
Definition Ää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]

Equivalents

ändlig automatruotsi



References

  1. Lähde:Jurafsky&Martin2000Section 2.2,ss. 33-49.

Lähdeviittaus tähän sivuun:
Tieteen termipankki 21.10.2019: Language Technology:deterministic-fsa. (Tarkka osoite: https://tieteentermipankki.fi/wiki/Language Technology:deterministic-fsa.)


Siirry tarkastelemaan sivun muokkaushistoriaa →