डिटरमिनिस्टिक फाइनाइट ऑटोमेटन (DFA) का उपयोग उन स्ट्रिंग्स को खोजने के लिए करें जो उपस्ट्रिंग "THE" से खत्म नहीं होतीं। हमें ध्यान रखना चाहिए कि उपस्ट्रिंग "THE" की कोई भी विविधता जैसे "tHe", "The", "ThE" आदि स्ट्रिंग के अंत में नहीं होनी चाहिए।
पहले, हम अपने dfa वेरिएबल को परिभाषित करते हैं और इसे 0 से इनिशियलाइज़ करते हैं जो हमारी स्थिति को ट्रैक करता है। यह प्रत्येक कैरेक्टर मिलान पर बढ़ाया जाता है।
int dfa = 0;
begin(char c) मेथड एक कैरेक्टर लेता है और जांचता है कि क्या यह 't' या 'T' है और पहली स्थिति यानी 1 पर जाता है।
void begin(char c){
if (c == 't' || c == 'T')
dfa = 1;
}
firstState(char c) मेथड पहले कैरेक्टर की जांच करता है और उस मान के आधार पर dfa असाइन करता है। यदि c 't' या 'T' है तो हम पहली स्थिति पर जाते हैं, अन्यथा यदि c 'h' या 'H' है तो हम दूसरी स्थिति पर जाते हैं और अंत में यदि यह कोई अन्य कैरेक्टर है तो हम शुरुआती स्थिति यानी 0 पर जाते हैं।
void firstState(char c){
if (c == 't' || c == 'T')
dfa = 1;
else if (c == 'h' || c == 'H')
dfa = 2;
else
dfa = 0;
}
secondState(char c) एक कैरेक्टर लेता है और DFA की दूसरी स्थिति की जांच के लिए उपयोग किया जाता है। यदि पास किया गया कैरेक्टर 'E' या 'e' के बराबर है तो हम तीसरी स्थिति पर जाते हैं अन्यथा शुरुआती स्थिति यानी 0 पर।
void secondState(char c){
if (c == 'e' || c == 'E')
dfa = 3;
else
dfa = 0;
}
thirdState(char c) एक कैरेक्टर लेता है और DFA की तीसरी स्थिति की जांच के लिए उपयोग किया जाता है। यदि कैरेक्टर 't' या 'T' के बराबर है तो हम पहली स्थिति (1) पर जाते हैं अन्यथा शुरुआती स्थिति यानी 0 पर।
void thirdState(char c){
if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
isAccepted(string str) टेस्ट की जाने वाली स्ट्रिंग को पैरामीटर के रूप में लेता है। len वेरिएबल स्ट्रिंग की लंबाई संग्रहीत करता है। फॉर लूप स्ट्रिंग लंबाई तक पुनरावृति करता है। यदि dfa = 0 तो start(char c) फंक्शन कॉल किया जाता है, यदि dfa 1 के बराबर है तो firstState(char c) फंक्शन कॉल किया जाता है और यदि dfa 2 के बराबर है तो secondState(char c) फंक्शन कॉल किया जाता है और यदि dfa 1,2,3 नहीं है तो thirdState(char c) फंक्शन कॉल किया जाता है। हम इस आधार पर सत्य या असत्य वापस करते हैं कि dfa 3 है या नहीं। यदि dfa 3 के बराबर नहीं है तो स्ट्रिंग स्वीकार की जाती है अन्यथा नहीं।
bool isAccepted(string str){
int len = str.length();
for (int i = 0; i < len; i++) {
if (dfa == 0)
begin(str[i]);
else if (dfa == 1)
firstState(str[i]);
else if (dfa == 2)
secondState(str[i]);
else
thirdState(str[i]);
}
return (dfa != 3);
}
उदाहरण
"THE" से न खत्म होने वाली स्ट्रिंग्स के लिए DFA खोजने के लिए निम्नलिखित कार्यान्वयन देखें:
#include <iostream>
#include <string>
using namespace std;
int dfa = 0;
void begin(char c){
if (c == 't' || c == 'T')
dfa = 1;
}
void firstState(char c){
if (c == 't' || c == 'T')
dfa = 1;
else if (c == 'h' || c == 'H')
dfa = 2;
else
dfa = 0;
}
void secondState(char c){
if (c == 'e' || c == 'E')
dfa = 3;
else
dfa = 0;
}
void thirdState(char c){
if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
bool isAccepted(string str){
int len = str.length();
for (int i = 0; i < len; i++) {
if (dfa == 0)
begin(str[i]);
else if (dfa == 1)
firstState(str[i]);
else if (dfa == 2)
secondState(str[i]);
else
thirdState(str[i]);
}
return (dfa != 3);
}
int main(){
string str = "helloForTheWorld";
if (isAccepted(str) == true)
cout<<"The string "<<str<<" is accepted ";
else
cout<<"The string "<<str<<" is not accepted";
return 0;
}
आउटपुट
उपरोक्त कोड निम्नलिखित आउटपुट देगा:
The string helloForTheWorld is accepted