Automaatin muuntaminen säännölliseksi lausekkeeksi

Näytämme, miten mikä tahansa äärellinen automaatti muunnetaan säännölliseksi lausekkeeksi.

Algoritmin kuvaus

Syötteenä on jokin NFA A. Ensimmäiseksi teemme siitä GNFA:n. Toisessa vaiheessa poistamme aina yhdellä askeleella yhden tilan, muutamme siirtymäfunktiota oikein ja toistamme, kunnes jäljellä on vain kaksi tilaa — alku- ja lopputila. Niiden välillä on kaari, jonka nimiönä on säännöllinen lauseke, ja se on koko algoritmin tulos. Koko menettely koostuu siis ennen kaikkea tilan poistamisesta ja automaatin sitä seuraavasta korjaamisesta niin, että saamme ekvivalentin automaatin.

Yhden tilan poistaminen

Sen, miten yksi tila poistetaan, voi havainnollistaa yksinkertaisella esimerkillä. Oletetaan, että osa automaatistamme näyttää tältä:

jossa R_i ovat säännöllisiä lausekkeita. Miltä automaatti näyttäisi, jos poistaisimme tilan q_r? Voimme ajatella asian niin, että olemme tilassa q_i ja kysymme, mitkä kaikki sanat pystymme tuottamaan tällä osuudella. Jos menemme tilasta q_i suoraan tilaan q_j, ne ovat kaikki sanat, jotka vastaavat säännöllistä lauseketta R₄.

Jos taas menemme tilaan q_r, voimme tuottaa muotoa R₁ olevia sanoja. Tilassa q_r voimme kuitenkin kiertää lausekkeella R₂, joten voimme oikeastaan tuottaa muotoa $R_1\circ (R_2^{\ast })$ olevia sanoja. Ja koska tilasta q_r pääsee vielä tilaan q_j, lisäämme siihen vielä säännöllisen lausekkeen R₃. Kaiken kaikkiaan tätä reittiä voimme siis saada muotoa $R_1\circ (R_2^{\ast })\circ R_3$ olevia sanoja.

Nyt tiedämme, että tästä automaatin osasta voi syntyä muotoa R₄ tai muotoa $R_1\circ (R_2^{\ast })\circ R_3$ olevia sanoja. Sen voi tietenkin kirjoittaa säännöllisen lausekkeen muotoon $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Nyt voimme helposti poistaa tilan q_r ja jättää vain kaksi tilaa q_i ja q_j, ja lausekkeen R₄ tilalle kirjoitamme juuri lasketun säännöllisen lausekkeen:

Teemme tämän menettelyn jokaiselle kaarelle jokaisesta tilasta q_i johonkin tilaan q_j, silmukat mukaan lukien, eli myös tapaukselle, jossa q_i = q_j.

Yhden tilan poistamisen jälkeen saamme ekvivalentin automaatin — automaatin, joka tunnistaa saman kielen.

Koko algoritmi

Syötteenä on NFA A = (Q, Σ, δ, q₀, F).

1. Muunnamme NFA:n A GNFA:ksi Z = (Q′, Σ, δ′, q₀′, q_f′). Jatkossa kirjaimella k merkitään tilojen määrää automaatissa Z.
2. Jos k = 2, algoritmi päättyy ja alku- ja lopputilan välisellä kaarella on tuloksena oleva säännöllinen lauseke.
3. Jos k>2, valitsemme minkä tahansa tilan q_r, joka on eri kuin alku- ja lopputila, eli q_r ≠ q₀′ ja q_r ≠ q_f′. Sitten luomme uuden GNFA:n Z′ = (Q′′, Σ, δ′′, q₀′, q_f′), jolle pätee: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ ja kaikille q_i ∈ Q′′ ∖ {q_f′} ja kaikille q_j ∈ Q′′ ∖ {q₀′} olkoon $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ jossa R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Jatka sitten askeleesta 2.

Esimerkki

Olkoon syötteenä tämä äärellinen automaatti:

Ensimmäiseksi muunnamme sen GNFA:ksi (turhia ∅-siirtymiä emme piirrä näkyviin):

Nyt sovellamme algoritmin toista osaa ja poistamme jonkin solmun. Aloitamme solmusta q₂. Poistamme solmun q₂ ja lisäämme siirtymän tilasta q₁ tilaan q_f. Merkitsemme tämän siirtymän b(a|b)^∗, koska solmusta q₁ pääsemme tilaan q₂ muotoa b oleville sanoille, sitten voimme kiertää lausekkeella a|b, jolloin saamme (a|b)^∗, ja lopuksi siirrymme epsilon-säännöllä tilaan q_f. Samalla pätee b(a|b)^∗ϵ = b(a|b)^∗. Saamme automaatin:

Jäljellä on viimeisen tilan q₁ poistaminen. Lisäämme kaaren tilasta q_s tilaan q_f. Miten sen merkitsemme? Tilaan q₁ pääsemme epsilon-säännöllä, jonka voi suoraan jättää pois. Sitten voimme kiertää lausekkeella a, joten saamme säännöllisen lausekkeen a^∗. Ja lopuksi kaarta pitkin pääsemme tilaan q_f, joten lauseke liitetään vielä lausekkeeseen b(a|b)^∗. Kuvaamme kaaren siis säännöllisellä lausekkeella a^∗ b(a|b)^∗.

Automaatissa on enää kaksi tilaa, joten algoritmi päättyy. Kaarella on tuloksena oleva säännöllinen lauseke.

Lähteet

• Esimerkki ja algoritmin kuvaus ovat peräisin teoksesta M. Sipser: Introduction to the Theory of Computation