Äärellinen automaatti

Äärellinen automaatti on tietojenkäsittelytieteen automaattiteoriassa ja kieliteknologiassa 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 määrittely

Deterministinen äärellinen automaatti määritellään viisikkona ( Q, Σ, δ, q̂, F ) jossa:

Q on äärellinen joukko tiloja
Σ on kielen aakkosto
δ on osittainen funktio Q×Σ → q
q̂ ∈ Q, alkutila
F ⊆ Q, lopputilojen joukko

DFA voidaan esittää graafisesti graafina, jolloin automaatin tila piirretään solmuina, alkutila merkitään siihen tyhjästä osoittavalla nuolella, ja hyväksyvät lopputilat kaksinkertaisilla ympyröillä. Tilasiirtymät piirretään kaarina tilojen välille. Kaaret nimetään kielen aakkoston mukaan, samasta tilasta voi olla vain yksi saman niminen lähtökaari.

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.

DFA:n operaatioita

DFA:n osittainen tilasiirtymäfunktio δ voidaan täydentää täydelliseksi. Tämä tapahtuu lisäämällä uusi hylkäävä tila, nimeltään vaikkapa q_r (R = reject), ja vetämällä kaari (q_r, a, q_r) jokaiselle a ∈ Σ ja (q, a, q_r) jokaiselle q ∈ Q ja a ∈ Σ, joille δ(q, a) ei ole määritelty.

DFA:n voidaan komplementoida, jolloin aakkostosta Σ muodostetun kielen ℒ komplementti ℒ - Σ* on ne merkkijonot, jotka eivät kuulu ℒ:ään. Tämä tapahtuu muuntamalla kaikki lopputilat ei-lopputiloiksi ja ei-lopputilat lopputiloiksi. Ennen tätä operaatiota DFA:n tilasiirtymäfunktio on muutettava täydeksi.

Saavuttamattomien tilojen poisto: jos DFA:ssa on tiloja, joita ei voida saavuttaa alkutilasta, ne voidaan poistaa kielen muuttumatta. Tämä onnistuu valitsemalla joukkoon Q' vain ne tilat, joihin on polku alkutilasta.

Automaatin minimointi: saman kielen hyväksyviä automaatteja on äärettömän monta. Niitä voidaan konstruktoida vaikka lisäämällä loputtomasti tiloja, joihin ei ole kaaria mistään. Saavuttamattomien tilojen poisto tekee osan minimoinnista, mutta ei täydellistä. Automaatin minimointi tapahtuu etsimällä tilojen joukkoja, lohkoja, jotka hyväksyvät saman kielen. Lohkot voidaan yhdistaa tiloiksi, ja lohkojen väliset siirtymät näiden tilojen välisiksi siirtymiksi.

Minimoitu DFA, josta on poistettu saavuttamattomat tilat on yksikäsitteinen, ja hyväksyy saman kielen kuin alkuperäinen DFA.

Tuloautomaatti: Kahden DFA:n tuloautomaatti muodostaa automaatin, jonka hyväksymä kieli on sama kuin automaattien kielen leikkaus. Se voidaan muodostaa seuraavilla operaatioilla:

Q = Q₁ × Q₂
δ((q₁, q₂), a) = (δ(q₁, a), δ(q₂, a)), jos δ(q₁, a) ja δ(q₂, a) on määritelty, muutoin määrittelemätön
q̂ = (q̂₁ × q̂₂)
F = F₁ × F₂
Σ:n on oltava sama molemmille automaateille.

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.

Sovellutuksia

Äärellisillä automaateilla voidaan mallintaa formaaleja kieliä. Tällöin äärellinen automaatti muodostetaan siten, että siirtymäkaaret ovat kielen aakkoston symboleita, ja kaikki onnistuneet matkat alkutilasta lopputilaan kuvaavat siirtymäjoukoillaan kaikkia kielen sallittuja ilmauksia. Automaatin tunnistama kieli on sen hyväksymien syötteiden joukko.

Äärellisillä automaateilla on kielenmallinnuksessa suora yhteys säännöllisiin ilmauksiin. Säännölliset ilmaukset voi konvertoida äärellisiksi automaateiksi hyvin yksinkertaisella ja intuitiivisella mekaniikalla. Tyypillisesti tässä käytetään apuna indeterminististä automaattia joka determinisoidaan tarvittaessa lopuksi. Esimerkiksi olkoot a, b mielivaltaisia aakkoston kirjainjoukkoja joita vastaa automaatissa joukko tiloja ja kaaria:

a* saadaan aikaan vetämällä aloitustilasta ε-siirtymä lopputilojen ohi ja vastaavasti lopputiloista alkutilaan (0—n kertaa tilajoukon läpikäynti)
(a|b) saadaan erottamalla yhteinen alkutila, josta siirrytään ε-kaarella a:n tai b:n alkutilaan, ja joukkojen lopuista vastaavasti yhteiseen lopputilaan.

Viitteet

Aho A., Ullman, J.D. (1977) Principles of Compiler Design. ISBN 0201000229
Antti Valmari: Ohjelmistotekniikan matemaattiset menetelmät, TTY, 2004
Pekka Orponen: Laskennan teoria, Helsingin yliopisto, 1994

Tietotekniikka