在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