DFA cho Chuỗi không kết thúc bằng “THE” trong C ++?

Sử dụng Automaton hữu hạn xác định (DFA) để tìm các chuỗi không kết thúc bằng chuỗi con “THE”. Chúng ta nên nhớ rằng bất kỳ biến thể nào của chuỗi con “THE” như “tHe”, “The”, “ThE”, v.v. không được ở cuối chuỗi.

Đầu tiên, chúng tôi xác định biến dfa của mình và khởi tạo nó thành 0 để theo dõi trạng thái của chúng tôi. Nó được tăng dần trên mỗi ký tự được so khớp.

int dfa = 0;

Phương thức begin (char c) nhận một ký tự và kiểm tra xem ‘t’ hay ‘T’ của nó và chuyển sang trạng thái đầu tiên, tức là 1.

void begin(char c){
   if (c == 't' || c == 'T')
   dfa = 1;
}

Phương thức firstState (char c) kiểm tra ký tự đầu tiên và gán dfa dựa trên giá trị đó. Nếu c là 't' hoặc 'T' thì chúng ta chuyển sang trạng thái đầu tiên khác nếu c là 'h' hoặc 'H', chúng ta chuyển sang trạng thái thứ hai và cuối cùng nếu đó là một số ký tự khác thì chúng ta chuyển sang trạng thái bắt đầu tức là 0.

void firstState(char c){
   if (c == 't' || c == 'T')
      dfa = 1;
   else if (c == 'h' || c == 'H')
      dfa = 2;
   else
      dfa = 0;
}

Trạng thái thứ hai (char c) nhận một ký tự và được sử dụng để kiểm tra trạng thái thứ hai của DFA. Nếu ký tự được truyền bằng ‘E’ hoặc ‘e’ thì chúng ta chuyển sang trạng thái thứ ba khác với trạng thái bắt đầu, tức là 0.

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

Trạng thái thứ ba (char c) nhận một ký tự và được sử dụng để kiểm tra trạng thái thứ ba của DFA. Nếu ký tự bằng ‘t’ hoặc ‘T’ thì chúng ta chuyển đến trạng thái đầu tiên (1) khác với trạng thái bắt đầu, tức là 0.

void thirdState(char c){
   if (c == 't' || c == 'T')
      dfa = 1;
   else
      dfa = 0;
}

IsAccepted (string str) lấy chuỗi được kiểm tra làm tham số. Biến len lưu trữ độ dài của chuỗi. Vòng lặp for lặp lại cho đến hết độ dài chuỗi. Nếu dfa =0 thì hàm start (char c) được gọi, nếu dfa bằng 1 thì hàm firstState (char c) được gọi và nếu dfa bằng 2 thì hàm secondState (char c) được gọi và nếu dfa isn ' t 1,2,3 thì hàm thirdState (char c) được gọi. Chúng tôi trả về true hoặc false dựa trên nếu dfa là 3 hay không. Nếu dfa không bằng ba thì chuỗi được chấp nhận, ngược lại thì không.

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);
}

Ví dụ

Chúng ta hãy xem cách triển khai sau để tìm DFA cho các chuỗi không kết thúc bằng “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;
}

Đầu ra

Đoạn mã trên sẽ tạo ra kết quả sau -

The string helloForTheWorld is accepted