C++ এ "THE" দিয়ে শেষ না হওয়া স্ট্রিংয়ের জন্য DFA?

ডিটারমিনিস্টিক ফিনিট অটোমেটন (ডিএফএ) ব্যবহার করে স্ট্রিংগুলি খুঁজে বের করতে যা সাবস্ট্রিং "THE" দিয়ে শেষ হয় না। আমাদের মনে রাখা উচিত যে "THE" সাবস্ট্রিং এর যেকোন পরিবর্তন যেমন "tHe", "The" "ThE" ইত্যাদি স্ট্রিং এর শেষে থাকা উচিত নয়।

প্রথমত, আমরা আমাদের dfa ভেরিয়েবলকে সংজ্ঞায়িত করি এবং এটিকে 0 তে আরম্ভ করি যা আমাদের অবস্থার ট্র্যাক রাখে। এটি প্রতিটি অক্ষরের সাথে মিলে যাওয়ায় বৃদ্ধি করা হয়৷

int dfa = 0;

begin(char c) পদ্ধতিটি একটি অক্ষর নেয় এবং এটি 't' বা 'T' কিনা তা পরীক্ষা করে এবং প্রথম অবস্থায় অর্থাৎ 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;
}

SecondState(char c) একটি অক্ষর নেয় এবং DFA দ্বিতীয় অবস্থা পরীক্ষা করার জন্য ব্যবহৃত হয়। পাস করা অক্ষরটি যদি 'E' বা 'e'-এর সমান হয়, তাহলে আমরা তৃতীয় অবস্থায় চলে যাই অন্যথায় শুরুর অবস্থায় অর্থাৎ 0.

void secondState(char c){
   if (c == 'e' || c == 'E')
      dfa = 3;
   else
      dfa = 0;
}

ThirdState(char c) একটি অক্ষর নেয় এবং DFA তৃতীয় অবস্থা চেক করার জন্য ব্যবহৃত হয়। যদি অক্ষরটি 't' বা 'T' এর সমান হয়, তাহলে আমরা প্রথম অবস্থায় (1) অন্য অবস্থায় সূচনা অবস্থায় যাই।

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 তারপর thirdState(char 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);
}

উদাহরণ

"THE" -

#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