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

Deterministik olmayan bir sonlu otomatı (NSO) deterministik sonlu otomata (DSO) nasıl dönüştüreceğimizi göstereceğiz; böylece deterministik olmayan otomatların hesaplama gücünün deterministik otomatlarınkine denk olduğunu kanıtlayacağız.

Temel Fikir

ε-geçişi olmayan ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ deterministik olmayan otomat verilsin. Şu koşullarla ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ deterministik otomatı kurarız:

• Q_D ⊆ 2^Q_N
• Σ_D = Σ_N
• p₀ = {q₀}
• F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

δ_D geçiş fonksiyonunu şöyle tanımlarız:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\Sigma }}_D:{\delta }_D(Q,a)=\bigcup _{q\in Q}{\delta }_N(q,a)$$

Bu ne demek? Deterministik olmayan otomat aynı anda birden fazla durumda olabilir; örneğin deterministik olmayan otomatımızın {q₀, q₁} durumlarında bulunduğu bir duruma gelebiliriz. Sonraki sembolü, örneğin 1’i okuyunca {q₀, q₂, q₃} durumlar kümesine geçebiliriz. Aynı otomatın deterministik sürümünde bu şöyle görünür: iki durum oluştururuz, bunları {q₀, q₁} ve {q₀, q₂, q₃} diye adlandırırız ve aralarına 1 sembolü için bir geçiş koyarız. Biçimsel olarak bir durumdan diğerine geçmiş oluruz, ama adlandırma sayesinde deterministik olmayan otomatta sırasıyla iki ya da üç durumda bulunacağımızı biliriz.

Örnek

Şu deterministik olmayan otomatı ele alalım:

Deterministik otomatı kurmak için her şeyden önce yeni geçiş fonksiyonunu kurmamız gerekir. Bu konuda tüm geçişleri yazacağımız bir tablo bize yardımcı olur. Tablo başlangıçta şöyle görünür:

$$\begin{array}{ccc}\text{durum}/\text{sembol}& 0& 1\\ \left\{q_0\right\}\end{array}$$

Algoritmanın sonunda sol sütunda deterministik otomatın tüm durumları bulunacak. Doldurulmuş tablo da geçiş fonksiyonunu belirleyecek. Şimdi tabloya, {q₀} durumundayken ve girişte 0 ve 1 sembolleri varken hangi durumlara geçtiğimizi yazarız.

$$\begin{array}{ccc}\text{durum}/\text{sembol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

q₀ durumundan 0 sembolü için yalnızca q₁ durumuna geçiş var; 1 sembolü için ise q₁ ve q₂ durumlarına geçiş var. Şimdi tabloya iki yeni durum ekleyelim: {q₁} ve {q₁, q₂}. Neden? Tabloya sol sütunda henüz bulunmayan bir durumlar kümesi yazdığımız anda bu durumlar kümesini oraya da ekleriz.

$$\begin{array}{ccc}\text{durum}/\text{sembol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

ve yine dolduralım. {q₁, q₂} durumunda iki durumu da denetlemeyi unutmamalıyız; yani q₁ durumundan nereye gittiğimizin, q₂ durumundan nereye gittiğimizle birleşimini almalıyız.

$$\begin{array}{ccc}\text{durum}/\text{sembol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

Tabloya eklememiz gereken birkaç yeni durum elde ettik:

$$\begin{array}{ccc}\text{durum}/\text{sembol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}\\ \{q_0,q_3\}\end{array}$$

…ve geçişleri yine dolduralım:

$$\begin{array}{ccc}\text{durum}/\text{sembol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

{q₀, q₁, q₃}, {q₁} ve {q₁,q₂} durumları tabloda zaten var, bu yüzden yalnızca {q₀,q₁,q₂,q₃} durumunu ekleriz.

$$\begin{array}{ccc}\text{durum}/\text{sembol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

Artık yeni durum eklemedik, yani tablo doldurulmuş oldu. Şimdi geriye yalnızca diyagramı çizmek kalıyor. Deterministik otomatın durumları ilk sütundadır, 0 ve 1 sembolleri için geçişler sonraki sütunlardadır. Asıl otomattaki kabul durumlarından birini içeren her durum, bu otomatta da kabul durumu olur. Yani q₃ durumunu içeren her durum kabul durumu olacaktır. Otomat şöyle görünecek:

Otomatın gerçekten doğru çalıştığını gösterebiliriz. 11001 sözcüğünü kabul ettirmeyi deneyelim. Deterministik otomatta şu yoldan gideriz

$$q_0{\to }^1{q}_1,q_2{\to }^1{q}_0,q_3{\to }^0{q}_1{\to }^0{q}_0,q_1,q_3{\to }^1{q}_0,q_1,q_2,q_3$$

ve son durum {q₀, q₁, q₂, q₃} kabul durumu olduğundan otomat sözcüğü kabul eder. Deterministik olmayan otomatta benzetim sırasında aynı durumlara ulaşırdık; yani q₀ durumunda başlardık ve 1 sembolü için {q₁, q₂} durumlarına geçerdik. Sonraki 1 sembolü bizi {q₀,q₃} durumlarına götürürdü ve sonraki durumlar için de böyle devam ederdi. Sonunda {q₀, q₁, q₂, q₃} durumlarının hepsinde bulunurduk ve otomat sözcüğü kabul ederdi.

Kaynaklar

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