数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C语言程序构建接受奇数个0和1的DFA
构建用于语言L={w:w有奇数个0且w有奇数个1}的确定性有限自动机(DFA)，字母表Σ={0,1}。
示例
0111、010101、01110011是接受的字符串，因为这些字符串具有奇数个0和奇数个1。
对于给定的语言，我们需要四个状态来绘制主要的DFA，它将读取奇数个0和1。我们也可以通过合并两个DFA来绘制它，其中一个只接受奇数个0，另一个接受奇数个1。
请按照以下步骤构建用于语言L={w:w有奇数个0且w有奇数个1}的DFA，字母表Σ={0,1} -
步骤1 - 对于奇数个0。
步骤2 - 对于奇数个1。
步骤3 - 将步骤1和步骤2结合起来，我们将得到最终结果。
解释
让我们以输入01110011为例，首先从q0开始，输入0时，它将进入状态q1。
现在我们需要输入1，然后它将进入状态q3。
现在在q3上再次输入1。它将进入状态q1，然后再次输入1，它将在读取0111后到达q3。
现在输入0，它将进入状态q2，然后再次输入0，它将进入状态q3。
现在，当我们再次输入1时，它将进入状态q2。最后，在状态q2上获得输入1后，它将到达状态q3，这是最终状态。
所以，字符串被接受。
示例
以下是构建用于语言L={w:w有奇数个0且w有奇数个1}的DFA的C程序，字母表Σ={0,1} -
#include <stdio.h>
int EE=0, OE=1, OO=2, EO=3; // DFA states
int state = 0; // initial DFA state
char input;
int main(void) {
printf("Enter a string of 0s and 1s: ");
while (1) {
scanf("%c", &input);
if (input == '
') // if end-of-line exit loop
break;
if ( (input != '0') && (input != '1') ) { // invalid input printf("Invalid input: program terminating
");
break;
}
if (state==0) {
// input is either '0' or '1' state = (input == '0') ? OE : EO;
}
else if(state==1) {
state = (input == '0') ? EE : OO;
}
else if (state==2) {
state = (input == '0') ? EO : OE;
} else {
state = (input == '0') ? OO : EE;
}
};
if (input == '
') {
if (state == OO)
printf("Input accepted
");
else
printf("Input rejected
");
}
return 0;
}输出
当我们执行上述程序时，我们将得到以下输出 -
Run 1: Enter a string of 0s and 1s: 101010 Input accepted Run 2: Enter a string of 0s and 1s: 10011100 Input rejected
更新于: 2021年6月14日
9K+ 浏览量
广告