Düzenli Dilin Kleene Kapanışı

L düzenli bir dil olsun. L dilinin Kleene kapanışının da düzenli bir dil olduğunu ispatlayacağız.

Dilin Kleene Kapanışı Nedir?

L dilinin Kleene kapanışını L^∗ ile gösteririz. Kleene kapanışı, L dilinden sonlu sayıda sözcüğün birleştirilmesiyle elde edilebilen tüm sözcükleri içerir. Kleene kapanışını şöyle tanımlayabiliriz:

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

burada ∘ birleştirme işlemini gösterir. Kleene kapanışı boş sözcüğü, yani ϵ’u da içerir.

Biçimsel Yöntem

Dillerin birleştirilmesindekine çok benzer şekilde ilerleyeceğiz. Yalnızca iki farklı otomatı birbirine bağlamak yerine tek bir otomatı kendisine bağlarız: otomatın kabul durumlarından başlangıç durumuna ε-geçişleri çizeriz. Ancak Kleene kapanışı boş sözcüğü de içermelidir. Bunu nasıl sağlarız? Başlangıç durumunu kabul durumu yapabiliriz. O zaman böyle bir otomat boş sözcüğü kabul ederdi, ama başka sözcükleri de kabul edebilirdi. Bu yüzden onun yerine yeni bir başlangıç durumu ekleriz ve bu yeni başlangıç durumundan eski başlangıç durumuna bir ε-geçişi çizeriz.

L₁ düzenli bir dil ve onu kabul eden otomat şu olsun:

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

Şu koşulları sağlayan deterministik olmayan A = ⟨Q, Σ, δ, q_s, F⟩ otomatını kurarız:

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

Geçiş fonksiyonu δ’yı şöyle tanımlarız:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{eğer}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{eğer}& q\in F_1\wedge a\ne ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{eğer}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{eğer}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{eğer}& q=q_s\wedge a\ne ϵ\end{array}$$

Örnek

00 veya 11 sözcüklerini kabul eden A₁ otomatını ele alalım:

L(A₁) dilinin Kleene kapanışı, 00 ve 11 çiftlerinden oluşan tüm sözcüklerin dilidir; örneğin 0000, 110011, 11110000 vb. Bu kapanışı kabul eden otomatı şöyle kurarız: eski başlangıç durumu q₀’a ε-geçişi olan yeni bir başlangıç durumu q_s ekleriz ve q₃ ile q₄ durumlarından q₀ durumuna ε-geçişleri ekleriz:

Bu otomatın 0000, 110011, 11110000 sözcüklerini gerçekten kabul ettiğini, ama örneğin 1010 sözcüğünü kabul etmediğini doğrulayabiliriz.