"द" सबस्ट्रिंग के साथ समाप्त नहीं होने वाले स्ट्रिंग्स को खोजने के लिए नियतात्मक परिमित ऑटोमेटन (डीएफए) का उपयोग करना। हमें इस बात का ध्यान रखना चाहिए कि "THE", "The" ,TheE" आदि जैसे सबस्ट्रिंग का कोई भी बदलाव स्ट्रिंग के अंत में नहीं होना चाहिए।
सबसे पहले, हम अपने dfa वेरिएबल को परिभाषित करते हैं और इसे 0 से इनिशियलाइज़ करते हैं जो हमारी स्थिति का ट्रैक रखता है। यह मिलान किए गए प्रत्येक वर्ण पर वृद्धि की जाती है।
int dfa = 0;
शुरुआत (चार सी) विधि एक चरित्र लेती है और जांचती है कि क्या यह 'टी' या 'टी' है और पहले राज्य में जाती है यानी 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; }
सेकेंडस्टेट (चार सी) एक चरित्र लेता है और डीएफए दूसरे राज्य की जांच के लिए प्रयोग किया जाता है। यदि पारित किया गया वर्ण 'ई' या 'ई' के बराबर है तो हम तीसरे राज्य में जाते हैं और प्रारंभिक अवस्था यानी 0.
void secondState(char c){ if (c == 'e' || c == 'E') dfa = 3; else dfa = 0; }
थर्डस्टेट (चार सी) एक चरित्र लेता है और डीएफए तीसरे राज्य की जांच के लिए प्रयोग किया जाता है। यदि वर्ण 't' या 'T' के बराबर है तो हम पहले राज्य में जाते हैं (1) अन्य प्रारंभिक अवस्था में अर्थात 0.
void thirdState(char c){ if (c == 't' || c == 'T') dfa = 1; else dfa = 0; }
isAccepted(string str) स्ट्रिंग को पैरामीटर के रूप में परीक्षण करने के लिए लेता है। लेन वैरिएबल स्ट्रिंग की लंबाई को स्टोर करता है। लूप के लिए स्ट्रिंग की लंबाई तक पुनरावृति होती है। यदि dfa =0 तो start(char c) फंक्शन कहा जाता है, यदि dfa 1 के बराबर होता है तो firstState(char c) फंक्शन को कॉल किया जाता है और यदि dfa 2 के बराबर होता है तो secondState(char c) फंक्शन को कॉल किया जाता है और यदि dfa है। t 1,2,3 तब थर्डस्टेट (चार c) फंक्शन कहलाता है। dfa 3 है या नहीं, इसके आधार पर हम सही या गलत लौटाते हैं। यदि dfa तीन के बराबर नहीं है तो स्ट्रिंग को स्वीकार किया जाता है अन्यथा नहीं।
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); }
उदाहरण
आइए "द" के साथ समाप्त न होने वाले स्ट्रिंग्स के लिए डीएफए खोजने के लिए निम्नलिखित कार्यान्वयन को देखें -
#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