DFA बनाने का प्रोग्राम जो C++ में इनपुट (a, b) से 'a' से शुरू और खत्म होता है

वर्णों 'ए' और 'बी' के एक डीएफए स्ट्रिंग को देखते हुए, जो कि 'ए' से शुरू और समाप्त होना चाहिए, कार्य यह पता लगाना है कि स्ट्रिंग डीएफए के माध्यम से 'ए' के ​​साथ शुरू और समाप्त होती है या नहीं।

DFA (निर्धारक परिमित ऑटोमेटा) क्या है?

गणना के सिद्धांत में, सैद्धांतिक कंप्यूटर विज्ञान की एक शाखा, नियतात्मक परिमित ऑटोमेटा एक परिमित राज्य मशीन है जो प्रतीकों के तार को स्वीकार या अस्वीकार करती है। नियतात्मक चलाने के लिए गणना की विशिष्टता को संदर्भित करता है।

एक डीएफए द्वारा स्ट्रिंग को खोजने के लिए और स्ट्रिंग को इनपुट (ए, बी) से 'ए' के ​​साथ शुरू और समाप्त होना चाहिए। चूंकि स्मृति की कोई अवधारणा नहीं है और हम केवल वर्तमान वर्ण को संग्रहीत कर सकते हैं, DFA प्रदान की गई स्ट्रिंग को संग्रहीत नहीं कर सकता है, अन्यथा हम आसानी से हमें दिए गए अनुक्रम/स्ट्रिंग के पहले और अंतिम वर्ण की जांच कर सकते हैं।

उदाहरण

Input: a b b a
Output: yes
Explanation: The input string starts and ends with ‘a’

Input: a a a b a b
Output: no

उपरोक्त समस्या के समाधान के लिए हम जिस दृष्टिकोण का अनुसरण कर रहे हैं -

इसलिए, हम ऊपर बताई गई समस्या के लिए DFA बनाएंगे और फिर हमारे द्वारा बनाए गए DFA के अनुसार समस्या का समाधान करेंगे।

dfa.jpg

एल्गोरिदम

Start
Step 1-> In main()
   Call function srand(time(0)) to generate random numbers
   Declare variable as int max = 1 + rand() % 15
   Declare and set int i = 0
   While(i < max)
      Declare char data = 'a' + rand() % 2
      Print data
      Increment i
      IF data = 'a'
         IF(i = max)
            Print "YES"
         End
         Loop While (i < max)
            Set data = 'a' + rand() % 2
            Print data
            Increment i
            If (data = 'a' AND i = max)
               Print YES\n
            End
            Else IF(i = max)
               Print NO
            End
         End
      End
      Else
         Loop While (i < max)
            Set data = 'a' + rand() % 2
            Print data
            Increment i
         End
         Print NO
      End
   End
Stop

उदाहरण

#include <iostream>
#include <time.h>
using namespace std;
int main() {
   // for generating random numbers
   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