Säännöllisten kielten yhdiste

Olkoon meillä kaksi säännöllistä kieltä L₁, L₂. Todistamme, että niiden yhdiste L = L₁ ∪ L₂ on myös säännöllinen kieli.

Menetelmä deterministisen automaatin avulla

Menetelmän idea

Meillä on kaksi säännöllistä kieltä L₁ ja L₂, ja haluamme todistaa, että niiden yhdiste L₁ ∪ L₂ on jälleen säännöllinen kieli. Koska L₁ ja L₂ ovat säännöllisiä kieliä, on olemassa äärelliset automaatit A₁ ja A₂, jotka hyväksyvät kielet L₁ ja L₂, eli pätee L(A₁) = L₁ ja L(A₂) = L₂. Rakennamme seuraavaksi äärellisen automaatin A, joka hyväksyy kielen L₁ ∪ L₂, ja todistamme näin, että kieli L₁ ∪ L₂ on säännöllinen.

Miten teemme sen? Meillä on käsillä äärelliset automaatit A₁ ja A₂, jotka hyväksyvät kumpikin oman kielensä. Voimme sanoa, että sana w kuuluu kieleen L₁ ∪ L₂ täsmälleen silloin, kun ainakin toinen automaateista A₁ tai A₂ hyväksyy sen.

Automaatti A voisi toimia niin, että syötteellä w se simuloi automaatin A₁ laskentaa syötteellä w. Jos A₁ hyväksyy sanan w, myös A hyväksyy sanan w. Jos A₁ hylkää sanan w, A yrittää vielä simuloida automaatin A₂ laskentaa syötteellä w. Jos A₂ hyväksyy sanan w, myös A hyväksyy sanan w. Muuten se hylkää.

Meidän täytyy vielä formalisoida, mitä tarkoittaa, että automaatti A ”simuloi” toisen automaatin laskentaa.

Formalisointi

Meillä on kaksi säännöllistä kieltä L₁ ja L₂, jotka äärelliset automaatit hyväksyvät:

$\begin{array}{rcl} A_{1} & = & (Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1}) \\ A_{2} & = & (Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2}) . \end{array}$

Rakennamme äärellisen automaatin A = (Q, Σ, δ, q, F), joka hyväksyy kielen L = L₁ ∪ L₂. Hyödynnämme ajatusta kahden automaatin A₁, A₂ simuloinnista. Kuvitellaan siis, että syötteenä on sana w = w₁w₂… w_n ja simuloimme nyt samanaikaisesti automaattien A₁ ja A₂ kulkua sanalle w. Automaatin A₁ alkukonfiguraatio on (q₁, w₁w₂… w_n), automaatin A₂ alkukonfiguraatio on (q₂, w₁w₂… w_n). Kummassakin automaatissa teemme nyt laskennan askeleen, jolloin päädymme konfiguraatioihin (δ₁(q₁, w₁), w₂… w_n) ja (δ₂(q₂, w₁), w₂… w_n).

Näemme, että nämä konfiguraatiot eroavat vain ensimmäisessä komponentissa, toinen komponentti — sanan lukematon osa — on aina sama. Simuloinnin aikana meidän ei siis tarvitse pitää yllä kahta kahden automaatin konfiguraatiota, vaan riittää yksi muotoa ((q_i, q_j), w_l… w_n) oleva konfiguraatio, jossa q_i ∈ Q₁ ja q_j ∈ Q₂. Toisin sanoen rakennettavan automaattimme A alkukonfiguraatio on ((q₁, q₂), w). Parin (q₁, q₂) ensimmäinen osa on tila, jossa automaatti A₁ parhaillaan on, ja toinen komponentti on automaatin A₂ nykyinen tila.

Voimme siis kirjoittaa, että rakennettavan automaatin A tilojen joukko on Q = Q₁ × Q₂. Se on kahden edellisen automaatin tilojen karteesinen tulo. Seuraava ajatus on, että automaatin A alkutila on (q₁, q₂), ja jos automaatti A₁ siirtyy symbolilla w₁ tilaan q_i ja automaatti A₂ siirtyy symbolilla w₁ tilaan q_j, automaatti A siirtyy symbolilla w₁ tilaan (q_i, q_j).

Siirtymäfunktion δ kirjoitamme näin (oletamme tässä jo, että olemme parhaillaan tiloissa q_i ja q_j):

$δ ((q_{i}, q_{j}), w) = (δ_{1} (q_{i}, w), δ_{2} (q_{j}, w))$

Jäljellä on enää pieniä yksityiskohtia. Aakkostolle pätee Σ= Σ₁ ∪ Σ₂. Alkutila on q = (q₁, q₂). Ja lopputilat ovat kaikki parit (q_i, q_j), joille pätee joko q_i ∈ F₁ tai q_j ∈ F₂.

Menetelmän havainnollistus

Olkoon meillä kaksi automaattia. Ensimmäinen on automaatti A₁, joka hyväksyy kaikki sanat (myös tyhjän sanan), joissa nollat ja ykköset vuorottelevat, eli muotoa 01, 0101, 010101, … olevat sanat.

Toinen automaatti A₂ hyväksyy sanat, joissa on ainakin yksi nolla:

Näiden kielten yhdisteeseen kuuluvat sanat, joissa on nolla tai jotka ovat muotoa 01, 0101, … Rakennamme nyt äärellisen automaatin A = (Q, Σ, δ, q, F), joka hyväksyy juuri tämän yhdistekielen. Näytämme ensin, miltä tämän uuden automaatin A tilat näyttävät. Ne ovat ensimmäisen ja toisen automaatin tilojen karteesinen tulo:

$Q = Q_{1} \times Q_{2} = {(q_{0}, p_{0}), (q_{0}, p_{1}), (q_{1}, p_{0}), (q_{1}, p_{1}), (q_{2}, p_{0}), (q_{2}, p_{1})}$

Nämä ovat kuusi tilaa automaatissa A, joka hyväksyy yhdistekielen L(A₁) ∪ L(A₂). Kaaviossa ne näyttäisivät tältä:

Älä säikähdä sitä, että tiloissa on tilaparit — se vain auttaa hahmottamaan, mitä automaatissa oikeastaan tapahtuu. Tilat voisivat aivan hyvin olla nimeltään tavallisesti q₀, …, q₅. Lopputilat ovat ne tilat, jotka sisältävät joko tilan q₀ tai tilan p₁, jotka ovat alkuperäisten automaattien lopputiloja. Alkutila on (q₀, p₀). Kaavioissa tilaparit on kirjoitettu kulmasulkeisiin, esimerkiksi ⟨ q₀, p₀⟩, mutta kyse on samasta parista (q₀, p₀).

Nyt meidän täytyy löytää kaikki siirtymät. Kirjoitamme tällaisen taulukon:

$\begin{array}{ccc} 0 & 1 \\ (q_{0}, p_{0}) \\ (q_{0}, p_{1}) \\ (q_{1}, p_{0}) \\ (q_{1}, p_{1}) \\ (q_{2}, p_{0}) \\ (q_{2}, p_{1}) \end{array}$

Ja täydennämme taulukkoa vähitellen. Ensimmäiseksi selvitämme, mihin johtaa siirtymä tilasta (q₀, p₀) syötteellä 0. Selvitämme, mihin johtaa siirtymä tilasta q₀ syötteellä 0 automaatissa A₁: se johtaa tilaan q₁. Automaatissa A₂ siirtymä tilasta p₀ nollalla johtaa tilaan p₁. Taulukkoon kirjoitamme siis (q₁, p₁):

$\begin{array}{ccc} 0 & 1 \\ (q_{0}, p_{0}) & (q_{1}, p_{1}) \\ (q_{0}, p_{1}) \\ (q_{1}, p_{0}) \\ (q_{1}, p_{1}) \\ (q_{2}, p_{0}) \\ (q_{2}, p_{1}) \end{array}$

Syötteellä 1 saamme: automaatille A₁ on δ₁(q₀, 1) = q₂ ja automaatille A₂ on δ₂(p₀, 1) = p₀. Saamme siis tilan (q₂, p₀).

$\begin{array}{ccc} 0 & 1 \\ (q_{0}, p_{0}) & (q_{1}, p_{1}) & (q_{2}, p_{0}) \\ (q_{0}, p_{1}) \\ (q_{1}, p_{0}) \\ (q_{1}, p_{1}) \\ (q_{2}, p_{0}) \\ (q_{2}, p_{1}) \end{array}$

Täydennämme taulukon loppuosan:

$\begin{array}{ccc} 0 & 1 \\ (q_{0}, p_{0}) & (q_{1}, p_{1}) & (q_{2}, p_{0}) \\ (q_{0}, p_{1}) & (q_{1}, p_{1}) & (q_{2}, p_{1}) \\ (q_{1}, p_{0}) & (q_{2}, p_{1}) & (q_{0}, p_{0}) \\ (q_{1}, p_{1}) & (q_{2}, p_{1}) & (q_{0}, p_{1}) \\ (q_{2}, p_{0}) & (q_{2}, p_{1}) & (q_{2}, p_{0}) \\ (q_{2}, p_{1}) & (q_{2}, p_{1}) & (q_{2}, p_{1}) \end{array}$

Ja tämän taulukon perusteella piirrämme enää kaavion loppuosan.

Voimme kokeilla, että automaatti toimii niin kuin pitää. Yritetään hyväksyä sana 0100. Automaatti käy läpi tilat

$(q_{0}, p_{0}), (q_{1}, p_{1}), (q_{0}, p_{1}), (q_{1}, p_{1}), (q_{2}, p_{1})$

Koska tila (q₂, p₁) on lopputila, automaatti A hyväksyy sanan 0100. Miten kävisi, jos yrittäisimme hyväksyä sanan 0100 automaateilla A₁ ja A₂? Automaatti A₁ kävisi läpi nämä tilat:

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

Automaatti päätyi tilaan q₂, joka ei ole lopputila, joten automaatti A₁ ei hyväksyisi tätä sanaa. Entä automaatti A₂?

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

Tila p₁ on lopputila, joten automaatti A₂ hyväksyisi sanan 0100. Huomaa, että automaatit A₁ ja A₂ päätyivät tiloihin q₂ ja p₁, mikä sopii yhteen sen kanssa, että automaatti A päätyi tilaan (q₂, p₁).

Menetelmä epädeterministisen automaatin avulla

Esimerkki

Sen, että säännöllisten kielten joukko on suljettu yhdisteen suhteen, voimme todistaa myös rakentamalla epädeterministisen automaatin, joka on paljon yksinkertaisempi.

Meillä on siis kaksi säännöllistä kieltä L₁, L₂, ja haluamme todistaa, että niiden yhdiste L = L₁ ∪ L₂ on myös säännöllinen kieli. Koska L₁, L₂ ovat säännöllisiä kieliä, täytyy olla olemassa automaatit A₁, A₂, jotka hyväksyvät nämä kielet. Eli pätee L(A₁) = L₁ ja L(A₂) = L₂. Näiden automaattien avulla rakennamme automaatin A, joka hyväksyy kielen L, eli L(A) = L.

Oletetaan, että äärelliset automaatit A₁ ja A₂ näyttävät tältä:

Automaatin, joka hyväksyisi molempien kielten yhdisteen, rakentaisimme luomalla uuden alkutilan ja viemällä tästä tilasta kaksi epsilon-siirtymää alkuperäisiin alkutiloihin. Siinä kaikki. Automaatti näyttäisi tältä:

Formalisointi

Meillä on kaksi automaattia A₁ = (Q₁, Σ, δ₁, q₁, F₁) ja A₂ = (Q₂, Σ, δ₂, q₂, F₂). Rakennamme automaatin A = (Q, Σ, δ, q₀, F), joka hyväksyy edellisten automaattien hyväksymien kielten yhdisteen, eli L(A) = L(A₁) ∪ L(A₂). Tällöin pätee:

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

Ja siirtymäfunktion δ määrittelemme näin:

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & jos & q \in Q_{1} \\ δ_{2} (q, a) & jos & q \in Q_{2} \\ {q_{1}, q_{2}} & jos & q = q_{0} \land a = ε \\ \emptyset & jos & q = q_{0} \land a \neq ε \end{cases}$

Lähteet

Luvut: Säännöllisten kielten sulkeumaominaisuudet, Säännöllisten kielten yhdiste, Säännöllisten kielten leikkaus, Säännöllisten kielten erotus, Säännöllisen kielen komplementti, Säännöllisten kielten konkatenaatio, Säännöllisen kielen Kleenen tähti

« Edellinen: Säännöllisten kielten sulkeumaominaisuudet

Seuraava: Säännöllisten kielten leikkaus »