数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C程序构建接受以“01”结尾的语言的DFA
问题
设计一个确定性有限自动机 (DFA)，其∑ = {0, 1}，接受字符集{0, 1}上以“01”结尾的语言。
解答
给定语言生成的字符串如下：
L={01,001,101,110001,1001,……….}字符串的最小长度为2，给定语言的DFA由以下状态组成：2+1 = 3个状态。
这里：
q0 − 输入0时，它进入状态q1；输入1时，它保持自身状态。
q1 − 输入0时，它保持自身状态；输入1时，它进入状态q2。
q2 − 输入0时，它进入状态q1；输入1时，它进入状态q0。状态q2是最终状态。
示例
以下是构建DFA的C程序，其∑ = {0, 1}，接受字符集{0, 1}上以“01”结尾的语言：
#include
#define max 100
main() {
char str[max],f='a';
int i;
printf("enter the string to be checked: ");
scanf("%s",str);
for(i=0;str[i]!='\0';i++) {
switch(f) {
case 'a': if(str[i]=='0') f='b';
else if(str[i]=='1') f='a';
break;
case 'b': if(str[i]=='0') f='b';
else if(str[i]=='1') f='c';
break;
case 'c': if(str[i]=='0') f='b';
else if(str[i]=='1') f='a';
break;
}
}
if(f=='c')
printf("
String is accepted", f);
else printf("
String is not accepted", f);
return 0;
}输出
输出结果如下：
Run 1: enter the string to be checked: 10101001 String is accepted. Run 2: enter the string to be checked: 10000010 String is not accepted.
更新于：2021年6月15日
14K+ 浏览量
广告