数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：构建从输入(a, b)中以‘a’开头和结尾的DFA
给定一个由字符‘a’和‘b’组成的DFA字符串，该字符串应该以字符‘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() {
// 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
更新于： 2019年12月23日
901 次浏览
广告