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

ปัญหา

สร้าง DFA (Deterministic Finite Automaton) ที่ยอมรับสตริงที่ ไม่ลงท้ายด้วย "THE" (ไม่สนใจตัวพิมพ์เล็ก/ใหญ่)

State Diagram

• State 0: เริ่มต้น / ไม่เจอ T
• State 1: เจอ 'T' หรือ 't'
• State 2: เจอ 'TH' หรือ 'Th' หรือ 'tH' หรือ 'th'
• State 3: เจอ "THE" (Reject state)

Transition Functions

State 0: 'T'/'t' → 1, อื่น → 0
State 1: 'T'/'t' → 1, 'H'/'h' → 2, อื่น → 0
State 2: 'E'/'e' → 3, อื่น → 0
State 3: 'T'/'t' → 1, อื่น → 0

โปรแกรมตัวอย่าง

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

int dfa = 0;

void start(char c) { if (c=='t'||c=='T') dfa=1; }
void state1(char c) { 
    if (c=='t'||c=='T') dfa=1; 
    else if (c=='h'||c=='H') dfa=2; 
    else dfa=0; 
}
void state2(char c) { if (c=='e'||c=='E') dfa=3; else dfa=0; }
void state3(char c) { if (c=='t'||c=='T') dfa=1; else dfa=0; }

bool isAccepted(string str) {
    for (char c : str) {
        if (dfa==0) start(c);
        else if (dfa==1) state1(c);
        else if (dfa==2) state2(c);
        else state3(c);
    }
    return dfa != 3;  // ยอมรับถ้าไม่ได้อยู่ state 3
}

int main() {
    string s = "helloForTheWorld";
    cout << (isAccepted(s) ? "Accepted" : "Not Accepted");
    return 0;
}

ผลลัพธ์

Accepted