Automaatin minimointi

Automaatin minimoinnilla tarkoitetaan sellaisen ekvivalentin automaatin löytämistä, jossa on mahdollisimman vähän tiloja. Myös automaattia, jossa ei ole yhtään tarpeetonta tilaa, voi vielä yksinkertaistaa.

Esimerkki

Otetaan tämä automaatti:

automaatti hyväksyy vain sanat 01 ja 11. On kuitenkin ilmeistä, että on olemassa yksinkertaisempi kolmen tilan automaatti, joka hyväksyy saman kielen. Tilat q₁ ja q₂ voi yhdistää yhdeksi uudeksi tilaksi {q₁, q₂}, ja ne siirtymät, jotka johtivat tiloihin q₁ tai q₂, johtavat uuteen tilaan, ja sama pätee tiloista q₁ ja q₂ lähteviin siirtymiin. Saamme tämän automaatin:

Tämä automaatti hyväksyy selvästi saman kielen kuin edellinen, ja siinä on silti vähemmän tiloja.

Tilojen ekvivalenssi

Olkoon meillä automaatti A = (Q, Σ, δ, q₀, F). Määrittelemme tilan q ∈ Q kielen, merkitään L(q), seuraavasti:

$L (q) = L ((Q, Σ, δ, q, F))$

Eli vaihdamme automaatin A alkutilan tilasta q₀ tilaksi q ja laskemme tämän automaatin hyväksymän kielen. Toisin sanoen kielessä L(q) ovat kaikki sellaiset sanat w, joilla automaatissa A päästään tilasta q sanalla w automaatin lopputilaan. Jos palaamme edelliseen automaattiin, niin L(q₁) = {1}.

Sanomme, että kaksi eri tilaa q₁ ja q₂ ovat ekvivalentit, jos pätee

$L (q_{1}) = L (q_{2})$

Mitä tämä tarkoittaa? Jos tilat q₁, q₂ ovat ekvivalentit, niin kun teemme niistä automaatin alkutiloja, ne tuottavat saman kielen. Toisin sanoen: jos automaatti päätyy konfiguraatioon (q₁, w) ja (q₂, w), sen täytyy molemmissa tapauksissa joko hyväksyä tai molemmissa tapauksissa hylätä.

Jos palaamme edelliseen automaattiin: tilat q₁ ja q₂ ovat ekvivalentit, koska kun olemme tilassa q₁, voimme hyväksyä syötesanan enää vain silloin, jos sanan lukematon osa on 1. Sama pätee, kun olemme tilassa q₂.

Automaatin minimoinnissa on siis tarkoitus löytää ekvivalentit tilat ja poistaa nämä tilat yhdistämällä ne yhdeksi uudeksi tilaksi samalla tavalla kuin teimme yllä olevassa esimerkissä.

Ekvivalenttien tilojen löytäminen

Mitkä tilat eivät varmasti ole ekvivalentit? Jos otamme lopputilan ja ei-hyväksyvän tilan, ne eivät varmasti ole ekvivalentit, koska lopputilan kieli on eri kuin ei-hyväksyvän tilan kieli — lopputila hyväksyy varmasti sanan ε, ei-hyväksyvä tila ei. Näytämme menetelmän heti esimerkillä. Olkoon meillä tämä automaatti:

Aloitamme luomalla kaksi tilojen joukkoa

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Nyt luomme siirtymätaulukon ja säilytämme tiedon ryhmistä S₁ ja S₂:

$\begin{array}{ccccc} ryhmä & tila & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Nyt muokkaamme taulukkoa niin, että sen sijaan, että siinä olisi suoraan kirjoitettuna, mihin tiloihin annetulla symbolilla mennään, merkitsemme siihen vain ryhmän, johon siirrytään. Esimerkiksi tilasta q₃ pääsemme symbolilla 0 tilaan q₅, joka on ryhmässä S₂. Tilan q₅ sijaan kirjoitamme taulukkoon siis S₂:

$\begin{array}{ccccc} ryhmä & tila & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Nyt jaamme molemmat ryhmät edelleen. Samaan ryhmään laitamme aina tilat, jotka siirtyvät kaikilla symboleilla samoihin ryhmiin. Esimerkiksi tilat q₃ ja q₆ eivät ole samassa ryhmässä, koska ne eivät siirry samaan ryhmään symbolilla 0 eivätkä symbolilla 1. Sen sijaan tilat q₁ ja q₂ ovat samassa ryhmässä, koska kummallakaan tilalla ei ole siirtymää symbolille 0 ja kumpikin tila siirtyy symbolilla 1 ryhmään S₁. Muodostamme siis uudet ryhmät:

$\begin{array}{ccccc} ryhmä & tila & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Jokaisessa ryhmässä on samat siirtymät. Nimeämme vasta syntyneet ryhmät ja selvitämme taas, mihin näistä uusista ryhmistä tilat osoittavat:

$\begin{array}{ccccc} ryhmä & tila & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

Tässä vaiheessa jaamme ryhmiä edelleen. Näemme kuitenkin, ettemme voi enää tehdä uutta jakoa, saisimme samat ryhmät — koska tiloilla q₁ ja q₂ on kyllä samat siirtymät ryhmien tasolla, mutta ne ovat jo samassa ryhmässä eikä ryhmässä S₄ ole muita tiloja. Ekvivalenttien tilojen etsintäalgoritmi on lopussa. Jokaisesta ryhmästä riittää valita yksi tila, muut poistamme, ja kaikki siirtymät, jotka johtivat poistettuihin tiloihin, johtavat siihen yhteen tilaan, jonka valitsimme.

Voimme siis valita, että uudessa automaatissamme on tilat q₃, q₆, q₀, q₁, q₄, ja tilat q₂ ja q₅ poistamme. Kaikki siirtymät, jotka johtivat tilaan q₂, johtavat nyt tilaan q₁, ja kaikki siirtymät, jotka johtivat tilaan q₅, johtavat tilaan q₄:

Automaatin minimoinnin eteneminen

Poistamme saavuttamattomat tilat,
poistamme tarpeettomat tilat,
poistamme ekvivalentit tilat.

Lähteet

Luvut: Saavuttamattomat tilat, Tarpeettomat tilat, Automaatin minimointi

« Edellinen: Tarpeettomat tilat

Seuraava: Säännöllisten kielten sulkeumaominaisuudet »