Epädeterministinen äärellinen automaatti

Aiemmissa luvuissa esitelty äärellinen automaatti (lyhennämme DFA) oli aina deterministinen, mikä näkyi siinä, että joka hetkellä oli selvää, mitä automaatti tekee. Nyt tutustumme yleisempään käsitteeseen, epädeterministisiin äärellisiin automaatteihin (lyhennämme NFA), joissa samasta tilasta voi lähteä samalle symbolille useita siirtymiä.

Esimerkki

Katso seuraavaa automaatin kaaviota:

Mikä siinä on erikoista? Solmusta q₀ lähtee kaksi kaarta symbolille 0. Jos yritämme hyväksyä sanan 001, näyttäisi siltä, ettei automaatti tiedä, pitääkö sen jäädä tilaan q₀ vai pitääkö sen seurata siirtymää tilaan q₁. Tällainen automaatti olisi epädeterministinen.

Determinismi tarkoittaa tässä, että joka tilanteessa on selvää, mitä automaatti tekee, eikä epäselvyydelle jää sijaa. Deterministisessä automaatissa on jokaista tilaa ja jokaista symbolia kohti vain yksi siirtymä. Epädeterminismi tarkoittaa epäselvyyttä — yhdestä tilasta voi samalle symbolille lähteä vaikkapa kolme siirtymää.

Miten automaatti sitten päättää? Epädeterministinen automaatti valitsee (joskus sanomme myös ”arvaa”) aina sen siirtymän, joka johtaa siihen, että se hyväksyy sanan — jos se on mahdollista.

Jos syötämme automaatille sanan 001, automaatilla on seuraavat tavat käsitellä sanaa:

$$\begin{array}{r}{q}_0\to q_0\to q_0\to q_0\\ q_0\to q_0\to q_1\to q_2\end{array}$$

sekä vaihtoehdot, joissa se ei lue koko sanaa. Ensimmäisessä se pysyi koko ajan tilassa q₀, mikä on ehdottomasti mahdollista, siirtymäsäännöt sallivat sen. Toisessa haarassa se uskaltautui siirtymään seuraaviin tiloihin ja päätyi lopulta tilaan q₂, joka on lopputila. Tässä haarassa automaatti hyväksyisi sanan. Epädeterministinen automaatti valitsee automaattisesti aina sen haaran, jossa se hyväksyy sanan, jos sellainen haara on olemassa.

Miten se onnistuu valitsemaan automaattisesti ”suotuisan” haaran? Voimme kuvitella, että epädeterministinen automaatti käy läpi kaikki mahdolliset haarat, ja jos se löytää haaran, jossa se hyväksyy sanan, se hyväksyy sanan. Miten se voisi käydä kaikki haarat läpi? Yksinkertaisesti niin, että kun se on tilassa, josta lähtee nykyiselle symbolille n kaarta, automaatti kopioi itsensä n kertaa ja jokainen kopio kulkee eri reittiä. Näin käymme vähitellen läpi kaikki mahdollisuudet.

Laskennan puuesitys

Muokkaamme edellistä automaattia hieman:

Epädeterminismi säilyy ensimmäisessä tilassa. Edellinen automaatti hyväksyi kaikki sanat, jotka päättyvät merkkijonoon 01. Tämä muokattu automaatti hyväksyy kaikki sanat, joissa on osasana 01. Se hyväksyy siis esimerkiksi sanan 101 tai 0101. Laskennan kaikki haarat voi helposti havainnollistaa puun avulla, esimerkiksi sanalle 01010 puu voisi näyttää tältä:

Alussa olemme alkutilassa q₀. Syötteenä on sana 01010, ensimmäinen lukematon merkki on 0. Tilasta q₀ lähtee kaksi siirtymää symbolille 0, tiloihin q₀ ja q₁. Puussa tällä solmulla on siis kaksi lasta: q₀ ja q₁. Seuraavaksi luemme symbolin 1. Siinä ei ole epäselvyyttä, siirrymme tiloihin q₀ ja q₂. Sitten luemme merkin 0, ja vasemmassa haarassa tulee taas epäselvyyttä, joten jaamme laskennan kahteen uuteen haaraan. Toisessa jäämme jälleen tilaan q₀ ja toisessa siirrymme tilaan q₁. Ja niin edelleen.

Huomaa, että yhteensä kaksi haaraa päättyy tilaan q₂, eli lopputilaan. Laskennassa on kaksi haaraa, joiden kautta automaatti voi hyväksyä annetun sanan. Tämä automaatti siis hyväksyisi sanan 01010. Voimme yrittää muodostaa vastaavan puun sanalle 1000.

Laskenta joko pysyy tilassa q₀ tai siirtyy tilaan q₁, mutta sieltä ei ole enää minne mennä, koska syötteenä on enää pelkkiä nollia ja tilasta q₁ on siirtymä vain symbolille 1. Mikään laskennan haara ei pääty lopputilaan, joten automaatti ei hyväksy sanaa 1000.

Epsilon-siirtymät

Epädeterministisissä automaateissa voimme lisäksi käyttää epsilon-siirtymiä. Ne ovat siirtymiä, jotka voimme tehdä riippumatta siitä, mikä symboli syötteenä on, ja lukematta mitään symbolia sanasta. Miten voisimme kirjoittaa epädeterministisen automaatin, joka hyväksyisi tyhjän sanan, kaikki pelkistä ykkösistä koostuvat sanat ja muotoa (10)ⁿ olevat sanat, eli 10, 1010, …?

Jaoimme automaatin kahdeksi ”aliautomaatiksi”. Ylempi huolehtii siitä, että se tunnistaa ykkösistä koostuvat sanat, alempi huolehtii muotoa (10)ⁿ olevista sanoista. Yritetään hyväksyä sana 111. Automaatti on alussa tilassa q₀ ja syötteenä on sana 111. Koska käytettävissä on epsilon-siirtymiä, se voi päättää siirtyä tilaan q₁ tai q₂ sen mukaan, kumpi sille sopii. Näemme, että sille sopii siirtyä tilaan q₁. Automaatti siirtyy sinne. Syötteenä on edelleen sana 111! Vasta nyt se alkaa lukea sanan symboleja ja siirtyy tilasta q₁ takaisin tilaan q₁, kunnes se on lukenut koko sanan ja hyväksyy sen.

Jos yrittäisimme hyväksyä sanan 1010, automaatti siirtyisi alussa tilaan q₂ ja alkaisi käsitellä symboleja vasta sieltä, ja hyväksyisi sanan jälleen.

Sanalle 1100 automaatti voisi tehdä mitä tahansa, koska se ei voi hyväksyä sellaista sanaa.

Epsilon-siirtymät ja epädeterminismi helpottavat työtämme monessa asiassa. Esimerkiksi todistuksen siitä, että säännöllisten kielten yhdiste on jälleen säännöllinen kieli, voi kirjoittaa epsilon-siirtymien avulla paljon yksinkertaisemmin kuin deterministisillä äärellisillä automaateilla. Siinä todistuksessa meillä oli esimerkkeinä nämä automaatit

ja

ja lisäksi rakensimme deterministisen äärellisen automaatin, joka hyväksyi molempien kielten yhdisteen. Epsilon-siirtymillä sellaisen automaatin voi rakentaa näin:

Lisäämme yksinkertaisesti uuden alkutilan, josta lähtee kaksi epsilon-siirtymää alkuperäisten automaattien alkuperäisiin alkutiloihin, ja siinä kaikki. Automaatti päättää epädeterministisesti, yrittääkö se hyväksyä sanan ensimmäisellä vai toisella ”aliautomaatilla”.

Epädeterministisen automaatin määritelmä

Olemme jo näyttäneet, miten deterministinen ja epädeterministinen äärellinen automaatti eroavat toisistaan, enää täytyy formalisoida se. Määrittelimme deterministisen äärellisen automaatin viisikoksi (Q, Σ, δ, q₀, F), jossa Q on tilojen joukko, Σ on aakkosto, δ on siirtymäfunktio, q₀ on alkutila ja F on lopputilojen joukko. Ainoa, mikä epädeterminististen automaattien määritelmässä muuttuu, on siirtymäfunktion määritelmä.

Deterministisessä versiossa funktio saattoi kutsulla δ(q, w) palauttaa vain yhden tilan, kun taas epädeterministisessä versiossa se voi palauttaa useita tiloja — jos yhdelle symbolille on määritelty useita siirtymiä. Koska meidän täytyy määritellä myös epsilon-siirtymät, merkitsemme joukkoa Σ ∪ {ε} joukoksi Σ_ε, eli Σ_ε = Σ ∪ {ε}. Funktion δ määrittelemme siis

$$\delta :Q\times {\mathrm{\Sigma }}_{\epsilon }\to 2^Q$$

Tässä 2^Q tarkoittaa potenssijoukkoa, eli joukon Q kaikkien osajoukkojen joukkoa. Laskennan formalisointi on hyvin samankaltainen kuin äärellisillä automaateilla. Automaatin konfiguraatio on jälleen pari (q, w) ∈ Q × Σ^∗. Laskennan askel ↦ on konfiguraatioiden joukon relaatio, jolle

$$(q_i,w_0{w}_1\dots w_n)\mapsto (q_j,w_1\dots w_n),$$

täsmälleen silloin, kun q_j ∈ δ(q_i, w₀). Tässä lauseessa oli suurin ero. Deterministisissä automaateissa tämä ehto kirjoitettiin q_j = δ(q_i, w₀), koska funktio δ palautti aina yhden tilan. Siirtymäfunktion epädeterministinen versio palauttaa tilojen joukon, siksi siinä on symboli ∈. Relaation refleksiivistä ja transitiivista sulkeumaa merkitsemme jälleen ↦ ^∗. Sanomme, että automaatti hyväksyy sanan w täsmälleen silloin, kun on olemassa q_f ∈ F, jolle

$$(q_0,w){\mapsto }^{\ast }(q_f,\epsilon ).$$

Lähteet

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