Otomatın En Küçük Hâle Getirilmesi

Otomatın en küçük hâle getirilmesi, durum sayısı mümkün olan en az olan denk bir otomat bulmak demektir. Gereksiz durumu olmayan bir otomat bile daha da sadeleştirilebilir.

Örnek

Şu otomatı ele alalım:

Otomat yalnızca 01 ve 11 sözcüklerini kabul ediyor. Aynı dili kabul eden, üç durumlu daha basit bir otomatın bulunduğu açık. q₁ ve q₂ durumları, yeni bir {q₁, q₂} durumunda birleştirilebilir; q₁ ya da q₂ durumlarına giden geçişler yeni duruma gider, q₁ ve q₂ durumlarından çıkan geçişler için de aynısı geçerlidir. Şu otomatı elde ederiz:

Bu otomat, bir öncekiyle aynı dili kabul ediyor ve üstelik daha az durumu var.

Durumların Denkliği

A = ⟨Q, Σ, δ, q₀, F⟩ bir otomat olsun. q ∈ Q durumunun dilini tanımlayalım ve L(q) ile gösterelim:

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Yani A otomatının başlangıç durumunu q₀ yerine q yaparız ve bu otomatın kabul ettiği dili buluruz. Başka bir deyişle, L(q) dili, A otomatında q durumundan w sözcüğüyle otomatın bir kabul durumuna ulaşılan tüm w sözcüklerinden oluşur. Önceki otomata dönersek L(q₁) = {1} olur.

İki farklı q₁ ve q₂ durumu için şu geçerliyse bunlara denk diyoruz:

$L (q_{1}) = L (q_{2})$

Bu ne demek? q₁, q₂ durumları denkse ve bunları otomatın başlangıç durumu yaparsak aynı dili üretirler. Başka bir deyişle, otomat ⟨q₁, w⟩ ve ⟨q₂, w⟩ konfigürasyonlarına gelirse, ya her iki hâlde de kabul etmeli ya da her iki hâlde de reddetmelidir.

Önceki otomata dönelim: q₁ ve q₂ durumları denktir, çünkü q₁ durumundayken giriş sözcüğünü ancak sözcüğün okunmamış kısmı 1’e eşitse kabul edebiliriz. q₂ durumundayken de aynısı geçerlidir.

Otomatı en küçük hâle getirirken amaç, denk durumları bulmak ve bunları yukarıdaki örnekte yaptığımız gibi tek bir yeni durumda birleştirerek ortadan kaldırmaktır.

Denk Durumlar Nasıl Bulunur

Hangi durumlar kesinlikle denk olmaz? Bir kabul durumuyla kabul durumu olmayan bir durumu alırsak bunlar kesinlikle denk değildir, çünkü kabul durumunun dili kabul durumu olmayanın dilinden farklıdır — kabul durumu ε sözcüğünü kesinlikle kabul eder, kabul durumu olmayan ise etmez. Yöntemi hemen bir örnek üzerinde gösterelim. Şu otomatımız olsun:

İki durum kümesi oluşturarak başlarız:

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Şimdi bir geçiş tablosu oluşturalım ve S₁ ile S₂ gruplarının bilgisini koruyalım:

$\begin{array}{ccccc} grup & durum & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Şimdi tabloyu şöyle düzenleriz: verilen sembolle hangi durumlara gidildiğini doğrudan yazmak yerine yalnızca geçtiğimiz grubu not ederiz. Örneğin q₃ durumundan 0 sembolüyle S₂ grubundaki q₅ durumuna gideriz. Tabloya q₅ yerine S₂ yazarız:

$\begin{array}{ccccc} grup & durum & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Şimdi her iki grubu da daha fazla bölelim. Tüm semboller için aynı gruplara geçen durumları her zaman aynı gruba koyarız. Örneğin q₃ ve q₆ durumları aynı grupta olmaz, çünkü ne 0 ne de 1 ile aynı gruba giderler. Buna karşılık q₁ ve q₂ durumları aynı grupta olur, çünkü her iki durumun da 0 için geçişi yoktur ve her ikisi de 1 için S₁ grubuna gider. Böylece yeni gruplar oluştururuz:

$\begin{array}{ccccc} grup & durum & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Her grupta geçişler aynıdır. Yeni oluşan grupları adlandırır ve durumların bu yeni gruplardan hangisine gittiğini yeniden belirleriz:

$\begin{array}{ccccc} grup & durum & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

Bu noktada grupları bir kez daha bölmeyi deneriz. Ancak artık başka bölme yapamayacağımızı görürüz, aynı grupları elde ederdik — çünkü q₁ ve q₂ durumlarının grupların içindeki geçişleri aynıdır, ama zaten aynı gruptadırlar ve S₄ grubunda başka durum yoktur. Denk durumları bulma algoritması sona erdi. Her gruptan bir durum seçmemiz yeter, diğerlerini sileriz ve silinen durumlara giden tüm geçişler seçtiğimiz o tek duruma gider.

Böylece yeni otomatın durumlarının q₃, q₆, q₀, q₁, q₄ olmasını seçebiliriz; q₂ ve q₅ durumlarını çıkarırız. q₂ durumuna giden tüm geçişler artık q₁ durumuna, q₅ durumuna giden tüm geçişler ise q₄ durumuna gider:

Otomatı En Küçük Hâle Getirme Adımları

Ulaşılamayan durumları çıkarırız,
gereksiz durumları çıkarırız,
denk durumları çıkarırız.

Kaynaklar

Bölümler: Ulaşılamayan Durumlar, Gereksiz Durumlar, Otomatın En Küçük Hâle Getirilmesi

« Önceki: Gereksiz Durumlar

Sonraki: Düzenli dillerin kapalılık özellikleri »