Äärellinen automaatti

Äärellinen automaatti on tietojenkäsittelytieteen automaattiteoriassa, kieliteknologiassa ja generatiivisessa kielitieteessä käytetty käsite, joka viittaa tehtävän, kielen tai vaikkapa tietojoukon mallintamiseen eräänlaisena tilojen ja niiden välisten relaatioiden tai siirtymien joukkona. Äärellinen automaatti on malli äärellistilaiselle tietokoneelle, joka saa syötteen merkki kerrallaan.
Automaatit jaetaan niiden tilasiirtymien ominaisuuksien mukaan kahteen ryhmään: epädeterminisissä äärellisissä automaateissa on tyhjiä kaaria, joita merkitään joko lambdalla 'λ' tai epsilonilla 'ε', ja kutsutaan sovellusalueesta riippuen vaikkapa vapaiksi siirtymiksi, tai tyhjäksi syötteeksi. Tällaisen kaaren tarkoitus on mahdollistaa vapaa siirtyminen tilasta toiseen, joka usein helpottaa automaatin kokoamista. Toinen erikoistapaus kaaren paino tai todennäköisyys, jotka viittaavat siirtymän valintaan jonkinasteisen sattuman mukaan.
Äärellisiä automaatteja tyypillisesti kuvataan graafisesti siten, että tiloja merkitään ympyröillä tai ellipseillä, ja tilojen välisiä siirtymiä merkitään nuolilla. Sekä tilat, että siirtymät ovat nimettyjä. Tilojen nimet kirjoitetaan tässä ympyrän sisälle, ja siirtymien nimet kaaren päälle tai sen läheisyyteen.

Deterministinen äärellinen automaatti

Deterministinen äärellinen automaatti, lyh. DFA (engl. deterministic finite-state automaton) on tila-automaatti, jossa kustakin tilasta voi olla vain yksiselitteisiä tilasiirtymiä muualle. Tällaisen automaatin erottamisen peruste on, että näin voidaan koneellisesti tai mekaanisesti läpikäydä automaattia ilman epäselvyyksiä tai välivaiheita.

DFA:n toiminta

DFA aloittaa toimintansa alkutilasta q̂ ja lukee syöteaakkostoon kuuluvia merkkejä. Merkin lukemisen seurauksena voi tapahtua kaksi asiaa: jos siirtymä δ(q, a) on määritelty, automaatti siirtyy tilaan δ(q, a), muutoin automaatti lakkaa olemasta missään tilassa.
Deterministinen äärellinen automaatti D hyväksyy kielen merkkijonon α jos ja vain jos α:n lukeminen vie D:n alkutilasta johonkin lopputilaan.
Äärellinen automaatti kuvaa siis yleensä kaikkia mahdollisia siirtymäreittejä alkutilasta lopputilaan oikeina ratkaisuina, kun taas mikä tahansa automaatin seuraaminen joka päätyisi muualle kuin lopputilaan antaisi virheellisen tuloksen.

Epädeterministinen äärellinen automaatti

Epädeterministinen äärellinen automaatti, lyh. NFA (engl. non-deterministic finite-state automaton) on tila-automaatti, jossa kustakin tilasta voi olla samalla aakkosella tilasiirtymiä useampaan kuin yhteen tilaan. Nimessä oleva osa epädeterministinen tulee siitä, että saman ratkaisun tuottavat tilat voidaan käydä lävitse useampaa kuin yhtä polkua pitkin kulkemalla. NFA:n ilmaisuvoima ei ole suurempi kuin DFA:n, mutta tietyntyyppiset DFA:t voi ilmaista huomattavasti yksinkertaisemmilla tilakoneilla NFA:ta käyttäen. Mielivaltaisesta epädeterministisestä äärellisestä automaatista voidaan muodostaa algoritmisesti saman kielen hyväksymä vastaava deterministinen automaatti.
NFA:ssa DFA:n osittainen tilasiirtymäfunktio δ korvataan tilasiirtymärelaatioilla, joka merkitään Δ. NFA on ystävällisesti epädeterministinen, ja hyväksyy merkkijonon α, jos on olemassa polku q̂─α→q, jossa q ⊂ F. Eli valitsee aina hyväksyntään johtavan tavan jos sellainen on olemassa.