编译原理（实验一）有穷自动机实验

言曌 2018年04月24日10:28:37 6 5778 views

博主分享免费Java教学视频，B站账号：Java刘哥，长期提供技术问题解决、项目定制：本站商品点此

一．实验目的：

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

二．实验内容

所给自动机如图所示：

三．实验要求：

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

2．模拟DFA的识别算法

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

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

四．实验步骤

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

2．写出编程思路、源代码；

3．写出上机调试时发现的问题，以及解决的过程；

4．写出你所使用的测试数据；

五、我的代码

#include <stdio.h>
char str[30];
void move(int num, int id) {
switch(num) {
case 0:
if(str[id] == 'a') {
if(str[id+1] != '#')
move(1, id+1);
else printf("不接受\n");
}
else if(str[id] == 'b') {
if(str[id+1] != '#') {
move(0, id+1);
}
else printf("不接受\n");
} else printf("不接受\n");
break;
case 1:
if(str[id] == 'a') {
if(str[id+1] != '#')
move(1, id+1);
else printf("不接受\n");
} else if(str[id] == 'b') {
if(str[id+1] != '#')
move(2, id+1);
else printf("不接受\n");
} else printf("不接受\n");
break;
case 2:
if(str[id] == 'a') {
if(str[id+1] != '#')
move(1, id+1);
else printf("不接受\n");
} else if(str[id] == 'b') {
if(str[id+1] != '#')
move(3, id+1);
else printf("接受\n");
} else printf("不接受\n");
break;
case 3:
if(str[id] == 'a') {
if(str[id+1] != '#')
move(1, id+1);
else printf("不接受\n");
} else if(str[id] == 'b') {
if(str[id+1] != '#')
move(0, id+1);
else printf("不接受\n");
} else printf("不接受\n");
break;
}
}
int main() {
printf("自动机M五元组为：\n");
printf("({0,1,2,3},{a,b},f,0,{3})\n");
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");
printf("自动机的矩阵表示为:\n");
printf(" 状态\\符号 a b\n");
printf(" 0 1 0\n");
printf(" 1 1 2\n");
printf(" 2 1 3\n");
printf(" 3 1 0\n");
printf("请输入待检验字符串：\n");
while(scanf("%s", str) != EOF) {
move(0, 0);
printf("请再来测试：\n");
}
return 0;
}