DFA สำหรับสตริงที่ไม่ลงท้ายด้วย "THE" ใน C ++?

ในการใช้ Deterministic Finite Automaton(DFA) เพื่อค้นหาสตริงที่ไม่ได้ลงท้ายด้วยสตริงย่อย “THE” เราควรจำไว้ว่าการเปลี่ยนแปลงใดๆ ของสตริงย่อย “THE” เช่น “tHe”, “The” ”The” ฯลฯ ไม่ควรอยู่ที่ส่วนท้ายของสตริง

ขั้นแรก เรากำหนดตัวแปร dfa ของเราและกำหนดค่าเริ่มต้นเป็น 0 ซึ่งจะคอยติดตามสถานะของเรา จะเพิ่มขึ้นในแต่ละอักขระที่ตรงกัน

int dfa = 0;

วิธี start(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 เก็บความยาวของสตริง for loop วนซ้ำจนถึงความยาวของสตริง ถ้า 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);
}

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อค้นหา DFA สำหรับสตริงที่ไม่ลงท้ายด้วย “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