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

文字「a」と「b」から構成される文字列が与えられたとき、その文字列が「a」で始まり、かつ「a」で終わっているかどうかをDFA（決定性有限オートマトン）を用いて判定する方法を解説します。

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

理論計算機科学の一分野である計算理論において、決定性有限オートマトン（DFA：Deterministic Finite Automata）とは、記号の列を受け入れるか拒否するかを判定する有限状態機械です。「決定的（Deterministic）」とは、現在の状態と入力記号が決まれば、遷移先の状態が必ず一意に定まることを意味します。

本記事では、入力 (a, b) から「a」で始まり「a」で終わる文字列をDFAで判定します。DFAにはメモリの概念がなく、現在読み込んでいる文字しか保持できないため、与えられた文字列全体を保存することができません。もしメモリが使えるのであれば、文字列の最初と最後の文字を確認するだけで簡単に判定できますが、DFAでは状態遷移を工夫してこの問題を解決する必要があります。

実行例

Input: a b b a
Output: yes
説明: 入力文字列は「a」で始まり、「a」で終わっています

Input: a a a b a b
Output: no

問題を解くためのアプローチ

まず、この問題に対するDFAを設計し、その状態遷移に従ってプログラムを実装します。DFAの各状態の役割は以下の通りです。

• 開始状態： 最初の文字が「a」であれば受理候補の状態へ遷移し、「b」であればどの入力も受理されない拒否状態へ遷移します。
• 受理候補状態： 最後の文字が「a」である可能性を保持する状態です。「a」を読むと自分自身に留まり、「b」を読むと未確定状態へ遷移します。
• 未確定状態： 直前の文字が「b」である状態です。「a」を読めば受理候補状態へ戻り、「b」であれば自分自身に留まります。
• 拒否状態： 最初の文字が「b」だった場合に入る状態で、以降どのような入力でも受理されることはありません。

文字列の読み込みが終わった時点で受理候補状態にいれば「YES」、それ以外の状態であれば「NO」を出力します。

アルゴリズム

開始
ステップ1 -> main()関数内で
   乱数を生成するために srand(time(0)) を呼び出す
   変数 int max = 1 + rand() % 15 を宣言する
   変数 int i = 0 を宣言・初期化する
   i < max の間、以下を繰り返す
     文字 data = 'a' + rand() % 2 を宣言する
     data を出力する
     i をインクリメントする
     もし data == 'a' ならば
       もし i == max ならば
         "YES" を出力する
       終了
       i < max の間、以下を繰り返す
         data = 'a' + rand() % 2 を設定する
         data を出力する
         i をインクリメントする
         もし data == 'a' かつ i == max ならば
           YES\n を出力する
         終了
         そうでなければ もし i == max ならば
           NO を出力する
         終了
       繰り返し終了
     終了
     そうでなければ
       i < max の間、以下を繰り返す
         data = 'a' + rand() % 2 を設定する
         data を出力する
         i をインクリメントする
       繰り返し終了
       NO を出力する
     終了
   繰り返し終了
停止

C++プログラム例

#include <iostream>
#include <time.h>
using namespace std;
int main() {
   // 乱数を生成するためのシード設定
   srand(time(0));
   int max = 1 + rand() % 15;
   int i = 0;
   while (i < max) {
      char data = 'a' + rand() % 2;
      cout << data << " ";
      i++;
      if (data == 'a') {
         if (i == max)
            cout << "YES\n";
         while (i < max) {
            data = 'a' + rand() % 2;
            cout << data << " ";
            i++;
            if (data == 'a' && i == max) {
               cout << "\nYES\n";
            } else if (i == max) {
               cout << "\nNO\n";
            }
         }
      } else {
         while (i < max) {
            data = 'a' + rand() % 2;
            cout << data << " ";
            i++;
         }
         cout << "\nNO\n";
      }
   }
   return 0;
}

出力結果

b b a b a b a b b b b b
NO

この出力例では、生成された文字列が「b」で始まっているため、DFAは直ちに拒否状態へ遷移し、結果として「NO」が出力されます。最初の文字が「a」であり、かつ最後の文字も「a」である場合のみ「YES」となります。