Saavuttamattomat tilat

Äärellisessä automaatissa voi olla tiloja, joihin ei ole mahdollista päästä. Tällaisia tiloja kutsutaan saavuttamattomiksi tiloiksi. Ne haluamme yleensä poistaa, koska ne vain turhaan monimutkaistavat koko automaattia.

Esimerkki saavuttamattomista tiloista

Olkoon meillä tämä automaatti:

Näemme, että mitä tahansa teemmekin, emme koskaan pääse tilaan q₃, koska siihen ei johda yhtään siirtymää. Sanomme siis, että tila q₃ on saavuttamaton. Kysymys — olisiko tila q₃ saavutettavissa, jos siihen johtaisi siirtymä jostakin toisesta tilasta? Jos vetäisimme siihen kaaren jostakin tiloista q₀, q₁, q₂, q₅, se olisi saavutettavissa. Jos lisäisimme toisen solmun ja vetäisimme siirtymän siitä…

…niin sekä tila q₃ että q₄ olisivat tietenkin saavuttamattomia.

Saavuttamattoman tilan määritelmä

Määrittelemme ensin saavutettavissa olevan tilan. Olkoon meillä äärellinen automaatti A = (Q, Σ, δ, q₀, F). Sanomme, että tila q ∈ Q on saavutettavissa, jos on olemassa sana w ∈ Σ^∗, jolle

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

Tila q ∈ Q on saavuttamaton, jos se ei ole saavutettavissa.

Saavuttamattomien tilojen poistaminen

Jos automaatissa on jo saavuttamattomia tiloja, ne kannattaa poistaa. Rakennamme siis ekvivalentin automaatin A′ = (Q′, Σ, δ′, q₀, F′), jossa ei ole saavuttamattomia tiloja.

Rakennamme saavutettavissa olevien tilojen joukon iteratiivisesti. Aloitamme joukosta S₀ = {q₀}, koska alkutila on varmasti saavutettavissa. Seuraavan joukon rakennamme näin:

$$S_i=\{r|\delta (q,a)=r\text{ jollekin }q\in S_{i-1},a\in \mathrm{\Sigma }\}\cup S_{i-1}$$

Suomeksi sanottuna joukko S₀ on aina annettu, ja joukon S₁ rakennamme ottamalla kaikki joukon S₀ tilat ja selvittämällä, mihin kaikkialle niistä johtaa siirtymiä kaikille aakkoston Σ symboleille. Nämä tilat yhdistämme alkuperäiseen tilojen joukkoon S₀. Samalla tavalla selvitämme joukon S₂ ja seuraavat. Selvästi pätee S_{i − 1} ⊆ S_i.

Saavutettavissa olevien tilojen joukon saamme sitten näin:

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$$

Voi näyttää oudolta, että yritämme yhdistää äärettömän monta joukkoa S_i, mutta automaatissa on vain äärellinen määrä tiloja. Se tarkoittaa, että jossakin vaiheessa joukot S_j ja S_{j + 1} ja kaikki seuraavat ovat samat, joten myös äärettömän monen joukon yhdisteenä voimme saada äärellisen tilojen joukon.

Palataan automaattiin

ja yritetään löytää saavutettavissa olevien tilojen joukko. Aloitamme asettamalla perusyhtälön

$$S_0=\left\{q_0\right\}$$

Nyt laskemme joukon S₁. Meidän täytyy löytää kaikki tilasta q₀ lähtevät siirtymät ja lisätä niiden kohdetilat joukkoon S₀. Koska pätee q₀ → ^a q₁ ja q₀ → ^bq₂, joukossa S₁ on lisäksi tilat q₁ ja q₂:

$$S_1=\{q_0,q_1,q_2\}$$

Seuraavaksi muodostamme joukon S₂. Katsomme, minne kaikkialle pääsemme tiloista q₀, q₁, q₂. Ainoa uusi tila on q₅, johon pääsemme tilasta q₁:

$$S_2=\{q_0,q_1,q_2,q_5\}$$

Sitten muodostamme joukon S₃. Pääsemmekö tiloista q₀, q₁, q₂, q₅ johonkin uuteen tilaan? Emme, joten joukossa S₃ on samat alkiot kuin joukossa S₂:

$$S_3=\{q_0,q_1,q_2,q_5\}$$

Koska S₂ = S₃, myös S₃ = S₄ = S₅ = … Jos yhdistämme kaikki joukot S_i, saamme joukon S₂, koska mihinkään seuraavaan joukkoon ei tule enää yhtään uutta alkiota.

Automaatin saavutettavissa olevien tilojen joukko on siis {q₀, q₁, q₂, q₅}. Saavuttamattomat tilat saamme pelkällä joukkojen erotuksella:

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$$

Automaattimme saavuttamattomien tilojen joukko on {q₃, q₄}. Poistamme automaatista A kaikki saavuttamattomat tilat ja kaikki siirtymät, joissa oli jokin saavuttamaton tila. Eli ekvivalentin automaatin ilman saavuttamattomia tiloja A′ = (Q′, Σ, δ′, q₀, F′) automaatille A = (Q, Σ, δ, q₀, F) määrittelemme seuraavasti:

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
• $F^{\prime }=F\cap Q^{\prime }=F\cap \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$

Lähteet

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