A NFA EXAMPLE TO CATCH STRINGS THAT ENDS WITH WEB or EBAY

In our privious article, we had shown how can be achieved with a DFA. This article we will introduce the same problem with a NFA which is relatively hard to implement than DFA. You can obtain all codes from here. Let’s start with state diagram. PS:For those who check over the DFA example the state equations is like this : 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 Here, “∑” symbol  is stands for the input set which is all printable ASCII characters including w,e,b,a,y . As you know,a rule of NFA’s, we can be in several states at one particular time. Let me explain with example. Suppose we had given “awebay” word. We start at state 1 because it’s our initial state. Then character “a” comes. We return to state 1. We can express this event via transition function like δ(1,a)=1 . So we have {1} state set which we are in. Next we have the character “w” .  If “w” comes while we are in state 1 we can now be in states 1 or 2. Videlicet δ(1,w)={1,2}. Next,  character is “e”. We must evaluate the output of transition function for each state that we are in. Therefor we say δ(1,e)={1,5} , δ(2,e)={3} and the output of transition function is {1,5,3}. Our word is continue with “bay”. If we evaluate them in order, for b: δ(1,b)={1}  δ(3,b)={4} δ(5,b)={6}  and {4}U{1}U{6}={1,4,6} and for a: δ({1,4,6},a)={1,7} . Pay attention that while we are in state 4, If any character comes, output of function is null set. Lastly from {1,7} where we in,If  “y” comes  we take output δ({1,7},y)={1,8}. In this manner we finish our word. Because of output state set {1,8} includes accepted state 8, the word aswebay is accepted by this automata. Now time to think about code. Conclusion of the example above, we can be in several state. To provide this feature, we will use a character array and keep the states in it. For each element of the states set(array), we must evaluate (via transition function) the next state or states for the input character. By doing this, we achieve the next states set that we are in. The keystone char * transition(char states[10],char input ) function can be implemented like this : Function get 2 parameter. First one is the states array. Second one is a character of our given string. For each member of the char array the process will be: decide what state it is, decide what input it is, decide where to go next and append it to new reached_states (If it is empty set, then delete old state), delete evaluated old state, And move on to next array member. New state is appended to reached_states via appendToArray function. Then old state is deleted via deleteFromArray. Eventually reached_states is copied into states via arrayCopy function and it is returned by transition function. So the task of transition function is over. For convenience transition function takes one character instead of a string at a time. Construct a brige between, we use void send (string str) function. send function takes one string (str) and send its characters to transition function one by one. It does this in printarray function. This function, as you guess, takes an array and prints it on the screen with some helpfull information. Wherein the use, takes the result that returned by transition function and prints it. Pay attention that the states[0] is initiated with 1. because it is our start state. void printarray(char *arr) is implemented like this: (not much to explain I guess) void arrayCopy(char a[10], char[10]) function copies the second parameter array ( b[10] ) into the first one ( a[10] ) . char * deleteFromArray (char orginal[10] , char ap) function deletes the parameter character ap from parameter array orginal[10]. Fills that area with last member of the array. Then it assigns NULL to the last position. As result returns the array back. Char * appendToArray (char [10], char ap) function tries to append the second parameter (character) to the first parameter which is an array (orginal[]). If it ‘s already in the array returns back without doing anything. Our last function void didAccepted() checks ıf the given string is accepted by automata or not. To do this, it looks for the reached_states has at least one accepted states. We can put aour functions in a class called automata. reached_states must be a member variable of this class. ps:If there is no access modifier to a member of class , then tis member is threated as private by default. in main function we take a string(stri) from user. Then we call the send function for this string. Lastly, to see the result, call didAccepted function to know if it is accepted or not. an example output of our program : We describe our arrays with length 10 to simplfy the codes and focus on key points. In this example we have 8 state. Even if we present all states (in this case even this is not possible) this arrays is enough for us. You can use dynamic array lengths if you wish. After pointing out this link to obtain all of codes  again, I stop here.  Happy codes 🙂 .

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.