首页 > 代码库 > 编译原理 实验2 DFA的运行

编译原理 实验2 DFA的运行

DFA的运行

一、 实验目的

1.理解有穷自动机的作用;

2.利用状态图和状态表表示有穷自动机;

3.以程序实现有穷自动机的运行过程;

4.利用状态表和有穷自动机的运行原理编制程序,使得程序能够识别一个输入串是否为一个有效的符号串。具体可以选择下面之一:无符号定点实数,无符号正偶数,自然数,整数,十六进制数,或其他自己定义的符号串。

二、 实验环境

操作系统:window xp

编写环境:visual c++ 

编写语言:c语言

三、 实验内容

1.简单介绍你所设计的有穷自动机。(要求必须完成无符号正偶数的有穷自动机

无符号正偶数 正规式

a:1 3 5 7 9

b:2 4 6 8

c:0 

(a|b)(a|b|c)*(b|c)|b

2.画出有穷自动机的状态表

3.状态图:

状态表: 0 1 2

0 1 2 -1

1 1 3 3

2 1 3 3

3 1 3 3

3.测试数据和结果。

修改下表中的内容。要注意输入数据的代表性)

组号

输入数据

结果

1

1#

接受

2

0#

接受

3

2#

接受

4

01#

接受

5

02#

接受

6

9000#

接受

7

+2#

接受

8

-2#

不接受

9

9999#

不接受

10

1.25#

不接受

11

-1.12#

不接受

12

122.#

不接受

四、 实验结果

五、 实验小结

附录:源代码

//正规式 (a|b)(a|b|c)*(b|c)|b

#include <cstdio>

#include <cstring>

using namespace std;

char a[1000];

int dp[4][3] = {

	1, 2, -1,

	1, 3, 3,

	1, 3, 3,

	1, 3, 3,

};

bool Q[4] = {0, 0, 1, 1};

bool run()

{

	int s = 0;

	for(int i = 0; a[i] != '#'; i++)

	{

		if(a[i] == '1' || a[i] == '3' || a[i] == '5' || a[i] == '7' || a[i] == '9')

			s = dp[s][0];

		else if(a[i] == '2' || a[i] == '4' || a[i] == '6' || a[i] == '8')

			s = dp[s][1];

		else if(a[i] == '0')

			s = dp[s][2];

		else

			return false;

		if(s == -1)

			return false;

	}

	if(Q[s])

		return true;

	return false;

} 

int main()

{

	printf("请输入一个数\n");//输入的字符串以#结尾

	while(1)

	{

		 

		scanf("%s", a);

		if(run())

			printf("接受\n");

		else

			printf("不接受\n"); 

	}

	return 0;



编译原理 实验2 DFA的运行