Düzenli Dillerin Birleşimi

İki düzenli dil L₁, L₂ olsun. Bunların birleşimi olan L = L₁ ∪ L₂ dilinin de düzenli bir dil olduğunu ispatlayacağız.

Deterministik Otomatla Yöntem

Yöntemin Fikri

İki düzenli dilimiz L₁ ve L₂ var ve birleşimleri olan L₁ ∪ L₂ dilinin yine düzenli bir dil olduğunu ispatlamak istiyoruz. L₁ ve L₂ düzenli diller olduğu için L₁ ve L₂ dillerini kabul eden sonlu otomatlar A₁ ve A₂ vardır, yani L(A₁) = L₁ ve L(A₂) = L₂ olur. Biz de L₁ ∪ L₂ dilini kabul eden bir sonlu otomat A kuracağız; böylece L₁ ∪ L₂ dilinin düzenli olduğunu göstermiş olacağız.

Bunu nasıl yapacağız? Elimizde dilleri ayrı ayrı kabul eden A₁ ve A₂ sonlu otomatları var. Bir w sözcüğü ancak ve ancak A₁ ve A₂ otomatlarından en az biri onu kabul ediyorsa L₁ ∪ L₂ diline aittir.

A otomatı şöyle çalışabilir: w girişi için önce A₁ otomatının w girişindeki hesaplamasını benzetir. A₁ otomatı w sözcüğünü kabul ederse A otomatı da w sözcüğünü kabul eder. A₁ otomatı w sözcüğünü reddederse A otomatı bir de A₂ otomatının w girişindeki hesaplamasını benzetmeyi dener. A₂ otomatı w sözcüğünü kabul ederse A otomatı da w sözcüğünü kabul eder. Aksi hâlde reddeder.

Geriye, A otomatının başka bir otomatın hesaplamasını “benzetmesinin” ne demek olduğunu biçimselleştirmek kalıyor.

Biçimsel Anlatım

L₁ ve L₂ düzenli dillerini kabul eden sonlu otomatlar şunlar olsun:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_1,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,q_2,F_2⟩.\end{array}$$

L = L₁ ∪ L₂ dilini kabul eden A = ⟨Q, Σ, δ, q, F⟩ sonlu otomatını kuruyoruz. A₁, A₂ otomatlarını benzetme fikrinden yararlanacağız. Giriş olarak w = w₁w₂… w_n sözcüğü verildiğini düşünelim; şimdi A₁ ve A₂ otomatlarının w sözcüğündeki işleyişini aynı anda benzeteceğiz. A₁ otomatının başlangıç konfigürasyonu ⟨q₁, w₁w₂… w_n⟩, A₂ otomatının başlangıç konfigürasyonu ⟨q₂, w₁w₂… w_n⟩ olur. Her otomatta şimdi bir hesaplama adımı yaparız; böylece ⟨δ₁(q₁, w₁), w₂… w_n⟩ ve ⟨δ₂(q₂, w₁), w₂… w_n⟩ konfigürasyonlarına geliriz.

Bu konfigürasyonların yalnızca ilk bileşenlerinin farklı olduğunu görüyoruz; ikinci bileşen — sözcüğün henüz okunmamış kısmı — her zaman aynıdır. Bu yüzden benzetim sırasında iki otomatın iki konfigürasyonunu tutmamıza gerek yok, ⟨⟨q_i, q_j⟩, w_l… w_n⟩ biçiminde tek bir konfigürasyon yeter; burada q_i ∈ Q₁ ve q_j ∈ Q₂ olur. Başka bir deyişle, kurduğumuz A otomatının başlangıç konfigürasyonu ⟨⟨q₁, q₂⟩, w⟩ olacak. ⟨q₁, q₂⟩ ikilisinin ilk bileşeni A₁ otomatının şu anda bulunduğu durumu, ikinci bileşeni A₂ otomatının şu anki durumunu gösterir.

Böylece kurduğumuz A otomatının durumlar kümesinin Q = Q₁ × Q₂ olduğunu yazabiliriz. Bu, önceki iki otomatın durumlarının kartezyen çarpımıdır. Fikir şöyle devam eder: A otomatının başlangıç durumu ⟨q₁, q₂⟩ olacak ve A₁ otomatı w₁ sembolüyle q_i durumuna, A₂ otomatı w₁ sembolüyle q_j durumuna geçiyorsa, A otomatı w₁ sembolüyle ⟨q_i, q_j⟩ durumuna geçecek.

Geçiş fonksiyonu δ’yı şöyle yazarız (burada artık q_i ve q_j durumlarında bulunduğumuzu varsayıyoruz):

$$\delta (⟨q_i,q_j⟩,w)=⟨{\delta }_1(q_i,w),{\delta }_2(q_j,w)⟩$$

Geriye yalnızca birkaç ayrıntı kalıyor. Alfabe için Σ= Σ₁ ∪ Σ₂ geçerlidir. Başlangıç durumu q = ⟨q₁, q₂⟩ durumudur. Kabul durumları ise, q_i ∈ F₁ ya da q_j ∈ F₂ olacak biçimdeki tüm ⟨q_i, q_j⟩ ikilileridir.

Yöntemin Örnek Üzerinde Gösterimi

İki otomatımız olsun. Birincisi, sıfırlarla birlerin dönüşümlü olarak geldiği tüm sözcükleri (boş sözcük dahil) kabul eden A₁ otomatıdır; yani 01, 0101, 010101, … biçimindeki sözcükleri:

Diğer otomat A₂, en az bir sıfır içeren sözcükleri kabul eder:

Bu dillerin birleşimi, ya sıfır içeren ya da 01, 0101, … biçiminde olan sözcüklerdir. Şimdi tam olarak bu birleşim dilini kabul eden A = ⟨Q, Σ, δ, q, F⟩ sonlu otomatını kuralım. Önce, yeni A otomatının durumlarının nasıl görüneceğini gösterelim. Bunlar birinci ve ikinci otomatın durumlarının kartezyen çarpımı olacak:

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

L(A₁) ∪ L(A₂) birleşim dilini kabul eden A otomatının altı durumu böyle görünür. Diyagramda şöyle olurlar:

Durumların durum ikililerinden oluşmasına hiç şaşırma — bu yalnızca otomatın içinde ne olup bittiğini daha iyi görmemizi sağlar. Durumlara rahatlıkla klasik biçimde q₀, …, q₅ de diyebilirdik. Kabul durumları, ya q₀ ya da p₁ durumunu içeren durumlardır; bunlar özgün otomatların kabul durumlarıdır. Başlangıç durumu ⟨q₀, p₀⟩ durumudur.

Şimdi tüm geçişleri bulmalıyız. Şöyle bir tablo yazalım:

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

Tabloyu adım adım dolduracağız. Önce ⟨q₀, p₀⟩ durumundan 0 girişiyle nereye geçiş olduğunu bulalım. A₁ otomatında q₀ durumundan 0 girişiyle nereye geçildiğine bakarız: q₁ durumuna. A₂ otomatında p₀ durumundan sıfırla p₁ durumuna geçilir. Bu yüzden tabloya ⟨q₁, p₁⟩ yazarız:

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

1 girişi için A₁ otomatında δ₁(q₀, 1) = q₂, A₂ otomatında δ₂(p₀, 1) = p₀ olur. Böylece ⟨q₂, p₀⟩ durumunu elde ederiz.

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

Tablonun geri kalanını dolduralım:

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

Bu tabloya göre diyagramın geri kalanını da çizebiliriz.

Otomatın istediğimiz gibi çalışıp çalışmadığını deneyebiliriz. 0100 sözcüğünü kabul ettirmeyi deneyelim. Otomat sırayla şu durumlardan geçer:

$$⟨q_0,p_0⟩,⟨q_1,p_1⟩,⟨q_0,p_1⟩,⟨q_1,p_1⟩,⟨q_2,p_1⟩$$

⟨q₂, p₁⟩ durumu bir kabul durumu olduğu için A otomatı 0100 sözcüğünü kabul eder. Peki 0100 sözcüğünü A₁ ve A₂ otomatlarıyla kabul ettirmeyi denesek ne olurdu? A₁ otomatı sırayla şu durumlardan geçerdi:

$$q_0,q_1,q_0,q_1,q_2$$

Otomat, kabul durumu olmayan q₂ durumunda bitti; yani A₁ otomatı bu sözcüğü kabul etmezdi. A₂ otomatı ne yapar?

$$p_0,p_1,p_1,p_1,p_1$$

p₁ bir kabul durumudur, yani A₂ otomatı 0100 sözcüğünü kabul ederdi. A₁ ve A₂ otomatlarının q₂ ve p₁ durumlarında bitmesinin, A otomatının ⟨q₂, p₁⟩ durumunda bitmesiyle uyumlu olduğuna dikkat et.

Deterministik Olmayan Otomatla Yöntem

Örnek

Düzenli diller kümesinin birleşim altında kapalı olduğunu, çok daha basit bir deterministik olmayan otomat kurarak da ispatlayabiliriz.

İki düzenli dilimiz L₁, L₂ var ve birleşimleri olan L = L₁ ∪ L₂ dilinin de düzenli bir dil olduğunu ispatlamak istiyoruz. L₁, L₂ düzenli diller olduğundan bu dilleri kabul eden A₁, A₂ otomatları vardır; yani L(A₁) = L₁ ve L(A₂) = L₂. Bu otomatları kullanarak L dilini kabul eden, yani L(A) = L olan bir A otomatı kuracağız.

A₁ ve A₂ sonlu otomatlarının şöyle göründüğünü varsayalım:

ve

İki dilin birleşimini kabul eden otomatı şöyle kurarız: yeni bir başlangıç durumu oluştururuz ve bu durumdan özgün başlangıç durumlarına iki ε-geçişi çizeriz. Hepsi bu kadar. Otomat şöyle görünür:

Biçimsel Anlatım

A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ ve A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩ otomatları olsun. Önceki otomatların kabul ettiği dillerin birleşimini kabul eden A = ⟨Q, Σ, δ, q₀, F⟩ otomatını kuruyoruz; yani L(A) = L(A₁) ∪ L(A₂). Şunlar geçerlidir:

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

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\\ {\delta }_2(q,a)& \text{eğer}& q\in Q_2\\ \{q_1,q_2\}& \text{eğer}& q=q_0\wedge a=\epsilon \\ \mathrm{\varnothing }& \text{eğer}& q=q_0\wedge a\ne \epsilon \end{array}$$

Kaynaklar

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