Tarpeettomat tilat

Äärellisessä automaatissa voi olla tiloja, joista ei ole mahdollista päästä lopputilaan ja jotka ovat siksi turhia. Tällaisia tiloja kutsutaan tarpeettomiksi tiloiksi. Ne haluamme yleensä poistaa, koska ne vain turhaan monimutkaistavat koko automaattia.

Esimerkki tarpeettomista tiloista

Olkoon meillä tämä äärellinen automaatti:

Näemme, että kun päädymme tiloihin q₄ tai q₅, emme enää koskaan pääse kumpaankaan lopputilaan q₁ tai q₂. Tällaiset tilat ovat siis tarpeettomia, ja voimme yksinkertaisesti poistaa ne, jolloin saisimme uuden automaatin, joka olisi kuitenkin ekvivalentti; se hyväksyisi saman kielen. Tarpeettomien tilojen poistamisen jälkeen automaatti näyttäisi tältä:

Se hyväksyisi silti saman kielen. On kuitenkin hetkiä, jolloin tarpeettomia tiloja kannattaa pitää — esimerkiksi kun rakennamme täydellistä automaattia.

Tarpeettoman tilan määritelmä

Olkoon meillä äärellinen automaatti A = (Q, Σ, δ, q₀, F). Sanomme, että tila q ∈ Q on tarpeeton, jos ei ole olemassa yhtään sanaa w ∈ Σ^∗ eikä yhtään tilaa q_f ∈ F, joille

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

Tarpeettomien tilojen poistaminen

Oletamme, että syötteenä on automaatti A = (Q, Σ, δ, q₀, F), jossa ei ole jo valmiiksi saavuttamattomia tiloja. Etsimme vähitellen tilat, jotka johtavat lopputiloihin, sitten tilat, jotka johtavat tiloihin, jotka johtavat lopputiloihin, ja niin edelleen. Näin saamme kaikkien niiden tilojen joukon, jotka eivät ole tarpeettomia. Alussa asetamme S₀ = F. Rakennamme seuraavat joukot S_i kaikille i ∈ ℤ⁺ tämän säännön mukaan:

$$S_i=\{q\in Q|\mathrm{\exists }a\in \mathrm{\Sigma }:\delta (q,a)\in S_{i-1}\}\cup S_{i-1}$$

Kaikkien tilojen, jotka eivät ole tarpeettomia, tuloksena syntyvän joukon voi esittää näin:

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

Ja tarpeettomien tilojen joukon näin:

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

Toisin sanoen: jos pätee S_i = S_{i + 1}, joukossa Q ∖ S_i on tarpeettomat tilat. Havainnollistamme menetelmää tällä automaatilla:

Ensimmäiseksi asetamme yhtälön S₀ = {q₁, q₂}. Seuraavaksi muodostamme joukon S₁ lisäämällä joukkoon S₀ kaikki tilat, joista johtaa siirtymä johonkin joukon S₀ tilaan. Lisäämme siis tilat q₀ ja q₃, koska tilasta q₀ johtaa siirtymä tilaan q₁ ja tilasta q₃ johtaa siirtymä tilaan q₂. Saamme S₁ = {q₀, q₁, q₂, q₃}. Koska S₀ ≠ S₁, jatkamme eteenpäin.

Muodostamme joukon S₂. Etsimme siis kaikki tilat, joista pääsee joukkoon S₁ ja jotka eivät vielä ole joukossa S₁. Se on ainoa tila q₆, josta pääsee tilaan q₃. Saamme S₂ = {q₀, q₁, q₂, q₃, q₆}. Koska S₁ ≠ S₂, jatkamme eteenpäin.

Muodostamme joukon S₃. Onko olemassa uutta tilaa, josta pääsee johonkin joukon S₂ tilaan? Ei ole, tiloista q₄ ja q₅ ei pääse mihinkään joukon S₂ tilaan, ja muut tilat ovat jo joukossa S₂. Pätee siis S₃ = {q₀, q₁, q₂, q₃, q₆}. Koska S₂ = S₃, algoritmi päättyy ja joukko S₂ on niiden tilojen joukko, jotka eivät ole tarpeettomia. Joukko {q₄, q₅} on niiden tilojen joukko, jotka ovat tarpeettomia.

Täsmällisesti uuden ekvivalentin automaatin ilman tarpeettomia tiloja rakennamme näin. Meillä on automaatti A = (Q, Σ, δ, q₀, F), ja rakennamme sille ekvivalentin automaatin A′ = (Q′, Σ, δ′, q₀, F) ilman tarpeettomia tiloja.

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a), jos δ(q, a) ∈ Q′, muuten δ′(q, a) ei ole määritelty

Lähteet

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