0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

「THE」で終わらない文字列を受理するDFAのコード(C++)

Last updated at Posted at 2023-05-27

以下のサイトで勉強していると、「「THE」で終わらない文字列を受理するDFA」というテーマがあった。

そのDFAは以下のようになる(上記のサイトから引用しているが、小英文字も加える必要がある)。

image.png

それを再現するために紹介されていたコードが分かりにくかったので、自分で書き直した。

ただし、状態集合を{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;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?