有穷状态自动机

实验三有限自动机的构造与识别

专业：商业软件工程姓名：陈蔓嘉学号：201506110245

一、 实验目的
1、掌握有穷状态自动机的概念；
2、掌握有穷状态自动机的存储及表示方法；
3、掌握有穷状态自动机与正则式之间的关系。

二、 实验要求
1、输入正规式；

2、构造该正规式的有穷状态自动机；

3. 以五元组形式输出。

三、算法

1、参见教材的转换规则。

四、 实验方法、步骤及结果测试

实验方法：

源程序名：压缩包文件（rar或zip）词法分析程序.zip
源程序名：词法分析程序.c
可执行程序名：词法分析程序.exe

算法：

 1 #include<stdio.h>
 2 #include<string.h>
 3 int i=0,j=0,x=0;
 4 int y;
 5 int number=2;
 6 int count=0;
 7 char ch;
 8 char a[100][100];
 9 main()
10 {
11     printf("
 请输入正规式,以#结束 ：");
12     ch=getchar();
13     do
14     {
15        if(ch=='|')
16         {
17             a[i][j]='';
18             j=0;
19             i++;
20             ch=getchar();
21             continue;
22         }
23         a[i][j]=ch;
24         j++;
25         ch=getchar();
26     }while(ch!='#');
27     a[i][j]='';
28     for(x=0;x<=i;x++)
29     {
30         y=0;
31         count=1;
32         while(a[x][y]!='')
33         {
34             if(a[x][y]=='.')
35             {
36                if(a[x][y]=='.'&& count==1)
37                {
38                  printf("
 f(0,%c)=%d
",a[x][y-1],number);
39                  if(a[x][y+2]=='')
40                   printf("
 f(%d,%c)=1
",number,a[x][y+1]);
41                  number++;
42                  count=2;
43                }
44             else if(a[x][y]=='.'&& count!=1)
45                {
46                    printf("
 f(%d,%c)=%d
",number-1,a[x][y-1],number);
47                    if(a[x][y+2]=='')
48                     printf("
 f(%d,%c)=1
",number,a[x][y+1]);
49                     number++;
50             }
51             }
52              if(a[x][y]=='*')
53              {
54                if(a[x][y]=='*'&& count==1)
55               {
56                    printf("
 f(0,^)=%d
",number);
57                    printf("
 f(%d,%c)=%d
",number,a[x][y-1],number);
58                    if(a[x][y+1]=='')
59                     printf("
 f(%d,^)=1
",number);
60                    else
61                     printf("
 f(%d,^)=%d
",number,number+1);
62                    number++;
63                    count=2;
64                }
65              else if(a[x][y]=='*'&& count!=1)
66                {
67                    printf("
 f(%d,%c)=%d
",number,a[x][y-1],number);
68                    if(a[x][y+1]=='')
69                     printf("
 f(%d,~)=1
",number);
70                    else
71                     printf("
 f(%d,~)=%d
",number,number+1);
72                    number++;
73                }
74             }
75             y++;
76         }
77     }
78 
79 }

4.运行结果及分析