Düzenli Dillerin Birleştirilmesi

İki düzenli dil L₁, L₂ olsun. Bunların birleştirilmesiyle (art arda eklenmesiyle) elde edilen L = L₁ ∘ L₂ dilinin de düzenli bir dil olduğunu ispatlayacağız.

Birleştirme Nedir?

“010” ve “1111” sözcüklerini birleştirirsek “0101111” sözcüğünü elde ederiz. Dilleri birleştirdiğimizde de yeni bir dil oluşur: birinci dilin her sözcüğünü ikinci dilin her sözcüğüyle birleştiririz. İki sözcüğün ve iki dilin birleştirilmesini küçük daire simgesiyle göstereceğiz: ∘. Buna göre L₁ ve L₂ dillerinin birleştirilmesini şöyle tanımlayabiliriz:

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

İspatın Fikri

İki düzenli dilimiz L₁, L₂ ve bu dilleri kabul eden iki otomatımız var:

$$\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}$$

A₁ ve A₂ otomatlarını “içinde barındıran” deterministik olmayan bir A = ⟨Q, Σ, δ, q, F⟩ otomatı kuracağız. Temel fikir şu: sözcüğü önce A₁ otomatıyla kabul etmeye başlarız; A₁ otomatı bir kabul durumuna ulaşınca sözcüğün geri kalan kısmını da A₂ otomatıyla kabul etmeyi deneriz. Bu otomat da sözcüğün o kısmını kabul ederse A otomatı sözcüğü kabul eder.

Örnek

Yalnızca sıfırlardan oluşan boş olmayan sözcükleri ve bir 1’den sonra yalnızca sıfırların geldiği sözcükleri (1, 10, 100, …) kabul eden A₁ otomatı şu olsun:

Bir de 01 ile biten sözcükleri kabul eden A₂ otomatı olsun:

Otomatları şöyle birleştiririz: A₁ otomatının tüm kabul durumlarından A₂ otomatının başlangıç durumuna ε-geçişleri ekleriz, sonra A₁ otomatının kabul durumlarını sıradan durumlara çeviririz. Yeni otomatın başlangıç durumu A₁ otomatının başlangıç durumu olur:

Otomat nasıl çalışır? Önce A₁ otomatının çalışmasının benzetimini yapmaya başlarız. Eski kabul durumlarından q₁ ya da q₂ durumuna geçersek A₁ otomatının sözcüğün bir kısmını kabul ettiğini biliriz. Sözcüğün tamamının L₁ ∘ L₂ diline ait olması için geri kalan kısmını da ikinci otomat A₂ kabul etmelidir; bu yüzden eski kabul durumlarının hepsinden A₂ otomatının eski başlangıç durumuna ε-geçişleri çıkar.

Örnek olarak 0001 sözcüğünü alalım. Bu sözcük iki dilin birleştirilmesine aittir, çünkü 00 ∘ 01 sözcüklerinin birleştirilmesiyle oluşabilir. Ama aynı şekilde 0 ∘ 001 sözcüklerinin birleştirilmesiyle de oluşabilir. Bizim otomatımızda iki yolun da benzetimini yapabiliriz. Otomat şu yolu izleyebilir:

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

Bu yolda otomat önce sözcüğün 00 kısmını, sonra 01 kısmını “kabul eder”. Ya da şu yolu izleyebilir:

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

ve böylece önce sözcüğün 0 kısmını, sonra 001 kısmını “kabul eder”. Her iki durumda da elbette p₂ kabul durumuna ulaşırız.

Biçimsel Yöntem

Bir kez daha: iki düzenli dilimiz L₁, L₂ ve bu dilleri kabul eden iki otomatımız var:

$$\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}$$

Aşağıdaki koşulları sağlayan deterministik olmayan bir A = ⟨Q, Σ, δ, q, F⟩ otomatı kuruyoruz:

• Q = Q₁ ∪ Q₂ (ayrıca Q₁ ∩ Q₂ = ∅ olduğunu varsayıyoruz)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Geçiş fonksiyonu δ’yı adım adım oluştururuz:

$$\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 \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{eğer}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{eğer}& q\in Q_2\end{array}$$

Kaynaklar

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