Belirsiz Sonlu Otomat (Nondeterministic Finite Automat, NFA)

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:

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

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)^*

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.

« Belirli Sonlu Otomat (Deterministic Finite Automat, DFA) | NFA’den DFA’e çevirim (Converting NFA to DFA) »

Yorumlar

Toplam 3 yorum var.

vildan | 30 Jun 2009, 21:38
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..
Şadi Evren ŞEKER | 01 Jul 2009, 14:32
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
vildan | 03 Jul 2009, 23:42
teşekkürler..

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Belirsiz Sonlu Otomat (Nondeterministic Finite Automat, NFA)' isimli yazı 11 Nov 2008 tarihinde, saat: 01:29 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 1426 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.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar