ডিটারমিনিস্টিক ফাইনাইট অটোমেটা (DFA) ব্যবহার করে "THE" সাবস্ট্রিং দিয়ে শেষ নয় এমন স্ট্রিং বের করতে হবে। খেয়াল রাখতে হবে "THE"-র যেকোনো ভেরিয়েশন যেমন "tHe", "The", "ThE" ইত্যাদি স্ট্রিং-এর শেষে থাকতে পারবে না।
প্রথমে dfa ভেরিয়েবল ডিফাইন করি এবং ০ দিয়ে ইণিশিয়ালাইজ করি যা আমাদের স্টেট ট্র্যাক রাখে। এটি প্রতিটি ক্যারেক্টার ম্যাচে ইনক্রিমেন্ট হয়।
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) যায় অন্যথায় শুরুর স্টেট অর্থাৎ 0-এ যায়।
void thirdState(char c){
if (c == 't' || c == 'T')
dfa = 1;
else
dfa = 0;
}
isAccepted(string str) টেস্ট করার স্ট্রিং প্যারামিটার হিসেবে নেয়। len ভেরিয়েবল স্ট্রিং দৈর্ঘ্য সংরক্ষণ করে। ফর লুপ স্ট্রিং দৈর্ঘ্য পর্যন্ত ইটারেট করে। যদি dfa = 0 হয় তবে start(char c) ফাংশন কল করা হয়, যদি dfa ১ সমান হয় তবে firstState(char c) ফাংশন কল করা হয় এবং যদি dfa ২ সমান হয় তবে secondState(char c) ফাংশন কল করা হয় এবং যদি dfa ১,২,৩ না হয় তবে thirdState(char c) ফাংশন কল করা হয়। আমরা true বা false ফেরত দিয়ে dfa ৩ কিনা তা চেক করি। যদি 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" দিয়ে শেষ নয় এমন স্ট্রিং-এর জন্য DFA বের করার ইমপ্লিমেন্টেশন:
#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
