Äärellinen automaatti

Äärellinen automaatti (englanniksi finite state machine tai finite automaton) on alkeellisen tietokoneen laskentamalli, joka koostuu joistakin tiloista ja siirtymistä ja joka osaa hyväksyä tai hylätä sille annetun sanan.

Esimerkki

Kuvaamme äärellisen automaatin aluksi epämuodollisesti tilakaavion avulla:

Automaatti koostuu tiloista. Kuvassa niitä on kolme, ja ne on piirretty ympyröinä: q₀, q₁ ja q₂. Tilojen välillä on siirtymiä, eli nuolia. Automaatissa täytyy olla myös alkutila, tässä q₀. Alkutila merkitään usein niin, että siihen osoittaa nuoli, joka ei lähde mistään tilasta. Lisäksi automaatissa on tavallisesti hyväksyvä tila eli lopputila. Se piirretään kaksinkertaisella viivalla, joten kuvassa se on tila q₂.

Tällainen automaatti hyväksyy joitakin sanoja. Annamme automaatille sanoja, ja automaatti yrittää hyväksyä ne. Jos se hyväksyy sanan, se vastaa KYLLÄ, jos ei hyväksy, se vastaa EI. Automaattimme yrittää hyväksyä sanoja, jotka koostuvat kirjaimista ”a, b, c”, joten voimme yrittää hyväksyä sanan ”abbc”.

Aloitamme alkutilasta q₀, ja syötteenä on sana ”abbc”. Seuraamme nyt nuolia.

Sana käydään läpi tavalliseen tapaan vasemmalta oikealle, eli ensimmäisenä käsitellään symboli ”a”. Syötteen ”a” nuoli johtaa tilaan q₁, joten siirrymme sinne ja poistamme symbolin ”a” sanasta. Syötteenä on sana ”bbc”:

Syötteen ”b” nuoli osoittaa takaisin tilaan q₁. Poistamme taas ensimmäisen kirjaimen, ja syötteenä on sana ”bc”. Pysymme jälleen tilassa q₁. Lopuksi syötteenä on sana ”c”. Tilasta q₁ syötteen ”c” nuoli vie meidät tilaan q₂.

Olemme käyttäneet kaikki syötesanan kirjaimet ja olemme tilassa q₂, joka on hyväksyvä tila. Tämä äärellinen automaatti siis hyväksyy sanan ”abbc”.

Jos emme olisi lopuksi hyväksyvässä tilassa, automaatti ei hyväksyisi sanaa. Automaatti ei hyväksyisi sanaa myöskään silloin, jos jossakin tilassa ei olisi mihin mennä. Esimerkiksi syötteellä ”ab” päätyisimme tilaan q₁ ja jäisimme sinne — automaatti ei hyväksy tällaista sanaa. Jos kokeilisimme sanaa ”aabbc”, olisimme taas epäonnisia, koska tilasta q₁ ei lähde nuolta kirjaimelle ”a”.

Äärellinen automaatti siis tunnistaa jonkin sanajoukon. Käytännössä automaatilla voisi selvittää esimerkiksi sen, onko annettu syötesana kelvollinen sähköpostiosoite.

Äärellisen automaatin määritelmä

Edellinen intuitiivinen käsitys äärellisestä automaatista täytyy muotoilla täsmällisesti, jotta automaateilla voi jatkossa työskennellä paremmin.

Sanomme, että äärellinen (deterministinen) automaatti on viisikko (Q, Σ, δ, q₀, F), jossa

• Q on tilojen äärellinen joukko,
• Σ (iso sigma) on aakkosto (symbolien eli kirjainten äärellinen joukko),
• δ: Q × Σ ⟶ Q on siirtymäfunktio,
• q₀ ∈ Q on alkutila,
• F ⊆ Q on lopputilojen (hyväksyvien tilojen) joukko.

Palataan edelliseen automaattiin,

jolloin voimme sanoa, että tilojen joukossa Q on kolme tilaa: Q = {q₀, q₁, q₂}. Aakkosto Σ sisältää kirjaimet, joista voimme koostaa sanoja, jotka automaatti sitten hyväksyy tai hylkää. Tässä se on todennäköisesti aakkosto Σ= {a, b, c}, mutta se voi olla myös mikä tahansa sen ylijoukko. Alkutila q₀ on tila q₀, siinä ei ole mitään muutosta. Lopputilojen joukossa on tässä automaatissa vain yksi tila F = {q₂}.

Siirtymäfunktiolla tarkoitetaan niitä kolmea nuolta, joissa on kirjaimet. Jos merkintä δ: Q × Σ ⟶ Q hämmentää, se tarkoittaa vain sitä, että δ on funktio (tarkemmin sanoen kuvaus), joka ottaa kaksi parametria: tilan joukosta Q ja kirjaimen joukosta Σ. Kun funktiota kutsutaan, se palauttaa uuden tilan. Siirtymäfunktiomme voisi määritellä taulukkona näin:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Jos siis kutsumme δ(q₁, c), sovelletaan kolmatta riviä ja funktio vastaa tilalla q₂ — aivan kuten kaavio. Jos olemme tilassa q₁ ja syötteenä on kirjain ”c”, päädymme tilaan q₂. Ennen kuin määrittelemme täsmällisesti, mitä tarkoittaa, että automaatti hyväksyy jonkin sanan, nojaamme käsitteen intuitiiviseen ymmärtämiseen ja katsomme lisää esimerkkejä.

Lisää esimerkkejä

1. Muodosta automaatti, joka toimii binääriaakkoston Σ= {0, 1} yllä ja hyväksyy vain sellaiset sanat, jotka päättyvät ykköseen. Se hyväksyy esimerkiksi sanat 1, 01, 000001, 0101011.

   

   Automaatissamme on kaksi tilaa — alkutila q₀ ja lopputila q₁. Aina kun syötteenä on numero 1, siirrymme lopputilaan q₁ ja pysymme siinä. Jos taas syötteenä on numero 0, siirrymme ei-hyväksyvään tilaan q₀ ja pysymme myös siinä.

2. Muodosta automaatti binääriaakkoston yllä, joka hyväksyy vain sellaiset sanat, joiden ensimmäinen kirjain on eri kuin viimeinen kirjain.

   

   Automaatti jakautuu heti ensimmäisessä askeleessa kahdeksi ”aliautomaatiksi”. Jos sana alkaa nollalla, automaatti siirtyy vasempaan osaan ja jää sinne, jos se alkaa ykkösellä, se siirtyy oikeaan osaan. Sen jälkeen homma on perinteistä: jos olemme vasemmassa osassa ja syötteenä on 1, siirrymme lopputilaan ja jäämme siihen. Jos syötteenä on 0, siirrymme tilaan q₁, joka ei ole lopputila.

   Toisin kuin edellisissä automaateissa, tässä automaatissa on useita lopputiloja, eli F = {q₃, q₄}.

3. Muodosta automaatti binääriaakkoston yllä, joka hyväksyy vain sellaiset sanat, joissa ei ole kahta nollaa peräkkäin.

   

   Tämä automaatti on mielenkiintoinen kahdesta syystä. Ensimmäinen on se, että se hyväksyy tyhjän sanan. Automaatille voi yrittää antaa tyhjän sanan, ja automaatti hyväksyy sen, jos alkutila on samalla lopputila, kuten tässä automaatissa on. Koska tyhjä sana on sana, jossa ei ole kahta nollaa peräkkäin, tämä on oikein. Toinen erikoisuus on se, että tämän automaatin kaikki tilat ovat lopputiloja. Ainoa tapaus, jossa automaatti ei hyväksyisi sanaa, on se, että tilasta ei lähde mitään siirtymää. Näin käy tilassa q₁, jolla ei ole siirtymää syötteelle 0, koska silloin sanassa olisi kaksi nollaa peräkkäin.

4. Muodosta automaatti aakkoston {-,+,.,0,1,…,9} yllä, joka hyväksyy vain sellaiset sanat, jotka esittävät luvun. Se tarkoittaa joko kokonaislukua, esimerkiksi 2, 548, 98263, tai desimaalilukua, esimerkiksi 5584.48, 3.14, ja kumpaakin myös negatiivisena miinusmerkillä: -2, -548, -3.14, sekä erikseen kirjoitetulla plusmerkillä, eli +2, +548, +3.14. Lisäksi meidän täytyy pystyä kirjoittamaan luku 0.123 pelkästään muodossa .123 (ilman alun nollaa), myös molempien etumerkkien kanssa. Otamme käyttöön apumerkinnän: sen sijaan, että kirjoittaisimme kymmenen siirtymää kymmenelle numerolle, käytämme symbolia N. Huomaa, että tässä tehtävässä desimaalierotin on piste, kuten ohjelmoinnissa, koska se on aakkoston symboli.

   

5. Muodosta automaatti binääriaakkoston yllä, joka hyväksyy vain muotoa 0ⁿ1ⁿ olevat sanat, eli sanat, joiden alussa on tietty määrä nollia ja sen jälkeen yhtä monta ykköstä. Esimerkkejä tällaisista sanoista ovat 0011, 00001111, 01.

   Tällaista automaattia ei voi rakentaa, koska emme voi mihinkään ”muistaa” nollien määrää. Meidän pitäisi luoda useita ”aliautomaatteja”, kuten toisessa esimerkissä, mutta näitä ”aliautomaatteja” pitäisi olla äärettömän monta, yksi jokaista arvoa n kohti.

Automaatin laskennan formalisointi

Olemme jo määritelleet äärellisen automaatin täsmällisesti. Seuraavaksi täytyy vielä määritellä, mitä tällainen automaatti oikeastaan tekee, eli määritellään automaatin laskenta.

Automaatin konfiguraatio: Sanomme, että pari (q, w) ∈ Q × Σ^∗ on automaatin konfiguraatio, jossa q on tila, jossa automaatti on parhaillaan, ja w on sanan toistaiseksi lukematon osa. Σ^∗ tarkoittaa aakkoston Σ sulkeumaa (Kleenen tähteä), eli kaikkien niiden sanojen joukkoa, jotka voi koota aakkoston Σ kirjaimista. Sulkeumaan kuuluu myös tyhjä sana, jota merkitsemme ε.

Jos meillä on automaatti (Q, Σ, δ, q₀, F) ja yritämme hyväksyä sanan w, automaatti on alkukonfiguraatiossa (q₀, w). Palataan automaattiin

ja halutaan hyväksyä sana w = abbc. Alkukonfiguraatio on silloin (q₀, abbc).

Laskennan askel määritellään relaationa ↦ joukkojen (Q × Σ^∗) × (Q × Σ^∗) välillä, eli automaatin konfiguraatioiden välillä. Olkoon w = w₀w₁… w_n sanan w toistaiseksi lukematon osa. Sanomme silloin, että parit (q₁, w₀w₁… w_n) ja (q₂, w₁… w_n) ovat relaatiossa ↦, kirjoitetaan

$$(q_1,w_0{w}_1\dots w_n)\mapsto (q_2,w_1\dots w_n),$$

täsmälleen silloin, kun δ(q₁, w₀) = q₂. Palataan esimerkkiimme: alkukonfiguraatio on (q₀, abbc). Kaaviosta näemme, että syötteellä ”a” voimme siirtyä tilaan q₁. Voimme siis kirjoittaa

$$(q_0,abbc)\mapsto (q_1,bbc),$$

koska δ(q₀, a) = q₁. Näin teimme yhden laskennan askeleen — katsoimme, mihin tilaan meidän pitää annetulla syötteellä (= sanan lukemattoman osan ensimmäinen kirjain) mennä, siirryimme sinne ja poistimme sanan lukemattomasta osasta ensimmäisen kirjaimen. Näin saimme uuden konfiguraation.

Laskennan askelrelaation refleksiivistä ja transitiivista sulkeumaa merkitään ↦ ^∗. Jos kirjoitamme K₁ ↦ ^∗ K₂, missä K₁, K₂ ovat automaatin konfiguraatioita, se tarkoittaa, että konfiguraatiosta K₁ päästään usean laskennan askeleen kautta konfiguraatioon K₂, eli on olemassa äärellinen konfiguraatioiden jono, jolle:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

Esimerkiksi automaatissamme pätee (q₀, abbc) ↦ ^∗ (q₁, bc), koska kahden laskennan askeleen jälkeen jäljellä on sana ”bc” ja olemme tilassa q₁. Siis on olemassa tämä konfiguraatioiden jono:

$$(q_0,abbc)\mapsto (q_1,bbc)\mapsto (q_1,bc)$$

Automaatti hyväksyy sanan w täsmälleen silloin, kun on olemassa q_f ∈ F, jolle $$(q_0,w){\mapsto }^{\ast }(q_f,\epsilon )$$ Tämä tarkoittaa, että automaatti hyväksyy sanan w täsmälleen silloin, kun on olemassa sellainen laskennan askelten jono, että sen lopussa olemme lukeneet koko sanan ja olemme automaatin lopputilassa. Se, että koko sana on luettu, ilmaistaan sillä, että konfiguraatiossa sanan paikalla on ε, eli tyhjä sana. Automaattimme hyväksyy sanan abbc, koska on olemassa tämä konfiguraatioiden jono:

$$(q_0,abbc)\mapsto (q_1,bbc)\mapsto (q_1,bc)\mapsto (q_1,c)\mapsto (q_2,\epsilon )$$

ja tila q₂ on lopputila, q₂ ∈ F.

Automaatin hyväksymä kieli on kaikkien niiden sanojen joukko, jotka automaatti hyväksyy. Automaatin A kieltä merkitsemme L(A). Pätee L(A) ⊆ Σ^∗ ja

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }|A\text{ hyväksyy sanan }w\}$$

Säännöllinen kieli on kieli, jonka jokin äärellinen automaatti hyväksyy.

Kaksi äärellistä automaattia on ekvivalentteja, jos ne hyväksyvät saman kielen. Eli automaatit A₁ ja A₂ ovat ekvivalentteja, jos pätee L(A₁) = L(A₂).

Lähteet

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools