DFA cho chuỗi KHÔNG kết thúc bằng "THE" trong C++

Thiết kế **DFA (Deterministic Finite Automaton - Tự động hữu hạn xác định)** chấp nhận chuỗi **KHÔNG** kết thúc bằng chuỗi con "THE" (không phân biệt chữ hoa/thường: "the", "The", "tHe"...).

Thiết kế trạng thái (States)

State 0 (Start): Chưa khớp gì / Vừa khớp xong một chuỗi không phải tiền tố của "THE".
State 1: Vừa đọc được 'T' hoặc 't' (Khớp tiền tố "T").
State 2: Vừa đọc được "TH" hoặc "Th" hoặc "tH" (Khớp tiền tố "TH").
State 3 (Dead/Reject): Vừa đọc được "THE" (hoặc biến thể) ở **cuối chuỗi**. Đây là trạng thái **không chấp nhận (Reject)**. Nếu đọc thêm ký tự khác, thoát ra State 0 hoặc 1.

Chấp nhận (Accept) nếu kết thúc ở State 0, 1, hoặc 2. Từ chối nếu kết thúc ở State 3.

Bảng chuyển trạng thái (Transition Table)

State \ Input	'T'/'t'	'H'/'h'	'E'/'e'
0	1	0	0
1	1	2	0
2	1	0	3
3	1	0	0

Chương trình C++

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

bool isAcceptedByDFA(const string& str) {
    int state = 0;
    for (char c : str) {
        char lower = tolower(c);
        switch(state) {
            case 0:
                if (lower == 't') state = 1;
                else state = 0;
                break;
            case 1:
                if (lower == 't') state = 1;
                else if (lower == 'h') state = 2;
                else state = 0;
                break;
            case 2:
                if (lower == 'e') state = 3; // Đã thấy "THE"
                else if (lower == 't') state = 1;
                else state = 0;
                break;
            case 3: // Đã thấy "THE", nhưng còn ký tự tiếp theo
                if (lower == 't') state = 1;
                else state = 0;
                break;
        }
    }
    // Chấp nhận nếu KHÔNG ở trạng thái 3 (tức là không kết thúc bằng THE)
    return state != 3;
}

int main() {
    vector<string> tests = {"helloForTheWorld", "TheEnd", "THE", "NothingHere", "Ththe", "TheThe"};
    for (auto &s : tests) {
        cout << "\"" << s << "\" -> " << (isAcceptedByDFA(s) ? "CHAP NHAN (Khong ket thuc THE)" : "TU CHOI (Ket thuc THE)") << endl;
    }
    return 0;
}

Đầu ra

"helloForTheWorld" -> CHAP NHAN (Khong ket thuc THE)
"TheEnd" -> CHAP NHAN (Khong ket thuc THE)
"THE" -> TU CHOI (Ket thuc THE)
"NothingHere" -> CHAP NHAN (Khong ket thuc THE)
"Ththe" -> TU CHOI (Ket thuc THE)
"TheThe" -> TU CHOI (Ket thuc THE)