首页 > 代码库 > 有穷状态自动机

有穷状态自动机

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

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

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

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

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

3. 以五元组形式输出。

三、    算法

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

技术分享

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

实验方法:

  1. 源程序名:压缩包文件(rarzip词法分析程序.zip
  2. 源程序名:词法分析程序.c
  3. 可执行程序名:词法分析程序.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("\n 请输入正规式,以#结束 :");
12     ch=getchar();
13     do
14     {
15        if(ch==|)
16         {
17             a[i][j]=\0;
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]=\0;
28     for(x=0;x<=i;x++)
29     {
30         y=0;
31         count=1;
32         while(a[x][y]!=\0)
33         {
34             if(a[x][y]==.)
35             {
36                if(a[x][y]==.&& count==1)
37                {
38                  printf("\n f(0,%c)=%d\n",a[x][y-1],number);
39                  if(a[x][y+2]==\0)
40                   printf("\n f(%d,%c)=1\n",number,a[x][y+1]);
41                  number++;
42                  count=2;
43                }
44             else if(a[x][y]==.&& count!=1)
45                {
46                    printf("\n f(%d,%c)=%d\n",number-1,a[x][y-1],number);
47                    if(a[x][y+2]==\0)
48                     printf("\n f(%d,%c)=1\n",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("\n f(0,^)=%d\n",number);
57                    printf("\n f(%d,%c)=%d\n",number,a[x][y-1],number);
58                    if(a[x][y+1]==\0)
59                     printf("\n f(%d,^)=1\n",number);
60                    else
61                     printf("\n f(%d,^)=%d\n",number,number+1);
62                    number++;
63                    count=2;
64                }
65              else if(a[x][y]==*&& count!=1)
66                {
67                    printf("\n f(%d,%c)=%d\n",number,a[x][y-1],number);
68                    if(a[x][y+1]==\0)
69                     printf("\n f(%d,~)=1\n",number);
70                    else
71                     printf("\n f(%d,~)=%d\n",number,number+1);
72                    number++;
73                }
74             }
75             y++;
76         }
77     }
78 
79 }
  1. 4.运行结果及分析

技术分享

 

有穷状态自动机