'a' দিয়ে শুরু ও শেষ হলে DFA তৈরি করার C++ প্রোগ্রাম

'a' এবং 'b' অক্ষরಗಳಿಂದ গঠিত একটি DFA স্ট্রিং দেওয়া আছে, যা 'a' দিয়ে শুরু এবং 'a' দিয়ে শেষ হতে হবে; কাজটি হলো DFA-এর মাধ্যমে স্ট্রিংটি 'a' দিয়ে শুরু এবং শেষ হয় কিনা তা যাচাই করা।

DFA (Deterministic Finite Automata) কী?

গণনার তত্ত্বে, সैद्धানতিক কম্পিউটার বিজ্ঞানের একটি শাখা, ডিটারমিনিস্টিক ফাইনাইট অটোমেটা হলো একটি সসীম স্টেট মেশিন যা সিম্বলের স্ট্রিং গ্রহণ বা অস্বীকার করে। ডিটারমিনিস্টিক বলতে কম্পিউটেশন চালানোর ייחודকতাকে বোঝায়।

ইনপুট (a, b) থেকে 'a' দিয়ে শুরু ও শেষ হওয়া স্ট্রিং খুঁজে বের করার জন্য DFA ব্যবহার করা হচ্ছে। যেহেতু মেমরির ধারণা নেই এবং আমরা শুধু বর্তমান ক্যারেক্টার সংরক্ষণ করতে পারি, তাই DFA দেওয়া স্ট্রিংটি সংরক্ষণ করতে পারে না, অন্যথায় আমরা সহজে স্ট্রিংটির প্রথম এবং শেষ ক্যারেক্টার চেক করতে পারতাম।

উদাহরণ

ইনপুট: a b b a আউটপুট: yes ব্যাখ্যা: ইনপুট স্ট্রিং 'a' দিয়ে শুরু ও শেষ হয়েছে
ইনপুট: a a a b a b আউটপুট: no

সমস্যা সমাধানের পদ্ধতি -

আমরা উপরোক্ত সমস্যার জন্য একটি DFA তৈরি করব এবং সেটি অনুযায়ী সমস্যাটি সমাধান করব।

dfa.jpg

অ্যালগরিদম

শুরু
ধাপ ১ -> main()-এ
    srand(time(0)) কল করে র‍্যান্ডম নম্বর জেনারেট
    int max = 1 + rand() % 15 ঘোষণা
    int i = 0 ঘোষণা এবং সেট
    যতক্ষণ (i < max)
        char data = 'a' + rand() % 2 ঘোষণা
        data প্রিন্ট
        i বৃদ্ধি
        যদি data == 'a'
            যদি (i == max)
                "YES" প্রিন্ট
            শেষ
            লুপ যতক্ষণ (i < max)
                data = 'a' + rand() % 2 সেট
                data প্রিন্ট
                i বৃদ্ধি
                যদি (data == 'a' এবং i == max)
                    "YES\n" প্রিন্ট
                শেষ
                অন্যথায় যদি (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