有穷自动机设计
1. 实验目的
编写实现一确定的有限自动机程序，能够检验某一输入串是不是一给定文法的句子。
2. 实验内容
通过c语言实现有穷自动机。
设计思路：
通过输入字符串，然后软件内置规则进行推导，从而实现了有穷自动机，其中大量使用了switch case来实现多个推导规则。
3. 源程序
#include
//s为初态，z为终态
int in(int s,int z)
{
if(s == z)
{
printf("3\nlook!the last status belongs to Z");
return 1;
}
else
{
return 0;
}
}
//s为状态，t为输入的字符
int step(int s,char t)
{
if(t == 'a')
switch(s)
{
case 0:return 1;
case 1:return 3;
case 2:return 1;
case 3:return 3;
}
else if(t == 'b')
switch(s)
{
case 0:return 2;
case 1:return 2;
case 2:return 3;
case 3:return 3;
}
}
int realize(char *input)
{
int z = 3;
int s,i;
s = 0;
for(i=0;input[i]!='\n';i++)
{
printf("%2d",s);
s = step(s,input[i]);
}
if(in(s,z))
{
return 1;
}
else
{
return 0;
}
}
int main()
{
int i;
int a;
char input[40];
printf("FA=({0,1,2,3},{a,b},M,0,{3})\n");
printf("M:\n");
printf(" M(0,a)=1 M(0,b)=2\n");
printf(" M(1,a)=3 M(1,b)=2\n");
printf(" M(2,a)=1 M(2,b)=3\n");
printf(" M(3,a)=3 M(3,b)=3\n");
printf("请输入你要检查的串");
lop: for(i=0;input[i-1] != '\n';i++)
{
scanf("%c",&input[i]);
}
for(i=0;input[i-1]!='\n';i++)
{
if(input[i] != 'a'&&input[i] != 'b'&&input[i] != '\n')
{
printf("input error,enter again please:\n"); goto lop;
}
}
printf("the status sequence is :\n");
a = realize(input);
if(a == 1)
printf("\nSo this string can be identified\n"); else
printf("\nSo this string can't be identified\n"); printf("press enter to exit the program\n"); getchar();
}
4. 程序运行结果测试
{
printf("input error,enter again please:\n"); goto lop;
}
}
printf("the status sequence is :\n");
a = realize(input);
if(a == 1)
printf("\nSo this string can be identified\n"); else
printf("\nSo this string can't be identified\n"); printf("press enter to exit the program\n"); getchar();
}
4. 程序运行结果测试