C语言程序构建用于正则表达式(a+aa*b)*的DFA

设计一个确定性有限自动机（DFA）来接受语言L = (a+aa*b)*。如果给定的字符串被DFA接受，则打印“字符串被接受”。否则，打印“字符串被拒绝”。

示例1

Input: Enter Input String
      aaaba
Output: String Accepted.

说明 - 给定的字符串的形式为(a+aa*b)*，因为第一个字符是a，后面跟着a或ab。

示例2

Input: Enter Input String
   baabaab
Output: String not Accepted.

给定正则表达式(a+aa*b)的DFA如下：

说明 -

  • 如果第一个字符始终为a，则遍历剩余字符串并检查是否有任何字符为a或ab。

  • 如果字符串中的第一个字符为'b'，则打印“字符串被拒绝”。

  • 如果在遍历过程中存在任何除a或b之外的字符，则打印“输入值错误”。

  • 否则，打印“字符串被接受”。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

程序

以下是构建用于正则表达式(a+aa*b)*的DFA的C语言程序 -

#include<stdio.h>
#include<conio.h>
#include<strings.h>
void main() {
   int table[2][2],i,j,l,status=0,success;
   char input[100];
   printf("To implementing DFA of language (a+aa*b)*
 Enter Input String:”);
   table[0][0]=1;
   table[0][1]=-1;
   table[1][0]=1;
   table[1][1]=0;
   scanf("%s",input);
   l=strlen(input);
   for (i=0;i<l;i++) {
      if(input[i]!='a'&&input[i]!='b') {
         printf("The entered Value is wrong");
         getch();
         exit(0);
      }
      if(input[i]=='a')
      status=table[status][0]; else
      status=table[status][1];
      if(status==-1) {
         printf("String not Accepted");
         break;
      }
   }
   if(i==l)
      printf("String Accepted");
   getch();
}

输出

执行上述程序时，会输出以下内容 -

Run 1:
To implementing DFA of language (a+aa*b)*
Enter Input String:cbsd
The entered Value is wrong.
Run 2:
To implementing DFA of language (a+aa*b)*
Enter Input String:abbababa
String not Accepted.
Run 3:
To implementing DFA of language (a+aa*b)*
Enter Input String:babbaab
String not Accepted.

更新于: 2021年6月14日

13K+ 浏览量

开启你的职业生涯

通过完成课程获得认证

开始学习
广告