【a,b】から「a」で始まり「a」で終わる文字列を判定するDFA構築プログラム

DFA（決定性有限オートマトン）とは

DFA（Deterministic Finite Automata：決定性有限オートマトン）とは、定義された受理条件に基づいて文字列を受理または拒否する有限状態機械です。

本記事では、「a」で始まり「a」で終わる文字列を受理するDFAを作成します。入力として使用できるのは、集合 {a, b} に含まれる文字のみです。この条件をもとにDFAを設計していきます。まず、DFAが受理する有効なケースと拒否する無効なケースについて確認しましょう。

受理される文字列の例

• ababba
• aabba
• aa
• a

拒否される文字列の例

• ab
• b
• aabab

プログラム例

以下のプログラムは、与えられた文字列が「a」で始まり「a」で終わるかどうかを判定します。このDFAは、先頭と末尾がどちらも「a」であるすべての文字列を受理対象とみなします。コードでは、文字列の最初の要素と最後の要素が一致しているかどうかをチェックし、それ以外の間にある文字は {a, b} のいずれであっても構いません。

#include <iostream>
#include <string.h>
using namespace std;
int main(){
    char str[] = "ababba";
    int length = strlen(str);
    if(str[0] == 'a' && str[length-1] == 'a'){
        printf("Accepted");
    } else {
        printf("Rejected");
    }
    return 0;
}

出力結果

Accepted

このように、DFAの考え方を用いることで、文字列の先頭と末尾の条件を簡潔に判定できます。実際のDFAでは状態遷移図を用いて各状態を明示的に定義しますが、プログラム上では上記のように条件分岐で表現できます。