在C ++中从输入(a，b)构建以'a'开头和结尾的DFA程序

给定DFA字符串“ a”和“ b”（应以字符“ a”开头和结尾），任务是通过DFA查找字符串是否以“ a”开头和结尾。

什么是DFA（确定性有限自动机）？

在计算理论中，确定性有限自动机是理论计算机科学的一个分支，是一种接受或拒绝符号字符串的有限状态机。确定性是指要运行的计算的唯一性。

为了通过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() {
   //用于生成随机数
   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