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):

nfaab

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.

nfaab2

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:

nfa2

ş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:

nfa3

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:

nfaab

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:

nfa4

Yukarıdaki ifade (a+b)*ab düzenli ifadesinin sonlu otomatı olmaktadır. Buna ilk otomatımızı da eklersek sonucu buluruz:

nfa5

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.

Yorumlar

  1. vildan

    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..

  2. Erol

    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

Erol için bir cevap yazın Cevabı iptal et

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