Lõplik olekumasin
 | See artikkel vajab toimetamist. (Juuni 2012) |
Lõplik olekumasin ehk lõplik automaat (inglise finite state automaton) kujutab endast käitumismudelit, mis koosneb olekutest, üleminekutest ehk siiretest ja toimingutest[1]. Lõplik automaat on kõige lihtsam olekuautomaat, mis defineeritakse kui viisik M = <K, Σ, δ, q, F>, kus K - lõplik olekute hulk, Σ - lõplik tähestik, q - algolek, F ⊆ K - lõppolekute hulk, δ : K x Σ -> K - üleminekufunktsioon.
Automaat suudab teha teatud tüüpi tööd. Automaadil on "nõel", mis näitab arvule, mida kutsutakse ta olekuks. Osad olekud on "erilised", nagu algolek ja lõppolekud. Lõppolekud on vajalikud, et analüüsida automaadi töö tulemust. Automaat on oma töö lõpul erinevates olekutes, mis võimaldab teha järelduse sisendandmete kohta. [2]
Üleminekute tabel on automaadi mälus ja näeb välja selline:
| 1, A -> 5 |
| 1, C -> 1 |
| 2, B -> 1 |
| 2, C -> 4 |
| 3, C -> 1 |
| ... |
Seda tabelit loetakse nii, et "kui praegune olek on 2 ja järgmine sümbol on B, siis mine olekusse 1". Paar <hetke olek, järgmine sisendsümbol, mis on tähestikus> määrab üleminekureegli(funktsiooni). Automaat töötab lugedes järgmise sisendsümboli ja liikudes tabeli järgi uude olekusse.