C ++の入力（a、b）から「a」で開始および終了するDFAを構築するプログラム

文字「a」と「b」のDFA文字列があり、文字「a」で開始および終了する必要がある場合、タスクは、文字列がDFAを介して「a」で開始および終了するかどうかを確認することです。

DFA（Deterministic Finite Automata）とは何ですか？

理論計算機科学の一分野である計算理論では、決定性有限オートマトンは、記号の文字列を受け入れるか拒否する有限状態マシンです。決定論的とは、実行する計算の一意性を指します。

DFAで文字列を検索する場合、文字列は入力（a、b）の「a」で開始および終了する必要があります。メモリの概念はなく、現在の文字しか保存できないため、DFAは提供された文字列を保存できません。それ以外の場合は、指定されたシーケンス/文字列の最初と最後の文字を簡単に確認できます。

例

Input: a b b a
Output: yes
Explanation: The input string starts and ends with ‘a’

Input: a a a b a b
Output: no

上記の問題を解決するために私たちが従うアプローチ-

そこで、上記の問題に対してDFAを作成し、作成したDFAに従って問題を解決します。

dfa.jpg

アルゴリズム

Start
Step 1-> In main()
   Call function srand(time(0)) to generate random numbers
   Declare variable as int max = 1 + rand() % 15
   Declare and set int i = 0
   While(i < max)
      Declare char data = 'a' + rand() % 2
      Print data
      Increment i
      IF data = 'a'
         IF(i = max)
            Print "YES"
         End
         Loop While (i < max)
            Set data = 'a' + rand() % 2
            Print data
            Increment i
            If (data = 'a' AND i = max)
               Print YES\n
            End
            Else IF(i = max)
               Print NO
            End
         End
      End
      Else
         Loop While (i < max)
            Set data = 'a' + rand() % 2
            Print data
            Increment i
         End
         Print NO
      End
   End
Stop

例

#include <iostream>
#include <time.h>
using namespace std;
int main() {
   // for generating random numbers
   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