编译原理(实验一)有穷自动机实验

avatar 2018年4月24日10:28:37 评论 361 views

一.实验目的:

  1. 理解有穷自动机的作用;
  2. 利用五元组、状态图和矩阵表表示有穷自动机;
  3. 以程序实现有穷自动机的运行过程。

 

二.实验内容

所给自动机如图所示:

三.实验要求:

1.给出自动机的五元组形式及矩阵表示。

2.模拟DFA的识别算法

3.设计相应的例子进行测试。

功能要求:输入一个单行无空格的字符串(以“#”号结束),如果该字符串是一个合法的输入,则显示“接受”,否则显示“不接受”。

 

四.实验步骤

    1.给出自动机的五元组形式及矩阵表示。

2.写出编程思路、源代码;

3.写出上机调试时发现的问题,以及解决的过程;

4.写出你所使用的测试数据;

 

五、我的代码

  1. #include <stdio.h>
  2. char str[30];
  3. void move(int num, int id) {
  4.     switch(num) {
  5.         case 0:
  6.             if(str[id] == 'a') {
  7.                 if(str[id+1] != '#')
  8.                     move(1, id+1);
  9.                 else printf("不接受\n");
  10.             }
  11.             else if(str[id] == 'b') {
  12.                 if(str[id+1] != '#') {
  13.                     move(0, id+1);
  14.                 }
  15.                 else printf("不接受\n");
  16.             } else printf("不接受\n");
  17.             break;
  18.         case 1:
  19.             if(str[id] == 'a') {
  20.                 if(str[id+1] != '#')
  21.                     move(1, id+1);
  22.                 else printf("不接受\n");
  23.             } else if(str[id] == 'b') {
  24.                 if(str[id+1] != '#')
  25.                     move(2, id+1);
  26.                 else printf("不接受\n");
  27.             } else printf("不接受\n");
  28.             break;
  29.         case 2:
  30.             if(str[id] == 'a') {
  31.                 if(str[id+1] != '#')
  32.                     move(1, id+1);
  33.                 else printf("不接受\n");
  34.             } else if(str[id] == 'b') {
  35.                 if(str[id+1] != '#')
  36.                     move(3, id+1);
  37.                 else printf("接受\n");
  38.             } else printf("不接受\n");
  39.             break;
  40.         case 3:
  41.             if(str[id] == 'a') {
  42.                 if(str[id+1] != '#')
  43.                     move(1, id+1);
  44.                 else printf("不接受\n");
  45.             } else if(str[id] == 'b') {
  46.                 if(str[id+1] != '#')
  47.                     move(0, id+1);
  48.                 else printf("不接受\n");
  49.             } else printf("不接受\n");
  50.             break;
  51.     }
  52. }
  53. int main() {
  54.     printf("自动机M五元组为:\n");
  55.     printf("({0,1,2,3},{a,b},f,0,{3})\n");
  56.     printf("f(0,a)=1  f(0,b)=0,  f(1,a)=1,  f(1,b)=2,\n  f(2,a)=1,  f(2,b)=3, f(3,a)=1,  f(3,b)=0\n");
  57.     printf("自动机的矩阵表示为:\n");
  58.     printf("    状态\\符号   a     b\n");
  59.     printf("       0       1     0\n");
  60.     printf("       1       1     2\n");
  61.     printf("       2       1     3\n");
  62.     printf("       3       1     0\n");
  63.     printf("请输入待检验字符串:\n");
  64.     while(scanf("%s", str) != EOF) {
  65.         move(00);
  66.         printf("请再来测试:\n");
  67.     }
  68.     return 0;
  69. }

运行结果

 

 

  • 微信
  • 交流学习,有偿服务
  • weinxin
  • 博客/Java交流群
  • 资源分享,问题解决,技术交流。群号:590480292
  • weinxin
avatar

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: