Yazan : Şadi Evren ŞEKER
DFA (deterministic finite automat) belirli sonlu otomatların (özdevinirlerin) tersine her durumdan gidişin karışık olduğu ve her durum için bir sonraki kelimede nereye gidileceğinin belirli olmadığı otomatlardır.
Basitçe DFA kurallarına uymayan bütün otomatlar NFA olarak adlandırılabilir.
Aşağıda bir örnek üzerinde durumu incleyelim:
yukarıdaki örnekte belirsiz durumlar bulunmaktadır. Örneğin b durumunda iken 1 kelimesi ile hem f durumuna hem de yine b durumuna gitmek mümkündür. Veya e durumundaki ike 1 kelimesi ile f veya a durumlarına geçmek de mümkündür. Bu belirsizlik yüzünden NFA’in bilgisayarlar tarafından algılanması ve kullanılması zor olmaktadır. Ancak insanlar tarafından NFA daha kolay anlaşılır ve kullanılır yapılardır.
Örnek 1 (Vildan hn.’ın isteği üzerine bu iki örneği ekliyorum umarım yardımcı olur)
Bir düzenli ifade (regular expression) olarak aşağıdaki örnek verilmiş olsun. Bu örneği sonlu otomat (finite state automata, Sonlu Özdevinirler) olarak göstermeye çalışalım:
a*b*
Yukarıdaki düzenli ifadeyi tanımak için öncelikle bu ifadeden üretilebilecek örnekleri görelim:
Üretilebilecek en kısa dizgi (String): ε (yani boş küme olacaktır, bu bazı kitaplarda λ sembolü ile de gösterilir). Çünkü kleene yıldızının üreteceği sonuçlar arasında boş küme de bulunmaktadır.
İkinci dizgimiz (String) : ab olacaktır ve bu üretme işlemi aab , abb, aabb, aaab, abbb şeklinde devam edecektir.
Yukarıdaki bu düzenli ifadeyi göstermek için aşağıdaki sonlu otomatı çizebiliriz (genelde sık yapılan bir hata olduğu için aşağıdaki hatalı örneği çizmek istiyorum):
Yukarıdaki şekilde anlatılmak istenen tek bir durum (State) oluşudur ve bu durum hem başlangıç (okla belirtilmiştir) hem de bitiş durumu (çift çizgi ile belirtilmiştir) olduğudur. Bu durum üzerinde hem a hem de b harfleri ile istenildiği kadar dönülebilir.
Yukarıdaki hata, yukarıdai FSM’in örneğin ba gibi bir kelimeyi de kabul etmesidir. Oysaki düzenli ifademiz buna izin vermemektedir. Doğrusu aşağıdaki şekilde olmalıdır.
Yukarıdaki çizim doğru çizimdir. Görüldüğü üzere otomatımız hem boş kelimeyi hem de a ve b ile üretilebilecek (Sırası değişmeden) bütün kelimeleri desteklemektedir.
Örnek 2:
Biraz daha karmaşık kabul edebileceğimiz bir örneği çözmeye çalışalım:
(a+b)*ab+c
Yukarıdaki ifadeyi analiz edip anlamaya çalışalım. Dilin üreteceği en küçük dizgiden (String) başlayalım ve uzatarak ihtimalleri deneyelim:
c
ab
aab
abab
aaab
bbab
şeklinde giden üretim listemiz bulunuyor. Yukarıdaki düzenli ifadeye bakıldığında görüleceği üzere + (ikinci + sembolü) ifadeyi ikiye bölmüştür. Yani ifademizi:
(a+b)*ab
veya
c
ifadelerinden birisini üretecek gibi düşünebiliriz.Bu durumu FSM ile gösterecek olursak:
şeklinde düşünülebilir. Elbette yukarıdaki çizim tam bir FSM değildir. Yani kollardan üstteki kolu açarak çizmemiz gerekir ancak fikir vermesi açısından + sembolleri (veya anlamındaki semboller) iki kol olarak düşünülebilir.
Yukarıdaki bu ifadeyi daha açık halde yazacak olursak ve üst kolu analiz edersek
(a+b)*ab
ifadesini de ikiye bölmek mümkündür:
(a+b)*
ve
ab
olarak bölünebilir.
Yukarıda bu üç ifade üleştirilmiştir (concatenate) yani
ABC
üleştirmesi olarak düşünülürse
A= (a+b)*
B= a
C= b
olarak düşünülebilir. Bu durumdaki üleştirme işlemleri aşağıdaki şekilde çizilebilir:
Yukarıdaki bu yeni çizimde üleştirme işlemi görülmüştür.
Yukarıdaki üleştirme işleminde de (a+b)*ifadesi kapalı olarak bırakılmıştır. Son olarak bu ifadeyi nasıl göstereceğimizi inceleyelim:
(a+b)*
ifadesi de görüldüğü üzere aslında a+b ifadesinin kleene yıldızının (kleene star) uygulanmış halidir. Dolayısıyla aşağıdaki şekilde gösterilebilir:
yukarıdaki şekilde görüleceği üzere bütün a ve b ile üretilebilecek (ve boş küme dahil) ihtimaller kapsanmaktadır.
Son aşamada bütün bu alt FSM çizimlerimizi birleştiriyoruz. Önce sondan başalayarak son iki çizimi birleştirelim:
Yukarıdaki ifade (a+b)*ab düzenli ifadesinin sonlu otomatı olmaktadır. Buna ilk otomatımızı da eklersek sonucu buluruz:
Yukarıda FSM’ini bulmak istediğimiz düzenli ifade olan (a+b)*ab+c ifadesinin son hali görülmektedir.
Yukarıdaki soru çözümü sırasında izelenen yöntem parçala fethet yöntemidir. Problem cevabını bildiğimiz basit parçalara bölünmüş ve sonra birleştirilmiştir. Problemde özel olarak karşılaşılabilecek en temel 3 durum olan veya (+), üleştirme (concetanation) ve kleene yıldızı durumlarını içeren bir örnek seçtim. Düzenli ifadeleri çevirirken istisnalar hariç bu üç duruma indirgeyerek çizim yapabilirsiniz.
iyi günler..siteniz derslerimizde çok yardımcı oluyor teşekkürler..sonlu durum makinaları,NFA-DFA ile ilgili örnek soru ve çözümler bulabileceğim bi yer var mı acaba cevaplarsanız sevinirim..
Eklemeye çalışayım. Tam olarak nasıl soruları istediğinizi söylemediğiniz için klasik olarak düzenli ifadelerden (regular expressions) sonlu otomata (finite state automata) çevirim yapan soru tipine bir örnek ve cevabını ekliyorum. Aynı soruyu önce NFA için çözüp ardından DFA’e çevirmeye çalışalım. Umarım yardımcı olur.
Başarılar
teşekkürler..
hazırladğınız kaynak gireceğim sınav için çok önemli bir yer teşkil etti çok teşşekür ederim
merhaba hocam, böyle konularin Türkce olarak yayinlanmasi müthis bir sey.
Tesekkürler.
hocam, elleriniz dert görmesin, 2 yıldır sizin ders notlarınız sınavlarıma çok yardımcı oldu.
Hocam bir soruda problemim var,
a(m+k)*m(j+n)*
bu soruda iki tane ‘m’ oldugu icin otomatin deterministic olmasini saglamalayiz.
Cozüm icin bir öneriniz var mi?
Simdiden tesekkürler