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 🙂 .