Yazan : Şadi Evren ŞEKER

Sonlu otomatların özel bir halidir. Bu özel hal aşağıdaki 3 durumu içermelidir:

  1. Her durumdan (State) gidilecek koşulun tek bir durum göstermesi. Yani bir durumda başka duruma geçerken bir kelime ile sadece bir duruma gidilebilmesi
  2. Herhangi bir girdi için, tek bitiş durumunun (final state) kabul edilmesi (birden fazla bitiş durumunun aynı anda kabul edilmemesi)
  3. Lambda (veya epsilon) kelimesinin durumlar arası geçişte yer almaması

Örneğin aşağıdaki sonlu otomatı (aynı zamanda sonlu durum makinesi (finite state machine) de denilmektedir) inceleyelim:

Yukardaki otomatta, başlangıç soldan gelen ok ile gösterilmiş q1 ve bitiş çift halka içerisine alınmış durum (düğüm, node, state) ile gösterilmiş olan q2’dir.

Yukarıdaki otomatın özellikleri kontrol edildiğinde belirli sonlu otomat (deterministic finite automaton) olmasını gerektiren koşullar şöyledir:

1. adımdaki şartı sağlar çünkü herhangi bir durumda diğerine giderken belirsizlik söz konusu değildir. Örneğin q1 durumundayken 0 gelince tek bir yere (yine q1) ve 1 gelince tek bir yere (q2) gidilmektedir. Şayet herhangi birisi için birden fazla alternatif bulunsaydı bu durumda belirsiz sonlu otomat (nondeterministic finite automat, nfa) denilebilirdi.

2. adımdaki şartı da sağlamaktadır çünkü otomatta hiç lambda geçişi (boş geçiş) yoktur. bütün geçişler bir değerle (kelime) yapılmaktadır.

3. adımı da sağlamaktadır çünkü tek bitiş durumu söz konusudur (bu bitiş de q2 durumudur)

dolayısıyla yukarıdaki otomatın belirli (Deterministic) olduğu söylenebilir

Sonlu Durum Makinelerinin Gösterimi

Bazı kaynaklarda, sonlu durum makinelerinin ifadesi için, yukarıdaki yazıda yer alan görsel gösterimin yerine küme gösterimi veya tablo gösterimi de kullanılmaktadır.

Buna göre durum makinesinin geçişlerini ve durumlarını gösteren bir şekil tablo hazırlanabilir. Yukarıdaki makine için aşağıdaki tablo aynı makineyi tutmaktadır:

q1 q2 q3
q1 0 1
q2 1 0
q3 1,0

Yukarıdaki gösterime göre geçişlerin tutulduğu bir matris oluşmuştur. Bu matris, yönlü bir şekil (graph) için kullanılmasından mütevellit asimetrik yapıdadır.

Aynı sonlu durum makinesi aşağıdaki tablo ile de tutulabilir:

0 1
q1 q1 q2
q2 q3 q2
q3 q2 q2

Yukarıdaki yeni tabloda, kolon başlıkları gelen parametreyi (geçiş değerini) ve tablo içeriği de geçilecek olan durumu(state) tutmaktadır.

Bu tabloda da bir hücrede birden fazla durum(state) bulunması halinde NFA, her hücrede tek durum (state) bulunması halinde DFA yorumu yapılabilir.

Yukarıdaki tablo gösterimlerine ilave olarak küme halinde tutulabilir. En çok kullanılan yazım aşağıdaki şekildedir:

(Σ, S, S0 , δ , F )

Buna göre Σ sembolü bir alfabeyi (alphabet) ifade etmektedir. Yani dilimizde kabul edilen girdilerin her birisini gösteren küme. Örneğin yazı boyunca kullandığımız DFA için {0,1 }kümesidir denilebilir.

S kümesi, otomattaki durumların kümesidir. Yani örnek otomatımızda {q1,q2,q3} durumları bulunmaktadır

S0 ise başlangıç durumudur (state). Örnek otomatımızda q1 başlangıç durumudur.

δ kümesi ise geçişlerin tutulduğu kümedir. Örnek otomatımızda geçişler için şöyle bir küme yazabiliriz δ = { q1 -> q1, 0 ; q1 -> q2 ,1 ; q2 -> q3 , 0 ;q2 -> q2 ,1 ;q3->q2, 0; q3 -> q2, 1   } olarak yazılabilir.

F ise bitiş durumunu gösterir. Yani bir gidi (input) bu durumda bitiriyorsa kabul edilir (accept). Diğer durumlarda bitmesi veya gidilemeyen bir devam olması durumunda ise red edilir (reject). Örnek otomatımızda q2 bitiş durumudur.

Kısaca yukarıdaki özellikler tek bir kümeler kümesinde toplanırsa, aşağıdaki gibi bir gösterim ortaya çıkar:

{ {0,1 } ,  {q1,q2,q3} , q1 , { q1 -> q1, 0 ; q1 -> q2 ,1 ; q2 -> q3 , 0 ;q2 -> q2 ,1 ;q3->q2, 0; q3 -> q2, 1   } , q2 }

Yukarıdaki bu küme en başta çizilen durum makinesini göstermek için yeterlidir.

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    lambda geçişi, bir durumdan (state) farklı bir duruma boş olarak geçilmesi demektir. Bazı kaynaklarda lambda bazı kaynaklarda ise epsilon sembolü ile gösterilmektedir.

    Örneğin düzenli ifadelerde (regular expressions) kullanılan a* gösterimini ele alalım. Bu gösterimde çıkabilecek ihtimaller:
    boş
    a
    aa
    aaa
    aaaa

    şeklinde devam eden seridir. Bunun anlamı bu gösterimden hiçbir kelime çıkmayabilir, yani boş bir kelime veya 0 (sıfır) uzunluğudan bir kelime çıkabilir. İşte bu değerin FA (sonlu otomata, finite automata) ile gösterilmesini isterseniz lambda sembolü kullanılır.

    Mamafih, DFA (deterministic finite automata) yani belirli sonlu otomatlarda lambda gösterimine izin verilmez. Bütün geçişler belirli bir değer ile olmalıdır. Diğer bir deyişle bir kenarda (bir geçişte) lambda değeri varsa bu otomat belirsiz sonlu otomat (non deterministic finite automata NFA) olarak sınıflandırılır.

    Lambda geçişlerinden kurtulmak için NFA’den DFA’ye çevirim başlıklı yazıyı okuyabilirsiniz. Bağlatı aşağıdaki gibidir:

    http://www.bilgisayarkavramlari.com/2008/11/11/nfaden-dfae-cevirim-converting-nfa-to-dfa/

    Başarılar

  2. Şadi Evren ŞEKER Article Author

    Teorik olarak bir CFG, bir DFA olarak yazılamaz. Bu durumu aşağıdaki yazıdaki seviyelere bakarak görebilirsiniz.

    http://www.bilgisayarkavramlari.com/2009/06/27/chomsky-hiyerarsisi-chomsky-hierarchy/

    CFG gösterimi Tip 2 iken DFA ve RE gösterimleri Tip 3 olarak sınıflandırılmaktadır.

    Ancak bazı CFG gösterimleri, DFA olarak yazılabilir, yani aslında CFG ile yazılabilecek diller, DFA ile gösterilebilecek dilleri kapsamaktadır (üst küme, superset). Bu durumu analiz etmek için düzenli ifadelerde pompalama önsavı (pumping lemma for regular expressions) konusuna bakmanız gerekir:

    http://www.bilgisayarkavramlari.com/2009/03/22/duzenli-ifadelerde-pompalama-onsavi-pumping-lemma-for-regular-expressions/

    Şayet bir dil, düzeni ifade olarak yazılamıyorsa DFA olarak da gösterilemez.

  3. sinan

    Hocam burda bu konuyu küme şeklinde anlatmışsınız fakat bize sınavda farklı bir biçimde soruldu küme yoktu sadece düz bir çizgi üzerine verilmiş değerler nfa dan dfa yı istiyordu arada lambda işareti vardı 001 ya da 01 se şöyle oluyor gibi değişik birşeydi mantık aynı mıdır bu yukarıdaki anlattığınız konuyla

  4. sercan

    Sadi Bey anlatiminiza saglik onlarca sayfayi ozumsemek icin caba gosterdim 1-2 saattir keske sizin makalenizi daha evvel bulabilseydim. Yardimlariniz icin cok sagolun.

  5. bilgisay

    Sanırım site taşınırken dosyada hata oluşmuş, şu anda yurt dışındayım en kısa sürede konu ile ilgilenip dosyayı yeniden yükleyeceğim. ilginiz için teşekkürler

  6. Onur

    Hocam öncelikle teşekkür ediyorum bu faydalı siteniz için.Hocam acaba düzenli ifadesi (aUba*Uab*a) gibi verilen bir dilin DFA sını nasıl çizebiliriz

  7. Şadi Evren ŞEKER

    Merhaba,

    Sanırım bu sorunun doğrudan çözümü yerine genel bir çözüm yöntemi soruyorsunuz. Vermiş olduğunuz düzenli ifadede kullanılan birleşim sembolü ”U” veya bazı gösterimlerdeki veya sembolü ”|” DFA çizilirken bu ifadedeki her parçanın ayrı ayrı yerine getirilebileceğini işaret eder.
    Diğer bir deyişle, sizin verdiğiniz ifadeyi U sembollerinden parçalarsak, 3 farklı ifade çıkar:
    a
    ba*
    ab*a
    Ve sonuçta çıkacak olan otomat bunlardan herhangi birisini kabul edebilir. O halde 3 tane farklı düzenli ifadeyi ayrı ayrı çizip birbirine paralel olarak bağlayabiliriz.
    Bu gösterim, bir NFA’dir (non deterministic) bunun DFA çevrilmesi için ayrıca bir adım gerekir. Bu adım için de NFA’den DFA’e çevirme algoritmasına bakabilirsiniz:
    http://bilgisayarkavramlari.sadievrenseker.com/2008/11/11/nfaden-dfae-cevirim-converting-nfa-to-dfa/

  8. Hilal

    Hocam merhaba, DFA da her bir halkadan tüm durumlara gidiş olmak zorunda mı?

    Bu örnek için mesela, q2 den sadece 0 la gidip 1 le gitmeme durumu olabilir miydi? bir örneğim de bir durağımda tek bir duruma gidiş var, transition table ını çıkardığımda boş kalıyor. Boş kalamaz gibi bir şart var mıdır?

  9. Feramuz Kapucu

    İyi geceler hocam bir DFA ya da NFA için birden fazla başlangıç durumu olması mümkün müdür? İnternette araştırdım ama doyurucu bir cevap alamdım.Cevabınızı bekliyorum şimdiden teşekkürler.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir