Säännöllisten kielten konkatenaatio

Olkoon meillä kaksi säännöllistä kieltä L₁, L₂. Todistamme, että niiden konkatenaatio eli liittäminen L = L₁ ∘ L₂ on myös säännöllinen kieli.

Mikä konkatenaatio on

Kahden sanan ”010” ja ”1111” liittämisestä syntyy sana ”0101111”. Kielten liittämisestä syntyy uusi kieli, jonka rakennamme liittämällä jokaisen yhden kielen sanan jokaiseen toisen kielen sanaan. Kahden sanan ja kahden kielen konkatenaatiota merkitsemme rengasoperaattorilla: ∘. Silloin voimme määritellä kielten L₁ ja L₂ konkatenaation näin:

$$L_1\circ L_2=\{a\circ b|a\in L_1,b\in L_2\}$$

Todistuksen idea

Meillä on kaksi säännöllistä kieltä L₁, L₂ ja kaksi automaattia, jotka hyväksyvät nämä kielet:

$$\begin{array}{rcl}{A}_1& =& (Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1)\\ A_2& =& (Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2)\end{array}$$

Rakennamme epädeterministisen automaatin A = (Q, Σ, δ, q, F), joka ”sisältää itsessään” molemmat automaatit A₁ ja A₂. Perusidea on, että aloitamme sanan hyväksymisen automaatilla A₁, ja kun automaatti A₁ päätyy lopputilaan, yritämme hyväksyä sanan jäljellä olevan osan vielä automaatilla A₂. Jos tämäkin automaatti hyväksyy osan sanasta, automaatti A hyväksyy sanan.

Esimerkki

Olkoon meillä tämä automaatti A₁, joka hyväksyy epätyhjät sanat, jotka koostuvat pelkistä nollista, sekä sanat, jotka koostuvat ykkösestä ja sitä seuraavista pelkistä nollista (1, 10, 100, …):

ja olkoon meillä tämä automaatti A₂, joka hyväksyy sanat, jotka päättyvät merkkijonoon 01:

Yhdistämme automaatit niin, että lisäämme kaikista automaatin A₁ lopputiloista epsilon-siirtymät automaatin A₂ alkutilaan ja teemme sitten automaatin A₁ lopputiloista tavallisia tiloja. Koko uuden automaatin alkutila on automaatin A₁ alkutila:

Miten automaatti toimii? Aloitamme simuloimalla automaatin A₁ toimintaa. Jos siirrymme entiseen lopputilaan q₁ tai q₂, tiedämme, että automaatti A₁ hyväksyy tämän sanan osan. Jotta koko sana kuuluisi kieleen L₁ ∘ L₂, toisen automaatin A₂ täytyy vielä hyväksyä sanan jäljellä oleva osa — siksi kaikista entisistä lopputiloista johtavat epsilon-siirtymät automaatin A₂ alkuperäiseen alkutilaan.

Otetaan esimerkiksi sana 0001. Se kuuluu molempien kielten konkatenaatioon, koska sana voi syntyä liittämällä sanat 00 ∘ 01. Mutta yhtä hyvin se voi syntyä liittämällä sanat 0 ∘ 001. Automaatissamme voimme simuloida molemmat tavat. Automaatti voi edetä tätä reittiä:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

Tätä reittiä automaatti ”hyväksyisi” ensin sanan osan 00 ja sitten sanan osan 01. Tai se voi edetä tätä reittiä:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

jolloin automaatti ”hyväksyisi” ensin sanan osan 0 ja sitten sanan osan 001. Molemmissa tapauksissa päädymme tietenkin lopputilaan p₂.

Täsmällinen menetelmä

Vielä kerran: meillä on kaksi säännöllistä kieltä L₁, L₂ ja kaksi automaattia, jotka hyväksyvät nämä kielet:

$$\begin{array}{rcl}{A}_1& =& (Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1)\\ A_2& =& (Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2)\end{array}$$

Rakennamme epädeterministisen automaatin A = (Q, Σ, δ, q, F), jolle pätee:

• Q = Q₁ ∪ Q₂ (oletamme samalla, että Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Siirtymäfunktion δ rakennamme vaiheittain:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{jos}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{jos}& q\in F_1\wedge a\ne \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{jos}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{jos}& q\in Q_2\end{array}$$

Lähteet

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