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.
mi 
Hey do you have the program?