Lõppautomaadid

Lõppautomaadid on piiratud seisunditega arvutusmudel, mida kasutatakse keelte ja järjestuste kirjeldamiseks. Nad koosnevad viiest põhiomadusest: Q on lõplik arv olekuid, Σ on sisendi tähestik, δ on üleminekufunktsioon, q0 on algolek ning F on vastuvõetud (lõpp) olekute hulk.

Deterministlik lõppautomaat (DFA) ja mitte‑deterministlik lõppautomaat (NFA) erinevad üleminekute määratlusest. DFA puhul on iga oleku ja sisendi kombinatsioonil täpselt üks järgnev olek: δ: Q × Σ → Q. NFA puhul võib sama kombinatsiooniga olla mitu võimalikku järgmist olekut või kasutada epsilon‑üleminekuid (δ: Q × (Σ ∪ {ε}) → P(Q)).

Keel, mida automaat tunnetab, on L(M) = { w ∈ Σ* | δ*(q0, w) ∈ F }. δ* on üleminekufunktsioon sõna peal. Iga NFA-l on ekvivalent DFA (kasutades subset construction), seega lõppautomaatide keelte klass on regulaarsetel keelidel. Regulaarseid keeli on võimalik kombineerida operatsioonidega nagu unioon, konkateneerimine ja star; DFA jaoks on täiendamine (complement) samuti võimalik, mis muudab regulaarseid keeli hästi hallatavaks.

Rakendused hõlmavad tekstitöötlust ja mustrite tuvastamist, sümbolite järjestuste kontrollimist kompilaatorites ja kõne-/riistvara kontrolli. Regulaarseid keeli ja lõppautomaatide teooriat kasutatakse laialdaselt tekstiotsingus, skeemide valideerimisel ning lõppautomaatide jõudlust ja suurust käsitlevate analüüside jaoks.

Ajaloos on lõppautomaatide kontseptsioon arenenud 1950.–1960. aastatel; Kleene'i regulaarseid väljendeid ja Rabin–Scott'i tulemus ekvivalentsuse kohta NFAs ja DFAs on tihti mainitud kui alused. Täpne töökooseis hõlmab ka teisi varaseid sümbolismide ja keelte teooria panuseid.