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

Linux kullandıysanız mutlaka grep komutu ile de bir yerlerde karşılaşmışsınızdır. Bilmeyenler için kısaca bunun verilen bir stringi yakalamaya yarayan bir komut olduğunu belirtirek uzatmadan geçelim. Peki bu komut nasıl koda dökülmüştür? Bir arama motoru istediğiniz metni ararken metin karşılaştırmalarını nasıl yapar ve sizi yakın sonuçlara götürür? Bu yazımız kafanızda birşeyler oluşması sağlayabilir.

Bu yazıda sonunda web veya ebay (regex olarak ifade edersek (ASCII karakter kümesi)*web ya da (ASCII karakter kümesi)*ebay ) kelimeleri geçen stringleri yakalayan sonlu otomata örneğinin c++ ile nasıl koda döküleceğini örnekleyeceğiz. Bu iş için DFA (Deterministic Finite Automata) kullanacağız.

Bildiğiniz gibi DFA da herhangi bir anda sadece bir state de bulunabiliriz. Bu state in hangisi olduğunu bir karakter değişkeni içerisinde saklayacağız. DFA ların bir başka özelliği ise input alfabesindeki herhangi bir inputa karşılık o anda bulunulan stateden hangi state e geçileceğinin net bir şekilde belli olmasıdır. Biz geçişleri if else blokları ile kontrol edeceğiz. İstenirse switch case yapısı da kullanılabilir.

Otomatamızın state diyagramı gördüğünüz gibi olacaktır.

Burada “∑” input alfabemizin kümesi olan yazdırılabilir  tüm (w,e,b,a,y dahil) ASCII karakterlerini temsil ediyor.

0: başlangıç state imiz. Elimizde herhangi istediğimiz bir karakter dizisi bulunmadığını niteliyor.

1: elimizde ‘w’ bulunduğu durum.

2:elimizde ‘we’ bulunduğu durumu belirtiyor.

3:elimizde ‘web’ bulunduğu durumu belirtiyor. Bu kabul edilen bir state. Kelimemizin sonunda web olduğunu haber veriyor.

4:elimizde ‘e’ bulunduğu durumu belirtiyor.

5:elimizde ‘eb’ bulunduğu durumu belirtiyor.

6:elimizde ‘eba’ bulunduğu durumu belirtiyor.

7:elimizde ‘ebay’ bulunduğu durumu belirtiyor. Bu kabul edilen bir state. Kelimemizin sonunda ebay geçtiğini bize anlatıyor.

Gelelim kodlamaya. Kodları bölüm bölüm açıklayacağız. Tamamını şuradan alabilirsiniz.

State ler arasındaki geçişi private: char transition(char) fonksiyonu ile sağlayacağız.

Bu fonksiyon bir adet char değişkeni alıyor. Bu bizim o çağrıda değerlendireceğimiz karakter. Örneğin “aswebay” girilmişse ilk değerlendirilecek input değişkeni a karakteri olacak. başlangıç state i 0 olduğu için ilk if bloğuna girilip karakterin w olup olmadığına bakılacak , olmadığı için state değişkenimiz 0 olarak kalacak. Kontroller bu şekilde devam ederek sonuçta bulunduğumuz state döndürülecek.

not: i değişkeninin herhangi bir görevi bulunmamakta

public: void send (string) fonksiyonumuzun görevi girilen stringin her karakteri için tek tek transition fonksiyonumuzu çağırmak.

public: int didAccepted () Fonksiyonumuzun görevi işlemler bittikten sonra çağrıldığında stringin kabul edilip edilmediğini kontrol etmek. Bunu state değişkenindeki değerin kabul edilen statelerden biri ile eşleşip eşleşmediğini karşılaştırarak yapıyor.

Fonksiyonlarımız automata sınıfımızda yer alıyor.sınıfımızda bulunan state değişkeni private ve  ilk değeri 0 olarak atanmış durumda çünkü başlangıç state imiz 0.

main fonksiyonumuzda ise bir string tanımlıyoruz. automata objesi(object) ile bu stringi send fonksiyonuna gönderiyoruz ve son olarak kabul edilen bir string olup olmadığını didAccepted fonksiyonu ile kontrol ediyoruz.

Dfa örneğimiz bu şekildeydi. Umarım kafanızda bir şeyler oluşmasına yardımcı olur. NFA örneğine buradan ulaşabilirsiniz. Kolay gelsin.