• Bağış
  • Belirli Sonlu Otomat (Deterministic Finite Automat, DFA)

    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. Tek bitiş durumunun bulunması (final state)
    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

    Benzer Yazılar:

    Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Belirli Sonlu Otomat (Deterministic Finite Automat, DFA)' isimli yazı 11 Nov 2008 tarihinde, saat: 00:49 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1801 defa okunmuştur.

    Benzer yazıları Automata (otomatlar, özdevinirler), Derleyiciler kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.


    Category: Automata (otomatlar, özdevinirler), Derleyiciler
    1 response to “Belirli Sonlu Otomat (Deterministic Finite Automat, DFA)”
    1. tarık says:

      DFA yı burda öğrendim..sağolun hocam..aslında tüm kavramları burda öğrendim:D

    Leave a Reply