以下のサイトで勉強していると、「「THE」で終わらない文字列を受理するDFA」というテーマがあった。
そのDFAは以下のようになる(上記のサイトから引用しているが、小英文字も加える必要がある)。
それを再現するために紹介されていたコードが分かりにくかったので、自分で書き直した。
ただし、状態集合を{s0, s1, s2, s3}とし、初期状態はs0、受理状態を{s0, s1, s2}とした。
また、変数nextsには、遷移先の状態の番号が入る。
ex.) 遷移先がs2 ⇒ nexts = 2
#include <iostream>
#include <string>
using namespace std;
int nexts = 0; // start state = 0
void s0(char c){
if(c == 'T' || c == 't') nexts = 1;
else nexts = 0;
}
void s1(char c){
if(c == 'H' || c == 'h') nexts = 2;
else if(c == 'T' || c == 't') nexts = 1;
else nexts = 0;
}
void s2(char c){
if(c == 'E' || c == 'e') nexts = 3;
else if(c == 'T' || c == 't') nexts = 1;
else nexts = 0;
}
void s3(char c){
if(c == 'T' || c == 't') nexts = 0;
else nexts = 3;
}
bool isAccepted(string str){
for(int i = 0; i < (int)str.length(); i++){
switch(nexts){
case 0:
s0(str[i]);
break;
case 1:
s1(str[i]);
break;
case 2:
s2(str[i]);
break;
case 3:
s3(str[i]);
break;
default:
cout << "The variable nexts should be an integer between 0 and 3." << endl;
return false;
}
}
return nexts != 3;
}
int main() {
string str;
cin >> str;
if(isAccepted(str)) cout << "ACCEPTED" << endl;
else cout << "REJECTED" << endl;
return 0;
}