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:

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

« Bilgisayar Mühendisliği | Belirsiz Sonlu Otomat (Nondeterministic Finite Automat, NFA) »

Yorumlar

Giriş yaparak yorum yazabilirsiniz.

Bu Yazı Hakkında

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 114 defa okunmuştur.

Benzer yazıları Automata (otomatlar), 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.