...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
557 views
DFA yı burda öğrendim..sağolun hocam..aslında tüm kavramları burda öğrendim:D
hocam cok sagolun paylasimlariniz icin ama lütfen daha fazla bilgi paylasirmisiniz.
elbette, tam olarak nasıl bir bilgiye ihtiyacınız olduğunu yazarsanız elimden geleni yapmaya çalışırım.
hocam lambda geçişi hakkında biraz bilgi verebilir misiniz?
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
teşekkür ederim gayet anlaşılır bir dille anlatmışsınız.