दिए गए DFA स्ट्रिंग में 'a' और 'b' वर्ण हैं, जो 'a' वर्ण से शुरू और अंत होने चाहिए, कार्य DFA के माध्यम से यह पता लगाना है कि स्ट्रिंग 'a' से शुरू और अंत होती है या नहीं।
DFA (नियतात्मक परिमित ऑटोमेटा) क्या है?
कम्प्यूटेशन सिद्धांत में, सैद्धांतिक कंप्यूटर विज्ञान की एक शाखा, नियतात्मक परिमित ऑटोमेटा एक परिमित अवस्था मशीन है जो प्रतीकों की स्ट्रिंग को स्वीकार या अस्वीकार करती है। नियतात्मक का अर्थ गणना की विशिष्टता से है।
DFA द्वारा स्ट्रिंग खोजने के लिए और स्ट्रिंग को इनपुट (a, b) से 'a' से शुरू और अंत होना चाहिए। चूंकि मेमोरी की कोई अवधारणा नहीं है और हम केवल वर्तमान वर्ण को स्टोर कर सकते हैं, DFA दिए गए स्ट्रिंग को स्टोर नहीं कर सकता, अन्यथा हम आसानी से दिए गए अनुक्रम/स्ट्रिंग के पहले और अंतिम वर्ण की जांच कर सकते थे।
उदाहरण
इनपुट: a b b a आउटपुट: हां व्याख्या: इनपुट स्ट्रिंग 'a' से शुरू और अंत होती है इनपुट: a a a b a b आउटपुट: नहीं
उपरोक्त समस्या को हल करने के लिए हम जिस दृष्टिकोण का पालन कर रहे हैं −
तो, हम उपरोक्त समस्या के लिए एक DFA बनाएंगे और फिर हमारे द्वारा बनाए गए DFA के अनुसार समस्या को हल करेंगे।
dfa.jpg
एल्गोरिदम
शुरुआत चरण 1-> main() में रैंडम नंबर उत्पन्न करने के लिए srand(time(0)) फ़ंक्शन कॉल करें int max = 1 + rand() % 15 के रूप में चर घोषित करें int i = 0 घोषित करें और सेट करें जब तक (i < max) char data = 'a' + rand() % 2 घोषित करें data प्रिंट करें i बढ़ाएं IF data = 'a' IF(i = max) "YES" प्रिंट करें अंत लूप जब तक (i < max) data = 'a' + rand() % 2 सेट करें data प्रिंट करें i बढ़ाएं अगर (data = 'a' AND i = max) "YES\n" प्रिंट करें अंत अन्यथा IF(i = max) "NO" प्रिंट करें अंत अंत अंत अन्यथा लूप जब तक (i < max) data = 'a' + rand() % 2 सेट करें data प्रिंट करें i बढ़ाएं अंत "NO" प्रिंट करें अंत अंत रुकें
उदाहरण
#include <iostream> #include <time.h> using namespace std; int main() { // रैंडम नंबर उत्पन्न करने के लिए srand(time(0)); int max = 1 + rand() % 15; int i = 0; while (i < max) { char data = 'a' + rand() % 2; cout << data << " "; i++; if (data == 'a') { if (i == max) cout << "YES\n"; while (i < max) { data = 'a' + rand() % 2; cout << data << " "; i++; if (data == 'a' && i == max) { cout << "\nYES\n"; } else if (i == max) { cout << "\nNO\n"; } } } else { while (i < max) { data = 'a' + rand() % 2; cout << data << " "; i++; } cout << "\nNO\n"; } } return 0; }आउटपुट
b b a b a b a b b b b b NO
