Sonu web veya ebay ile biten kelimeleri yakalayan sonlu otomata (NFA) örneği

Bir önceki yazıda DFA örneğini koda dökmüştük. Bu yazıda ise koda dökülmesi nisbeten biraz daha zor olan NFA örneğini yapacağız. Kodlara topluca bu linkten erişebilirsiniz.

Öncelikle state diyagramı ile başlayalım.

DFA örneğini inceleyenler için buradaki statelerin karşılığının a=>1    b=>1,2   c= >1,3,5  d=>1,4,6    e=>1,5    f=>1,6  g=>1,7  h=>1,8  olduğunu belirtelim.

 

∑ sembolü yazdırılabilir (w,e,b,a,y) dahil tüm ASCII karakter kümesini temsil ediyor. Bu küme bizim input kümemiz. Bildiğiniz gibi NFA ların özelliği bir anda birden fazla state de bulunulabilmesidir. Bir örnekle açıklayalım. İnput string olarak ‘awebay’ kelimesini ele alalım. Başlangıç state imiz 1 olduğu için buradayız. a karakteri geliyor. Sonuçta 1 state i elimizde kalıyor. Transition fonksiyonu olarak ifade edersek δ(1,a)=1 oluyor. Dolayısıyla bulunduğumuz state hala 1 state i. Sırada w karakteri var. 1 state inde iken w gelirse artık 1 ve /veya 2 statelerinde bulunabiliriz yani δ(1,w)={1,2} . Sıradaki karakterimiz e. Bu karakteri bulunduğumuz her state (küme) için değerlendirmeliyiz. Bu yüzden δ(1,e)={1,5} ve δ(2,e)={3} çıktılarının bileşimi artık bizim bulunduğumuz state kümesi olacak ki bu da {1,5,3} state lerinden oluşan küme. İnput stringimizin devamında bay var. Sırasıyla yine karakterleri değerlendirmeye alırsak b için δ(1,b)={1}  δ(3,b)={4} δ(5,b)={6} olduğundan {4}U{1}U{6}={1,4,6} sonucunu alırız. a için δ({1,4,6},a)={1,7} sonucunu alıyoruz. Burada 4 state inde iken bir input geldiğinde boş kümeye düşüldüğüne dikkat edin. Son olarak bulunduğumuz {1,7} kümesinde iken y geldiğinde  δ({1,7},y)={1,8} sonucunu alıyoruz. Bulunduğumuz kümede kabul edilen 8 state i bulunduğu için girilen aswebay string i kabul ediliyor.

Şimdi kodu düşünelim. Bir anda birden fazla durumda bulunabileceğimizden bunu bir karakter dizisinde tutacağız. Bu kümedeki her eleman (state) için yeni gelen karakteri bir transition fonksiyonu ile değerlendirip bulunduğumuz yeni state kümesini elde edeceğiz ve bu kümeyi de yine bir dizide tutacağız. Yazımızın kilit noktası char * transition(char states[10],char input ) fonksiyonumuzun  kodları şu şekilde :

Fonksiyon iki parametre alıyor. States dizisi o anda bulunulan stateleri tutuyor. input ise değerlendirilecek karakter.  Bulunulan her state için (states dizisinin her bir elemanı için ) while döngüsü içindeki if else blokları ile önce bulunulan değerlendirilen state e sonra da gelen input a göre geçilecek state e  karar veriliyor. Geçilen state appendToArray fonksiyonu ile reached_states adlı diziye eklendikten sonra states deleteFromArray fonksiyonu ile dizisinden siliniyor. Son olarak bu karakter için (o anki tüm stateler ile) tüm değerlendirmeleri yaptıktan sonra ulaştığımız stateleri tutan reached_states dizisi arrayCopy fonksiyonu ile states dizisine kopyalanıp states dizisi sonuç olarak döndürülüyor. Böylece transition fonksiyonu görevini yapmış oluyor.

Basitlik açısından transition fonksiyonu tek karakter için (char input) çağrılıyor. Biz ise kullanıcıdan bir karakter dizisi alıyoruz. Aradaki köprüyü sağlamak için void send (string str) fonksiyonunu kullanıyoruz.

send fonksiyonu bir string (str) alıyor ve karakterlerini tek tek transition fonksiyonuna gönderiyor. Bunu printarray isimli fonksiyon içinden yapıyor. tahmin edeceğiniz gibi print array bir diziyi ekrana basan fonksiyon. Transition fonksiyonumuzun dönderdiği diziyi (states) alıyor ve bunu biraz ek bilgi ile ekrana basıyor. kodları şu şekilde:

void arrayCopy(char a[10], char[10]) fonksiyonu aldığı ikinci( b[10] ) diziyi ilk diziye( a[10] ) kopyalıyor.

char * deleteFromArray (char orginal[10] , char ap) fonksiyonu aldığı diziden (orjinal [10]) karakteri (ap) siliyor. Sildiği yere son elemanı koyuyor. Son karaktere NULL atıyor. Sonuçta da kalan diziyi dönderiyor.

Char * appendToArray (char [10], char ap) fonksiyonu aldığı diziye (orginal[]) aldığı karakteri (ap) eğer yoksa ekliyor. Zaten bulunuyorsa aldığı diziyi doğrudan dönderiyor.

son fonksiyonumuz void didAccepted() ile girdimizin otomata tarafından kabul edilip edilmediğini öğreniyoruz. Fonksiyon bunu reached_states içinde kabul edilen 4 ve 8 statelerinden birinin bulunup bulunmadığını kontrol ederek yapıyor.

Fonksiyonlarımızı automata isimli bir sınıf içine yazıyoruz.  reached_states dizimiz bu sınıfın private bir değişkeni. Bu arada başına erişim tanımlayıcı (public,private vs) yazmadığımız fonksiyonlar da varsayılan olarak private olarak değerlendiriliyor. Sınıfımızın genel görünümünü ve main fonksiyonunu verip yazımızı sonlandıralım.

Main fonksiyonunda kullanıcıdan stri isimli bir string alıyoruz, send fonksiyonuna gönderiyoruz. Son olarak didAccepted fonksiyonunu çağırarak inputun kabul edilip edilmediğini öğreniyoruz.

Programımızın örnek çıktısı :

Dizi boyutlarını 10 olarak sabit şekilde tanımadık. Çünkü bizim örneğimizde sadece 8 state imiz var ve hepsinde aynı anda bulunsak bile (ki örneğimizde bu bile mümkün değil) bu dizi bize yetecektir. Kodu basit tutup gerekli noktalara odaklanmak açısından diziyi sabit boyutlu tanımlamış olsak da dinamik olarak boyutu ayarlayanabilir. Kodların tamamını topluca bu linkten bulabileceğinizi tekrar belirterek yazımızı noktalıyoruz. Herkese kolay gelsin.