A DFA example that catch strings ending with web/ebay

If you have ever used Linux ,you probably meet with the grep command. For who doesn’t know it, shortly, we can say it is a command is used to catch a given string. So how grep command can be implemented? How can a search engine compare words to find the closer results for your queries? This topic can help you with start understanding.

We will introduce how you can implement a DFA which controls a given string if it ends with ebay/web (as regex (all printable ASCII characters)*web or (all printable ASCII characters)*ebay ) or not.

As you know, as a rule of DFA, We can be in just one state at a time. We are going to keep this information (which state we are in) in a character variable. Another characteristic of DFA s, it is clear which state to jump which we are present, for a particular input character . We are going to control the this pass with if-else blocks.

The diagram of our automata will be like this

Here, “∑” symbol  is stands for the input set which is all printable ASCII characters includes w,e,b,a,y .

0 is our initial state.It means we have nothing that we like.

state 1 tells we have “w”

state 2 tells we have “w” followed by “e” (we)

state 3 tells we have “web” .This state is an accepted state.

state 4 tells we have “e”

state 5 tells we have “eb”

state 6 tells we have “eba”

state 7 tells we have “ebay”. This is also an accepted state.

Let’s get to coding.We are going to explain codes part by part. You can obtain whole code from here

Transition between states will be controlled via private: char transition(char) function.

ps:i hasn’t got any mission

This function gets just a char variable which will be handled for that call. For example; if we enter “aw”, firstly we handle the “a” character. First if block will be evaluated and because of “a” is not equal “w” , state variable will be set as “0”. Then the similar process will go on with character “w”. Eventually the state variable will be returned as 1. Because we have “w” character.

The task of public: void send (string) function is to call transition function for ever single character in a given string. Because Transition function can handle just one character at a time.

Function public: int didAccepted () , is responsible for controll whether the given string has accepted or not. It can achieve this by checking the state variable is whether equal to 3 or 7 or not.

Our functions will be in a class named automata. Private class variable state is already initiated with 0 because our initial state is 0.

Lastly we have the main function like above. We create an automata object. Then send (via send function) the string that is entered by user. Eventualy we check  if it is accepted by automaton via didAccepted function.

End of story 🙂 I hope this helped you with some understanding. You can view the NFA automata implementation via this link.

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.