Deterministik Olmayan Otomatın Benzetimi

Elimizde deterministik olmayan bir otomat varsa ve verilen sözcüğü kabul edip etmediğini öğrenmek istiyorsak otomatı deterministik otomata dönüştürebiliriz, bir şekilde deneyebiliriz ya da NSO’nun çalışmasını benzetecek bir algoritma kullanabiliriz.

Algoritmanın İlkesi

İlkeyi uygun bir örnek üzerinde gösterelim. Şu otomatı ele alalım:

Bu, bir dili kabul eden deterministik olmayan sonlu otomattır. Hangi dili kabul ettiği şu an hiç önemli değil. Böyle bir otomatın 11001 giriş sözcüğü için hesaplamasının nasıl görünebileceğini göstereceğiz. Mantık şöyle: sözcükten bir sembol işleriz ve aynı sembol için birden fazla geçiş olduğundan nerelere gidebileceğimize bakarız. Bu durumların hepsini aklımızda tutarız; sonraki adımda artık “bu durumların hepsinde aynı anda” olduğumuzu varsayarız ve bu durumlardan başka nerelere gidebileceğimizle ilgileniriz.

Böylece bulunabileceğimiz durumlar kümesini ve sözcüğün okunmamış kısmını aklımızda tutacağız. Başlangıçta elimizde ⟨{q₀}, 11001⟩ ikilisi var. q₀ durumunda (başlangıç durumu) başlarız ve girişte 11001 sözcüğü vardır. Otomat şöyle görünür; içinde bulunduğumuz durum kırmızı ve kalın olarak vurgulanmıştır:

İlk sembol 1’dir; q₀ durumundan 1 sembolü için yalnızca bir geçiş vardır, dolayısıyla q₁ durumuna geçeriz. ⟨{q₁}, 1001⟩ ikilisini aklımızda tutarız. Otomat şöyle görünür:

Devam edelim. Sözcüğün okunmamış kısmı 1001 olduğundan yine 1 için geçişleri ararız. Bu kez iki geçiş var — geri q₀ durumuna ve ayrıca q₃ durumuna. Şimdi iki duruma aynı anda gideriz. Böylece ⟨{q₀, q₃}, 001⟩ ikilisini aklımızda tutarız.

Bunun mantığı ne? Başlangıç durumundan 11 sözcüğüyle hem q₃ durumuna hem q₀ durumuna ulaşan bir yol olduğunu biliyoruz. Hangi dalın işimize yarayacağını henüz bilmiyoruz, o halde ikisini de aklımızda tutarız. Devam edelim. Girişte 0 sembolü var. Şimdi hem q₀ durumundan hem de q₃ durumundan çıkan geçişlere bakmalıyız. q₀ durumundan q₁ ve q₂ durumlarına geçişler çıkıyor, q₃ durumundan ise geri q₁ durumuna bir geçiş çıkıyor. Bu durumların hepsini hesaba katarız ve ⟨{q₁, q₂}, 01⟩ ikilisini elde ederiz:

Ama bu adımı henüz bitirmedik. q₂ durumundan q₄ durumuna bir ε-geçişi çıktığını görüyoruz. ε-geçişi üzerinden “istediğimiz zaman gidebileceğimizi”, yani bunun için sonraki karakteri okumamız gerekmediğini biliyoruz. Başka bir deyişle, giriş sözcüğünden bir sonraki sembolü okumadan q₄ durumuna da geçebiliriz. Bu yüzden q₄ durumunu da bulunabileceğimiz durumlara ekleriz: ⟨{q₁, q₂, q₄}, 01⟩. Otomatı şöyle renklendiririz:

Sonra girişte 0 var. Bulunduğumuz bu üç durumdan nereye geçebileceğimize bakarız. q₁ durumundan hiçbir yere geçemeyiz, çünkü 0 için geçiş yok. Bu daldaki hesaplama biter. q₄ durumundan da hiçbir yere gidemeyiz. q₂ durumundan yine q₂ durumuna geçebiliriz. Ama q₂ durumundan yine q₄ durumuna bir ε-geçişi çıktığı için q₄ durumuna da gidebiliriz. Böylece {q₁, q₂, q₄} durumlar kümesinden 0 sembolü için {q₂, q₄} durumlar kümesine gidebiliriz ve ⟨{q₂, q₄}, 1⟩ ikilisini elde ederiz:

Son olarak girişte 1 sembolü var. q₂ durumundan hiçbir yere gidemeyiz, bu daldaki hesaplama biter. Ama q₄ durumundan q₃ ve q₅ durumlarına gidebiliriz. ⟨{q₃, q₅}, ε⟩ ikilisini elde ederiz:

Otomat artık sözcüğün tamamını okudu ve iki durumda “bulunuyor”: q₃, q₅. Bunlardan en az biri kabul durumu olduğu için otomat 11001 sözcüğünü kabul eder.

Algoritma

İlk olarak, parametre olarak bir durumlar kümesi alan ve ε-geçişleriyle ayrıca hangi durumlara gidebileceğimizi hesaplayan bir fonksiyona ihtiyacımız var. Girdi, ⟨Q, Σ, δ, q₀, F⟩ otomatı ile States durumlar kümesidir; çıktı ise bu durumların, ε-geçişleriyle ulaşılabilen durumları da içeren üst kümesidir. Bu işleme States kümesinin ε-kapanışı diyeceğiz.

$\begin{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

Bu fonksiyonu, deterministik olmayan otomatın çalışmasını benzetecek fonksiyonda kullanacağız. Girdiler otomat, w = w₁w₂… w_n giriş sözcüğü ve otomatın o anda bulunduğu durumlar kümesidir. Çıktı, otomatın verilen sözcüğü kabul edip etmemesine göre Evet ya da Hayır yanıtıdır.

$\begin{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return EVET \\ Else \\ Return HAYIR \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

Otomatın w sözcüğünü kabul edip etmediğini denetlemek istiyorsak fonksiyonu şöyle çağırırız: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

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: Deterministik Olmayan Sonlu Otomat

Sonraki: NSO’dan DSO’ya Dönüştürme »