DFA তৈরির প্রোগ্রাম যা C++ এ ইনপুট (a, b) থেকে 'a' দিয়ে শুরু এবং শেষ হয়

'a' এবং 'b' অক্ষরের একটি DFA স্ট্রিং দেওয়া হয়েছে, যা 'a' অক্ষর দিয়ে শুরু এবং শেষ হওয়া উচিত কাজটি হল DFA এর মাধ্যমে স্ট্রিংটি 'a' দিয়ে শুরু এবং শেষ হয় কিনা তা খুঁজে বের করা।

DFA(ডিটারমিনিস্টিক ফিনিট অটোমেটা) কি?

গণনার তত্ত্বে, তাত্ত্বিক কম্পিউটার বিজ্ঞানের একটি শাখা, ডিটারমিনিস্টিক ফিনিট অটোমেটা হল একটি সীমাবদ্ধ রাষ্ট্র মেশিন যা প্রতীকের স্ট্রিংগুলিকে গ্রহণ বা প্রত্যাখ্যান করে। ডিটারমিনিস্টিক বলতে বোঝায় চালানোর জন্য গণনার স্বতন্ত্রতা।

একটি DFA দ্বারা স্ট্রিং খুঁজে বের করার জন্য এবং স্ট্রিংটি ইনপুট (a, b) থেকে 'a' দিয়ে শুরু এবং শেষ হওয়া উচিত। যেহেতু মেমরির কোন ধারণা নেই এবং আমরা শুধুমাত্র বর্তমান অক্ষর সংরক্ষণ করতে পারি, তাই 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