Säännöllisen kielen Kleenen tähti

Meillä on säännöllinen kieli L. Todistamme, että kielen L Kleenen tähti on jälleen säännöllinen kieli.

Mikä kielen Kleenen tähti on

Kielen L Kleenen tähteä (kielen sulkeumaa) merkitään L^∗. Se sisältää kaikki sanat, jotka voi koota liittämällä yhteen äärellisen määrän kielen L sanoja. Sen voi määritellä näin:

$$L^{\ast }=\{a_1\circ a_2\circ \cdots \circ a_n|a_i\in L,n\in \mathbb{N}\},$$

jossa ∘ tarkoittaa konkatenaatio-operaatiota. Kleenen tähti sisältää myös tyhjän sanan, eli ϵ.

Täsmällinen menetelmä

Etenemme hyvin samankaltaisesti kuin kielten konkatenaation tapauksessa. Sen sijaan, että yhdistäisimme kaksi eri automaattia, yhdistämme yhden automaatin itsensä kanssa — automaatin lopputiloista johdamme siis epsilon-siirtymät automaatin alkutilaan. Kleenen tähden täytyy kuitenkin sisältää myös tyhjä sana. Miten sen saa aikaan? Voimme tehdä alkutilasta lopputilan. Silloin tällainen automaatti hyväksyisi tyhjän sanan, mutta se saattaisi hyväksyä myös jonkin muun sanan. Siksi luomme sen sijaan uuden alkutilan ja johdamme tästä uudesta alkutilasta epsilon-siirtymän alkuperäiseen alkutilaan.

Meillä on säännöllinen kieli L₁ ja automaatti, joka hyväksyy tämän kielen:

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

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

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

Siirtymäfunktion δ määrittelemme näin:

$$\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 ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{jos}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{jos}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{jos}& q=q_s\wedge a\ne ϵ\end{array}$$

Esimerkki

Olkoon meillä tämä automaatti A₁, joka hyväksyy sanat 00 tai 11:

Kielen L(A₁) Kleenen tähti on siis kieli, jonka muodostavat kaikki sanat, jotka koostuvat pareista 00 ja 11, esimerkiksi 0000, 110011, 11110000 jne. Tämän Kleenen tähden hyväksyvän automaatin rakentaisimme luomalla uuden alkutilan q_s, josta on epsilon-siirtymä entiseen alkutilaan q₀, ja lisäämällä epsilon-siirtymät tiloista q₃ ja q₄ tilaan q₀:

Voimme tarkistaa, että tämä automaatti todella hyväksyy sanat 0000, 110011, 11110000, mutta ei hyväksy esimerkiksi sanaa 1010.

Lähteet

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