# DFA for Strings not ending with “THE”

Problem – Accept Strings that not ending with substring “THE”. Check if a given string is ending with “the” or not. The different forms of “the” which are avoided in the end of the string are:

`"THE", "ThE", "THe", "tHE", "thE", "The", "tHe" and "the"`

All those strings that are ending with any of the above mentioned forms of “the” are not accepted.

Determinitis finite automata (DFA) of strings that not ending with “THE” –
The initial and starting state in this dfa is Qo

Approach used in the program –
In this program, consider the 4 states to be 0, 1, 2 and 3. Now let us take a variable named DFA which will be initially 0. Whenever any transition takes place, it will update the value of DFA with the number associated with new state.

Example : If a transition occurs from state 0 to state 1 then the value of DFA will be updated to 1. If a transition occurs from state 2 to state 3 then the value of dfa will be updated to 3. In this way, apply this algorithm on entire string and if in the end, then reach state 0, 1 or 2 then our string will be accepted otherwise not.

```Input : XYzabCthe
Output : NOT ACCEPTED

Input :  Themaliktth
Output :  ACCEPTED```

## C++

 `// CPP program to implement DFS that accepts ` `// all string that do not end with "THE" ` `#include ` `#include ` ` `  `// dfa tells the number associated ` `// with the present state ` `int` `dfa = 0; ` ` `  `// This function is for ` `// the starting state (zeroth) of DFA ` `void` `start(``char` `c) ` `{ ` `    ``// On receiving 'T' or 't' goto first state (1) ` `    ``if` `(c == ``'t'` `|| c == ``'T'``) ` `        ``dfa = 1; ` `} ` ` `  `// This function is for the first state of DFA ` `void` `state1(``char` `c) ` `{ ` `    ``// On receiving 'T' or 't' goto first state (1) ` `    ``if` `(c == ``'t'` `|| c == ``'T'``) ` `        ``dfa = 1; ` ` `  `    ``// On receiving 'H' or 'h' goto second state (2) ` `    ``else` `if` `(c == ``'h'` `|| c == ``'H'``) ` `        ``dfa = 2; ` ` `  `    ``// else goto starting state (0) ` `    ``else` `        ``dfa = 0; ` `} ` ` `  `// This function is for the second state of DFA ` `void` `state2(``char` `c) ` `{ ` `    ``// On receiving 'E' or 'e' goto third state (3) ` `    ``// else goto starting state (0) ` `    ``if` `(c == ``'e'` `|| c == ``'E'``) ` `        ``dfa = 3; ` `    ``else` `        ``dfa = 0; ` `} ` ` `  `// This function is for the third state of DFA ` `void` `state3(``char` `c) ` `{ ` `    ``// On receiving 'T' or 't' goto first state (1) ` `    ``// else goto starting state (0) ` `    ``if` `(c == ``'t'` `|| c == ``'T'``) ` `        ``dfa = 1; ` `    ``else` `        ``dfa = 0; ` `} ` ` `  `bool` `isAccepted(``char` `str[]) ` `{ ` `    ``// store length of string ` `    ``int` `len = ``strlen``(str); ` ` `  `    ``for` `(``int` `i=0; i < len; i++) { ` `            ``if` `(dfa == 0) ` `                ``start(str[i]); ` ` `  `            ``else` `if` `(dfa == 1) ` `                ``state1(str[i]); ` ` `  `            ``else` `if` `(dfa == 2) ` `                ``state2(str[i]); ` ` `  `            ``else` `                ``state3(str[i]);         ` `    ``} ` ` `  `    ``return` `(dfa != 3); ` `} ` ` `  `// driver code ` `int` `main() ` `{ ` `    ``char` `str[] = ``"forTHEgeeks"``; ` `    ``if` `(isAccepted(str) == ``true``) ` `        ``printf``(````"ACCEPTED "````); ` `    ``else` `        ``printf``(````"NOT ACCEPTED "````); ` `    ``return` `0; ` `} `

/div>

## Python3

 `# Python3 program to implement DFS that accepts  ` `# all stringing that do not end with "THE"  ` ` `  `# This function is for the starting ` `# state (zeroth) of DFA  ` `def` `start(c): ` `     `  `    ``# On receiving 'T' or 't' goto  ` `    ``# first state (1)  ` `    ``if` `(c ``=``=` `'t'` `or` `c ``=``=` `'T'``): ` `        ``dfa``=``1` ` `  `# This function is for the first state of DFA  ` `def` `state1(c):  ` `     `  `    ``# On receiving 'T' or 't' goto first state (1)  ` `    ``if` `(c ``=``=` `'t'` `or` `c ``=``=` `'T'``): ` `        ``dfa ``=` `1` ` `  `    ``# On receiving 'H' or 'h' goto second state (2)  ` `    ``elif` `(c ``=``=` `'h'` `or` `c ``=``=` `'H'``): ` `        ``dfa ``=` `2` ` `  `    ``# else goto starting state (0)  ` `    ``else``: ` `        ``dfa ``=` `0` ` `  `# This function is for the second state of DFA  ` `def` `state2(c): ` `     `  `    ``# On receiving 'E' or 'e' goto third  ` `    ``# state (3) else goto starting state (0)  ` `    ``if` `(c ``=``=` `'e'` `or` `c ``=``=` `'E'``): ` `        ``dfa ``=` `3` `    ``else``: ` `        ``dfa ``=` `0` `         `  `# This function is for the third state of DFA  ` `def` `state3(c): ` `     `  `    ``# On receiving 'T' or 't' goto first  ` `    ``# state (1) else goto starting state (0)  ` `    ``if` `(c ``=``=` `'t'` `or` `c ``=``=` `'T'``): ` `        ``dfa ``=` `1` `    ``else``: ` `        ``dfa ``=` `0` ` `  `def` `isAccepted(string): ` `     `  `    ``# store length of stringing  ` `    ``length ``=` `len``(string)  ` ` `  `    ``for` `i ``in` `range``(length): ` `        ``if` `(dfa ``=``=` `0``): ` `            ``start(string[i]) ` `        ``elif` `(dfa ``=``=` `1``): ` `            ``state1(string[i]) ` `        ``elif` `(dfa ``=``=` `2``): ` `            ``state2(string[i]) ` `        ``else``: ` `            ``state3(string[i])         ` `    ``return` `(dfa !``=` `3``)  ` ` `  `# Driver Code  ` `if` `__name__ ``=``=` `"__main__"` `: ` `    ``string``=``"forTHEgeeks"` `     `  `    ``# dfa tells the number associated  ` `    ``# with the present state ` `    ``dfa ``=` `0` `    ``if` `isAccepted(string): ` `        ``print``(``"ACCEPTED"``) ` `    ``else``: ` `        ``print``(``"NOT ACCEPTED"``) ` ` `  `# This code is contributed by SHUBHAMSINGH10 `

## PHP

 ` `

Output :

```ACCEPTED
```

The time complexity of this program is O(n)