Deterministik Olmayan Sonlu Otomat

Önceki bölümlerde tanıttığımız sonlu otomat (kısaca SO ya da DSO) her zaman deterministikti; yani her an otomatın ne yapacağı belliydi. Şimdi daha genel bir kavrama, deterministik olmayan sonlu otomatlara (kısaca NSO) bakacağız. Bu otomatlarda aynı durumdan çıkan ve aynı sembol için tanımlı birden fazla geçiş bulunabilir.

Örnek

Şu otomat diyagramına bak:

Bu diyagramda ilginç olan ne? q₀ düğümünden 0 sembolü için iki ok çıkıyor. 001 sözcüğünü kabul ettirmeye çalışırsak otomat, q₀ durumunda mı kalacağını yoksa q₁ durumuna giden geçişi mi izleyeceğini bilemeyecek gibi görünür. Böyle bir otomat deterministik değildir.

Bu anlamda determinizm, her durumda otomatın ne yapacağının belli olması, belirsizliğe yer bırakılmaması demektir. Deterministik otomatta her durum ve her sembol için yalnızca bir geçiş vardır. Deterministik olmamak ise belirsizlik demektir — bir durumdan aynı sembol için örneğin üç geçiş çıkabilir.

Peki otomat nasıl karar verir? Deterministik olmayan otomat, mümkünse her zaman sözcüğü kabul etmeye götürecek geçişi seçer (buna bazen “tahmin eder” de deriz).

Otomata 001 sözcüğünü verirsek otomatın bu sözcükle başa çıkmak için şu seçenekleri vardır:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

Bunlara bir de sözcüğün tamamını okumadığı durumlar eklenir. Birincisinde otomat hep q₀ durumunda kalıyordu; geçiş kuralları buna izin verdiği için bu kesinlikle mümkündür. İkinci dalda ise başka durumlara geçmeyi göze aldı ve sonunda kabul durumu olan q₂ durumuna ulaştı. Bu dalda otomat sözcüğü kabul eder. Deterministik olmayan otomat, böyle bir dal varsa her zaman kendiliğinden sözcüğü kabul ettiği dalı seçer.

Bu “uygun” dalı kendiliğinden nasıl seçiyor? Şöyle düşünebiliriz: deterministik olmayan otomat tüm olası dalları dener ve sözcüğü kabul ettiği bir dal bulursa sözcüğü kabul eder. Tüm dalları nasıl dener? Çok basit: otomat, geçerli sembol için n ok çıkan bir durumdayken kendini n kez kopyalar ve her kopya farklı bir yoldan gider. Böylece tüm olasılıkları adım adım gezeriz.

Otomatın Hesaplamasının Ağaç Gösterimi

Önceki otomatı biraz değiştirelim:

Deterministik olmama durumu yine ilk durumda kalıyor. Önceki otomat 01 ile biten tüm sözcükleri kabul ediyordu. Bu değiştirilmiş otomat ise 01 alt sözcüğünü içeren tüm sözcükleri kabul eder. Yani örneğin 101 ya da 0101 sözcüğünü kabul eder. Hesaplamanın tüm dallarını bir ağaçla kolayca gösterebiliriz; örneğin 01010 sözcüğü için ağaç şöyle görünebilir:

Başta q₀ başlangıç durumundayız. Girişte 01010 sözcüğü var, okunmamış ilk karakter 0. q₀ durumundan 0 sembolü için iki geçiş çıkıyor; bunlar q₀ ve q₁ durumlarına gider. Ağaçta bu düğümün iki çocuğu olur: q₀ ve q₁. Sonra 1 sembolünü okuruz. Burada belirsizlik yok, q₀ ve q₂ durumlarına geçeriz. Sonra 0 karakterini okuruz; sol dalda yine belirsizlik ortaya çıkar ve hesaplamayı iki yeni dala böleriz. Birinde yine q₀ durumunda kalırız, diğerinde q₁ durumuna geçeriz. Böyle devam eder.

Toplam iki dalın kabul durumu olan q₂ durumunda bittiğine dikkat et. Otomatın verilen sözcüğü kabul edebileceği iki hesaplama dalı var. Yani bu otomat 01010 sözcüğünü kabul eder. Benzer bir ağacı 1000 sözcüğü için de çizmeyi deneyebiliriz.

Hesaplama ya q₀ durumunda kalır ya da q₁ durumuna geçer; ama oradan öteye gidecek yeri yoktur, çünkü girişte geriye yalnızca sıfırlar kalmıştır ve q₁ durumunda yalnızca 1 sembolü için geçiş vardır. Hesaplamanın hiçbir dalı kabul durumunda bitmez, dolayısıyla otomat 1000 sözcüğünü kabul etmez.

ε-Geçişleri

Deterministik olmayan otomatlarda ayrıca ε-geçişlerini de kullanabiliriz. Bunlar, girişte hangi sembol olursa olsun ve sözcükten hiçbir sembol okumadan yapabileceğimiz geçişlerdir. Boş sözcüğü, yalnızca birlerden oluşan tüm sözcükleri ve (10)ⁿ biçimindeki sözcükleri, yani 10, 1010, … sözcüklerini kabul eden deterministik olmayan bir otomatı nasıl yazabiliriz?

Otomatı iki “alt otomata” böldük. Üstteki yalnızca 1’lerden oluşan sözcükleri tanır, alttaki (10)ⁿ biçimindeki sözcüklerle ilgilenir. 111 sözcüğünü kabul ettirmeyi deneyelim. Otomat başlangıçta q₀ durumundadır ve girişte 111 sözcüğü vardır. ε-geçişleri olduğu için işine geldiği gibi q₁ ya da q₂ durumuna geçmeye karar verebilir. q₁ durumuna geçmenin işine geleceğini görüyoruz. Otomat oraya geçer. Üstelik girişte hâlâ 111 sözcüğü durmaktadır! Ancak bu andan sonra sözcükteki sembolleri okumaya ve q₁ durumundan yine q₁ durumuna geçmeye başlar; sözcüğün tamamını okuyunca sözcüğü kabul eder.

1010 sözcüğünü kabul ettirmeyi denersek otomat başta q₂ durumuna geçer, sembolleri de ancak buradan itibaren işler ve sözcüğü yine kabul eder.

1100 sözcüğü için otomat ne yaparsa yapsın, bu sözcüğü kabul etmesinin yolu yoktur.

ε-geçişleri ve determinizmin olmaması birçok işimizi kolaylaştırır; örneğin düzenli dillerin birleşiminin yine düzenli dil olduğunun kanıtı, ε-geçişleriyle deterministik sonlu otomatlar durumundakinden çok daha kolay yazılabilir. Bu kanıtta şu otomat örneklerimiz vardı

ayrıca bu iki dilin birleşimini kabul eden bir deterministik sonlu otomat kurmuştuk. ε-geçişleriyle böyle bir otomatı şöyle kurabiliriz:

Kısacası yeni bir başlangıç durumu ekleriz; bundan, asıl otomatların başlangıç durumlarına iki ε-geçişi çıkar ve iş biter. Otomat, sözcüğü kabul etmeyi hangi “alt otomatla” deneyeceğine deterministik olmayan biçimde kendisi karar verir.

Deterministik Olmayan Otomatın Tanımı

Deterministik ve deterministik olmayan sonlu otomat arasındaki farkı gördük, geriye bunu biçimlendirmek kaldı. Deterministik sonlu otomatı ⟨Q, Σ, δ, q₀, F⟩ beşlisi olarak tanımlamıştık; burada Q durumlar kümesi, Σ alfabe, δ geçiş fonksiyonu, q₀ başlangıç durumu ve F kabul durumları kümesidir. Deterministik olmayan otomatların tanımında değişen tek şey geçiş fonksiyonunun tanımıdır.

Deterministik sürümde δ(q, w) çağrısı yalnızca bir durum döndürebiliyordu; deterministik olmayan sürümde ise — bir sembol için birden fazla geçiş tanımlıysa — birden fazla durum döndürebilir. ε-geçişlerini de tanımlamamız gerektiğinden Σ ∪ {ε} kümesini Σ_ε ile gösterelim, yani Σ_ε = Σ ∪ {ε}. Böylece δ fonksiyonunu şöyle tanımlarız:

$δ : Q \times Σ_{ε} \to 2^{Q}$

Buradaki 2^Q, kuvvet kümesini, yani Q kümesinin tüm alt kümelerinin kümesini gösterir. Hesaplamanın biçimlendirilmesi sonlu otomatlardakine çok benzer. Otomatın konfigürasyonu yine bir ⟨q, w⟩ ∈ Q × Σ^∗ ikilisidir. Hesaplama adımı ↦, konfigürasyonlar kümesi üzerinde şöyle bir bağıntıdır:

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

ancak ve ancak q_j ∈ δ(q_i, w₀) ise. En büyük fark bu cümlede ortaya çıktı. Deterministik otomatlarda bu koşulu q_j = δ(q_i, w₀) olarak yazmıştık, çünkü δ fonksiyonu her zaman tek bir durum döndürüyordu. Geçiş fonksiyonunun deterministik olmayan sürümü bir durumlar kümesi döndürür, bu yüzden orada ∈ sembolü vardır. Bağıntının yansımalı ve geçişli kapanışını yine ↦ ^∗ ile göstereceğiz. Şu koşulu sağlayan bir q_f ∈ F varsa ve ancak o zaman otomatın w sözcüğünü kabul ettiğini söyleriz:

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

Kaynaklar

Bölümler: Sonlu Otomat, Tam Otomat, Deterministik Olmayan Sonlu Otomat, Deterministik Olmayan Otomatın Benzetimi, NSO’dan DSO’ya Dönüştürme

« Önceki: Tam Otomat

Sonraki: Deterministik Olmayan Otomatın Benzetimi »